Round #849/1791 (Div. 4)
On This Page
Contest date: 2023-02-03
A. Codeforces Checking
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
geometry, implementation, *800
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
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.)
def solve(n, s): res = n if res <= 1: return 1 while res > 0: first = s 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))
>>> deque('123') deque(['1', '2', '3'])
from collections import deque def solve(n, s): s = deque(s) while len(s) and s != s[-1]: s.popleft() s.pop() print(len(s))
D. Distinct Split
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
abcabcd can be splited into
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 string
ab better that
f('abc') = 3 f('abca') = 3 f('ab') = 2 f('b') = 1 5 > 4
- 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)))
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()
b_set = set(s[point+2:]) is very heavy on each step in the loop.
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
𝑏 when the frequency of a character is greater than zero.
E. Negatives and Positives
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).
def solve(): n = inp_int() a = inp_int_list() count_minus = 0 count_zeros = 0 min_val = abs(a) 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()
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
There are two types of inputs (cases) (in addition to array
n of test cases):
- line with two elements:
2 x. Starts with
- line with three elements:
1 l r. Starts with
In 1st case: print array
In 2nd case: update the value of
𝑎𝑖 to the sum of its digits.
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
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 =  * (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)
greedy, sortings *1100
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
i, you can do one of three actions:
- Move left one unit: this action costs
- Move right one unit: this action also costs
- Use a teleporter at point
i: this action costs $a_i$ coins. When you use a teleporter, you are immediately teleported back to point
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 point
i = 5, and you use the teleporter located at point
5, you will be immediately transported back to point
0, 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
- the number of coins you have
- the list of teleporter costs
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
c, and all elements of
a are positive integers.
For example, the following input should return
n = 8 c = 32 a = [100, 52, 13, 6, 9, 4, 100, 35] max_teleporters(n, c, a) => 2
Will use greedy algorithm.
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:
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)
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).