Round #849/1791 (Div. 4)

TODO G2

Contest date: 2023-02-03

• Contest problems

• Editorial

• Template with function snippets

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

1. If we concatenate two strings into one s, we need to keep order of the letters.
2. Need to split this string s in a such a way so that repeated letters fall into different parts of string s (a and b).

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:

1. Divide string into two parts starting left part from len 1. For example: s = ‘abcabc’ a = ‘a’ b = ‘bcabc’
2. Increase left part and decrease right part.
   1. 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):

1. line with two elements: 2 x. Starts with 2
2. line with three elements: 1 l r. Starts with 1

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 a_i 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

1. Use FenwickTree template
2. Save there count of a[i] changes. No need to calculate more than 3 times
3. 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 1 coin.
• Move right one unit: this action also costs 1 coin.
• Use a teleporter at point i: this action costs $a_i$ coins. When you use a teleporter, you are immediately teleported back to point 0.

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 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).