Round #849/1791 (Div. 4)
On This Page
TODO G2
Contest date: 2023-02-03
A. Codeforces Checking
https://codeforces.com/contest/1791/problem/A
Solution:
def solve(letter):
code = "codeforces"
if letter in code:
print("YES")
else:
print("NO")
for _ in range(int(inp())):
letter = inp()
solve(letter)
B. Following Directions
https://codeforces.com/contest/1791/problem/B
geometry, implementation, *800
Solution:
def solve(n, s):
x = 0
y = 0
for move in s:
if move == 'L':
x -= 1
elif move == 'R':
x += 1
elif move == 'U':
y += 1
elif move == 'D':
y -= 1
if x == 1 and y == 1:
print("YES")
break
else:
print("NO")
for _ in range(int(inp())): # attempts
num = int(inp())
letter = inp()
solve(num, letter)
C. Prepend and Append
https://codeforces.com/contest/1791/problem/C
implementation, two pointers, *800
In this problem we are allowed:
- to remove first letter of the binary string and last.
- We can do this while first letter is not equal to the last according to the definition of the problem. (Add πΆ to one end of the string and π· to the other end of the string.)
Solution:
def solve(n, s):
res = n
if res <= 1:
return 1
while res > 0:
first = s[0]
last = s[-1]
if first == last:
return res
s = s[1:-1]
res -= 2
return res
for _ in range(int(inp())): # attempts
n = int(inp())
s = inp()
print(solve(n, s))
Optimized:
Use deque from collection module
>>> deque('123')
deque(['1', '2', '3'])
from collections import deque
def solve(n, s):
s = deque(s)
while len(s) and s[0] != s[-1]:
s.popleft()
s.pop()
print(len(s))
D. Distinct Split
https://codeforces.com/contest/1791/problem/D
brute force, greedy, strings, *1000
If we get a string abcabcd we need to split into two strings.
Note 1: result number could not be more than string length.
abcabcd can be splited into abc and abcd.
len(‘abc’) = 3 #3 distinct letters
len(‘abcd’) = 4
3 + 4 = 7
Output: maximum possible value of π(π)+π(π) such that π+π=π .
Let’s look at other examples and possible edge cases.
Note 2: function for a string π₯ - is the number of distinct characters. (From problem statement.)
'aaaaa' => 1 # 1 distinct
- If we concatenate two strings into one
s, we need to keep order of the letters. - Need to split this string
sin a such a way so that repeated letters fall into different parts of strings(aandb).
abcab => abc and ab better that abca and b because:
f('abc') = 3 f('abca') = 3
f('ab') = 2 f('b') = 1
5 > 4
Approach 1:
- Divide string into two parts starting left part from
len 1. For example: s = ‘abcabc’ a = ‘a’ b = ‘bcabc’ - Increase left part and decrease right part.
- On each step calculate sum of distinct letters. For example: set(a) + set(b) max_result = max(max_result, len(set(a)) + len(set(b)))
Solution:
def solve():
# input
n = int(inp())
s = inp()
point = 0
max_n = 0
a_set = set(s[point])
b_set = set(s[point+1:])
while point < n - 1:
max_n = max(max_n, len(a_set) + len(b_set))
a_set.add(s[point + 1])
b_set = set(s[point+2:])
point += 1
if max_n == n:
break
return max_n
def run():
for _ in range(inp_int()):
print(solve())
if __name__ == "__main__":
if os.environ.get("CODE_DEBUG"):
sys.stdin = open("./input.txt", "r")
start_time = time.time()
run()
print("\n--- %s seconds ---\n" % (time.time() - start_time))
else:
run()
Optimization:
b_set = set(s[point+2:]) is very heavy on each step in the loop.
Use Counter instead.
def solve():
# input
n = int(inp())
s = inp()
point = 0
max_n = 0
a = set(s[point])
b = Counter(s[point+1:])
while point < n - 1:
max_n = max(max_n, len(a) + len(b))
point += 1
b_letter = s[point]
a.add(b_letter)
b[b_letter] -= 1
if b[b_letter] <= 0:
del b[b_letter]
if max_n == n:
break
return max_n
Explanation from Codeforces:
Let’s check all splitting points π for all (1β€πβ€πβ1). We denote a splitting point as the last index of the first string we take (and all the remaining characters will go to the second string).
We need to keep a dynamic count of the number of distinct characters in both strings π (the first string) and π (the second string).
We can do this using two frequency arrays (and adding one to the distinct count of either string π or π when the frequency of a character is greater than zero.
E. Negatives and Positives
https://codeforces.com/contest/1791/problem/E
dp, greedy, sortings, *1100
Explanation from Codeforces:
We can notice that by performing any number of operations, the parity of the count of negative numbers won’t ever change.
Thus, if the number of negative numbers is initially even, we can make it equal to 0 by performing some operations.
So, for an even count of negative numbers, the answer is the sum of the absolute values of all numbers (since we can make all of them positive). And if the count of negative numbers is odd, we must have one negative number at the end.
We will choose the one smallest by absolute value and keep the rest positive (for simplicity, we consider β0 as a negative number).
Solution:
def solve():
n = inp_int()
a = inp_int_list()
count_minus = 0
count_zeros = 0
min_val = abs(a[0])
s = 0 # sum
for i in range(n):
if a[i] < 0:
count_minus += 1
if a[i] == 0:
count_zeros += 1
v = abs(a[i])
s += v
min_val = min(min_val, v)
count_minus = count_minus % 2 # if count of odd numbers is negative
count_minus -= count_zeros
if count_minus <= 0:
return s
if count_minus == 1:
s -= abs(min_val * 2)
return s
return s
def run():
for _ in range(inp_int()):
print(solve())
run()
Optimization:
def solve():
n = inp_int()
a = inp_int_list()
count_minus = 0
for i in range(n):
if a[i] < 0:
count_minus += 1
a[i] = abs(a[i])
s = sum(a) # sum
if count_minus % 2:
return s - min(a) * 2
else:
return s
F. Range Update Point Query
https://codeforces.com/contest/1791/problem/F
There are two types of inputs (cases) (in addition to array a and n of test cases):
- line with two elements:
2 x. Starts with2 - line with three elements:
1 l r. Starts with1
In 1st case: print array a
In 2nd case: update the value of ππ to the sum of its digits.
Slow Solution:
def sum_of_digits(n):
sum = 0
while n:
sum += n % 10
n //= 10
return sum
def solve():
n, q = map(int, inp().split())
a = list(map(int, inp().split()))
while q:
q -= 1
t, *params = map(int, inp().split())
if t == 1:
l, r = params
for i in range(l-1, r):
a[i] = sum_of_digits(a[i])
else:
x, = params
print(a[x-1])
t = int(inp().strip())
for _ in range(t): # attempts
solve()
This solution is slow because of loop:
for i in range(l-1, r):
a[i] = sum_of_digits(a[i])
The key here is the following: after the operation is applied on ai thrice, it won’t change after any further operations.
Problem here is to implement a solution how to save information how many times there was a change of a[i].
One way is to use Fenwick Tree
- Use FenwickTree template
- Save there count of
a[i]changes. No need to calculate more than 3 times - When need to print
a[x]calculate up to three times and print result.
class Fenwick: #also known as Binary Indexed Tree (BIT)
# no need to change here anything
def __init__(self, n):
self.n = n
self.bit = [0] * (n+1)
def add(self, idx, val):
while idx <= self.n:
self.bit[idx] += val
idx += idx & -idx
def add_range(self, l, r, val):
self.add(l, val)
self.add(r+1, -val)
def query(self, idx):
#Calculates the sum of the elements from the beginning to idx
ret = 0
while idx > 0:
ret += self.bit[idx]
idx -= idx & -idx
return ret
def range_sum(self, l, r):
# Return the sum of the elements from l (inclusive) to r (exclusive)
return self.prefix_sum(r - 1) - self.prefix_sum(l - 1)
def prefix_sum(self, x):
# return sum upto and including element x
z = x
res = 0
while z >= 0:
res += self.bit[z]
# Strip trailing zeros from z, and then take away one
z = (z & (z + 1)) - 1
return res
def solve():
n, q = list(map(int, inp().split()))
a = list(map(int, inp().split()))
tree = BIT(n)
while q:
q -= 1
t, *params = map(int, inp().split())
if t == 1:
l, r = params
tree.add(l, 1)
tree.add(r + 1, -1)
else:
x, = params
need = min(3, tree.query(x)) # get count of times need to change a[i]
cur = a[x - 1]
for i in range(need):
cur = sum_of_digits(cur)
print(cur)
Good to know
- Segment Tree template tutorial
- A Visual Introduction to Fenwick Tree | medium
- Fenwick Tree | cp-algorithms
- Segment Tree | cp-algorithms
- ΠΠ΅ΡΠ΅Π²ΠΎ ΠΎΡΡΠ΅Π·ΠΊΠΎΠ² | algorithmica
- ΠΠ΅ΡΠ΅Π²ΠΎ Π€Π΅Π½Π²ΠΈΠΊΠ° | algorithmica
- ΠΠ΅ΡΠ΅Π²ΠΎ Π€Π΅Π½Π²ΠΈΠΊΠ° | habr
G1. Teleporters (Easy Version)
https://codeforces.com/contest/1791/problem/G1
greedy, sortings *1100
Statement:
You are playing a game where you are given a list of teleporters (0,2,β¦,π), each located at a point on the number line. The number line includes all integers from 0 to n.
At point i, you can do one of three actions:
- Move left one unit: this action costs
1coin. - Move right one unit: this action also costs
1coin. - Use a teleporter at point
i: this action costs $a_i$ coins. When you use a teleporter, you are immediately teleported back to point0.
Last statement in the problem means that at any point i on the number line, you have the option to use a teleporter located at that point, which will immediately transport you back to point
0. However, using a teleporter costs a certain number of coins, denoted by $a_i$. For example, if you are at pointi = 5, and you use the teleporter located at point5, you will be immediately transported back to point0, but you will have to pay the cost $a_i$ in coins to do so.Essentially, the teleporters provide a way for you to quickly move back to the starting point (point
0) without having to take multiple steps, but this convenience comes at a cost. You can only use each teleporter once, and you must have enough coins to pay the cost of using it.
You start at point 0, and you have c coins to spend. Your goal is to use as many teleporters as possible while still having at least 1 coin left over. You cannot use a teleporter more than once.
Write a function max_teleporters(n, c, a) that takes in
- the length of the number line
n - the number of coins you have
c - the list of teleporter costs
a.
The function should return the maximum number of teleporters you can use given your starting position at 0 and the number of coins you have to spend.
You may assume that n, c, and all elements of a are positive integers.
For example, the following input should return 2:
n = 8
c = 32
a = [100, 52, 13, 6, 9, 4, 100, 35]
max_teleporters(n, c, a) => 2
Will use greedy algorithm.
Approach:
Given input: n = 8, c = 32, a = [100, 52, 13, 6, 9, 4, 100, 35]
Step 1: Calculate the cost of each teleporter
- For each teleporter at position i, add the index i and the cost a[i]
- The resulting array cost contains the costs to use each teleporter, accounting for the cost of moving to that teleporter’s position: [101, 54, 16, 10, 14, 10, 107, 43]
Step 2: Sort the cost array in ascending order
- Sorting the array ensures that we use the cheapest teleporters first
Step 3: Compute the maximum number of teleporters we can use
- Initialize a variable used to 0 to keep track of how many teleporters we’ve used
- Iterate over the sorted cost array, adding the cost of each teleporter to a running total total
- If the current total is less than or equal to c, we can use the current teleporter, so increment used
- If the current total is greater than c, we’ve run out of coins and can’t use any more teleporters, so exit the loop
- Return the final value of used
Step 4: Return the maximum number of teleporters we can use
- The maximum number of teleporters we can use is the value of used computed in Step 3:
2
Solution:
def max_teleporters(n, c, a):
# First, we add the index of each teleporter to its cost, so that we can easily
# calculate the cost to reach each teleporter from the starting position (0).
for i in range(n):
a[i] += i + 1
# We then sort the list of teleporter costs in ascending order, so that we can
# use the cheapest teleporters first.
a.sort()
# We iterate over the sorted list of teleporter costs, using as many teleporters
# as possible while still having at least one coin remaining. We keep track of the
# number of teleporters used in the "used" variable.
used = 0
for cost in a:
if cost <= c:
used += 1
c -= cost
else:
break
# Finally, we return the number of teleporters used.
return used
Explanation from Codeforces:
It’s easy to see that it’s optimal to only move right or to use a portal once we are at it. We can notice that when we teleport back, the problem is independent of the previous choices.
We still are at point 0 and have some portals left. Thus, we can just find out the individual cost of each portal, sort portals by individual costs, and take them from smallest to largest by cost as long as we can.
The cost of portal π is $π+ππ_$ (since we pay &π_π& to use it and need π moves to get to it).
G2. Teleporters (Hard Version)
https://codeforces.com/contest/1791/problem/G2
binary, search, greedy, sortings *1900
Explanation from Codeforces:
Please also refer to the tutorial for the easy version.
If we are not at the first taken portal, the problem is still independent for each portal, but this time the cost of a portal is $πππ(π_π+π,π_π+π+1βπ)$ (since we can come to a portal either from point 0 or point $π+1$).
So, we again sort the portals by their costs. But this time, we need to make sure that the first taken portal is taken from point 0, so we will iterate over all portals and check the maximum amount of portals we can take if we use it as the first one.
We can check this using prefix sums over the minimum cost array and binary searching, checking if the amount of considered portals taken doesn’t exceed the number of coins we initially have (we also have to deal with the case when the portal we are considering is included both times as the initial portal and in the minimum cost prefix).