edit: fixed

1. Problem names are in Russian
2. You put F before E in the editorial.

I don't understand how E was accepted by coordinators since it is so standard to anyone who's ever seen Hierholzer's before.

I was not able to debug my code for finding Eulerian path, damn sed lyf :(

2110D - Fewer Batteries can be solved without binary search too.

Solution is that ->

First for each index store the minimum batteries that will be required from that point so that one is able to reach the endpoint(nth node). That is done by dijisktra on the graph with opposite edge starting from node n and cost as maximum of all the nodes visited .

After that ,minimising the cost with normal dijisktra on forward graph starting with node 0 and cost as maximum of all the nodes visited.

U can look to my submission 321152832

Problem F could also be solved in O(N), tho it doesn't matter much. Most things are same, except there is one more observation: - Let's say our current array is a[1] <= a[2] <= a[3]... a[N] - Then, we don't actually need to try f(a[i], a[N]), where a[i] <= a[N-1]/2, since max possible value of f(a[i], a[N]) <= min possible value of f(a[N-1], a[N]). (where a[i] * 2 <= a[N-1])

Thus, if the maximum value gets updated (let's say x is new, y is the old one):

1. 2*y > x, obviously answer = x.

2. We check elements in range y/2...y. (We can push everything to a set and just iterate from the back).

Well, one can see that we only process an element with a current maximum only once, thus we can just push everything to a vector and clear after each use: 321161406

In question D many solution that were accepted shouldn't have passed system testing cause now that I am trying submit those same solution again they are giving MLE on test case 31 which those solutions were not tested against in the system testing phase!

My submission for D seems to be $$$\mathcal{O}(n^2)$$$ but there is no testcase to fail it. 321147941

For each node, I compute a list of intervals to describe all the possible battery counts at that node. Then computing these lists is a straightforward DP.

But for each transition between $$$u$$$ and $$$v$$$, $$$v$$$'s entire list must be checked. This motivates a hack testcase: for the first $$$\frac{n}{2}$$$ nodes, form a chain and attach each node to the middle node as well. Then for the other $$$\frac{n}{2}$$$ nodes, attach them to the middle node. The size of the middle node's list is $$$\frac{n}{2}$$$ now, and computing $$$\frac{n}{2}$$$ more transitions from that will give quadratic runtime. Here's the generator if I wasn't clear:

N = 200000 

print(1)
print(N, N-1 + N//2-2)
print(N * "1000000000 ")
for i in range(1, N+1):
    if i == N//2:
        continue

    if i < N//2 - 1:
        print(i, i+1, 1)

    print(min(i, N//2), max(i, N//2), 1)

My final solution adds some optimization on top of the original idea, but with some work it can be defeated as well.

Is there a way to improve the worst bound for my approach?

Did anyone else get Runtime Error on test case 12 while solving E? How did you solve it?

why can dfs pass D?????? i tried many ways but not dfs till 01:30

It's really weird that my solution passed just with a break. It does Dijkstra on $$$(idx,sum)$$$, which should be $$$O((n+m)W\log{n})$$$ in the worst case. Can anyone try to uphack it? 321125700

Can anyone tell me why my solution is failing? It says that the jury found a solution, but I don't still can't see why my solution couldn't find the euler path, even after accounting for the euler cycle.

Problem E, -> Submission

This works too. (For D)

~~~~~
import random
import sys
import heapq
from bisect import *
from collections import defaultdict,deque,Counter
input=sys.stdin.readline
def readList():
    return list(map(int, input().split()))
def readInt():
    return int(input())
def readInts():
    return map(int, input().split())
def readStr():
    return input().strip()
def print_array(arr):
    print(" ".join(map(str, arr)))
def printer(is_True):
    print('YES') if is_True else print('NO')
def random_seed():
    return random.randint(0,10**9+7)
for _ in range(readInt()):
    n,m=readInts()
    b=readList()
    edges=[]
    for _ in range(m):
        s,t,w=readInts()
        edges.append((s-1,t-1,w))
    edges.sort(key=lambda x:x[-1])
    batteries=[-1]*n
    batteries[0]=b[0]
    q=deque()
    children=defaultdict(list)
    ans=-1
    for s,t,w in edges:
        children[s].append((t,w))
        if batteries[s]>=w and batteries[t]<batteries[s]+b[t]:
            batteries[t]=batteries[s]+b[t]
            q.append(t)
        while q:
            node=q.popleft()
            for neigh,weight in children[node]:
                if batteries[node]>=weight and batteries[neigh]<batteries[node]+b[neigh]:
                    batteries[neigh]=batteries[node]+b[neigh]
                    q.append(neigh)
        if batteries[n-1]>=0:
            ans=w
            break
    print(ans)

What is the reason behind DFS failing in test case #31 ?.

How one would have figured it out before implementing during contest that (Oh no DFS won't work need to figure out something else ...).

Hey for problem C my idea was at every point where there is -1 to check if the minimum element in the remaining array is smaller than or equal to current height.If yes , set that arr[i] to 0 otherwise 1. THen I later check if the given array is able to pass the array But on test 2 , number 89 this shows wrong.

Can anyone help me out in finding a teat case were my code fails

https://mirror.codeforces.com/contest/2110/submission/321134907

Could you help me see why the time complexity is qualified? I used the priorityqueue and visit arrays，problem D：321109278

c&d are too easy, though I was stumbled by c because of an imperceptible mistake, which made my rating down

However, e&f are marvelous! I love them very much

Can anyone please help me out with why my code fails in pretest 2. (Submission : 321127415 )

My intuition is that I store the minimum of all upper limits among the limits from the end to the particular index i. So we only assign v[i]=1 when h<mini[i] because if we increase h when h is already >=mini[i], the answer would fail because we already exceeded the upper limit of atleast one obstacle. And if (h<mini[i]) , we can always keep increasing h by 1 (or assigning v[i] as 1) BECAUSE all the upper limits are at least mini[i] so we don't exceed anyone's upper limit and if we talk about exceeding the lower limit since we increase height by 1 now, it does not matter because being above the lower limit is still being in the range (li<=h<=ri) so we only have to worry abt not even reaching the lower limit of any one obstacle but since we keep increasing the height when v[i] has not yet reached mini[i], so we tend to reach the lower limits of obstacles as well cuz being above the lower limits(while being below the minimum of upper limits) is justified. So, I do not understand how it is still not an optimal path! :(

Can anyone please help me out with why my code fails in pretest 2. 321158954

I store the minimum (along with its index) of all upper limits among the limits from the end to the particular index, and from the range of current index to maximum index of the minimum upper limit i count the number of compulsory 1s using precomputed num1 array in O(1). So we only assign v[i]=1 when h+(number of compulsory 1s)<mini[i] because if we increase h when h+(number of compulsory 1s) is already >=mini[i], the answer would fail because we already exceeded the upper limit of atleast one obstacle.

My code - ~~~~~

void solve(){

int n;
cin >> n;
v32 d(n), num1(n+1);
vv32 p(n, v32(2)), minn(n, v32(2));
forn(i, n) cin >> d[i];
forn(i, n) cin >> p[i][0] >> p[i][1];
forn(i, n) num1[i+1] = num1[i]+(d[i] == 1);
minn[n-1][0] = p[n-1][1]; minn[n-1][1] = n-1;
rforn(i, n-2){
    minn[i] = minn[i+1];
    if(p[i][1] < minn[i][0]) minn[i][0] = p[i][1], minn[i][1] = i;
}

int curh = 0;
forn(i, n){
    if(d[i] >= 0){
        curh += d[i];
        if(curh < p[i][0] || curh > p[i][1]){
            cout << "-1\n";
            return;
        }
    } else {
        int diff = minn[i][0]-curh, ind = minn[i][1], ct1 = num1[ind]-num1[i];
        // cout << diff << " " << ind << " " << ct1 << ln;
        if(ct1 < diff){
            d[i] = 1;
            curh++;
        } else if(ct1 == diff) d[i] = 0;
        else {
            cout << "-1\n";
            return;
        }
        if(curh < p[i][0] || curh > p[i][1]){
            cout << "-1\n";
            return;
        }
    }
}

print_vec(d);

} ~~~~~

In problem C i applied a greedy approach where i increase the height where ever it is possible .

firstly i calculated the maximum possible height for each obstacle such that i can reach the end .

then updated my values accordingly . can someone tell where can this greedy approach fail .

My submission — 321105467 ??

I had an alternate solution to B. I essentially cut the first opening bracket (always at first position) and last closing bracket (always at last position) and then checked if it was still balanced. It seemed easier to me that messing with the balanace factor arrays.

def isBalanced(s):
    st = []
    for i in range(len(s)):
        if s[i] == '(':
            st.append(s[i])
        else:
            if st and (st[-1] == '(' and s[i] == ')'):
                st.pop()
            else:
                return False
    return not st
 
for _ in range(int(input())):
    s = input()
    s = s[1:-1]
    #print(s)
    print("NO" if isBalanced(s) else "YES")

My initial idea in D was to binary search on the answer and run dijkstra(for each node, find max number of batteries you can end up with there) but that exceeds TL. But it seems like just bfs works: https://mirror.codeforces.com/contest/2110/submission/321128976

though it gets TL verdict after removing this line:

if(dist < d[u]) continue;

Cutting down on parallel entries seems to help a lot, but I don't think it makes up for the cases where each d[u] can be updated a lot of times. Can anyone prove the correctness of this or uphack it?

I don't understand why my solution for C is not working. Can anyone please help me out?

My Submission — 321200477

In problem C, I was able to write code to the determine whether the d array is possible or not, but couldn't do the build d array part. I saw some accepted submissions like #321209728 or 321058108. Either they choose greedily 0 as value for next d[i] or 1, it works. Why?

In the solution to problem B, the last condition is useless, since we only removed the first opening bracket and the last closing bracket, so the final $$$bal$$$ will not change and will still be 0. After the loop, we can print "NO" without additional checks.

In B I was just checking for the presence of ")(" , where does this logic fail?

Did my first contest on codeforces. Got a rating of +438 and idk if its good or bad. I did 2 problems under an hour with no wrong submissions. For reference, I'm 1440 in codechef and 1442 in leetcode.

Here is an enhanced version of the problem F.

How to solve D if this condition (si<ti) is not true?

My solution for B. Can it be hacked?

We have string S, and I am finding such strings A and B such that A + B == S, A and B are balanced bracket sequence. A is ending with ')', B is starting with '('. I am deleting the first char of B, and the last char of A. So, if I found such string A and B, answer will be "yes", else "no"

Why is this solution incorrect: https://mirror.codeforces.com/contest/2110/submission/321230391

Can anyone give me a test case where this fails?

what am I doing wrong in problem C? this is my intuition

I thought since we can only increase the height and can't decrease it later on, I will find the suffix minimum for the r[i] values from end to start, so in our current state we will know how much we can increase, so that later on we will be safe. So I will stick to the max possible answer at the current state, and hopefully this should satisfy the current l[i]; if it's not, then it's not possible.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<int> d(n), l(n), r(n);

        for (int i = 0; i < n; ++i) cin >> d[i];
        for (int i = 0; i < n; ++i) cin >> l[i] >> r[i];

        // Step 1: preprocess r[i] to be the minimum from i to end
        for (int i = n - 2; i >= 0; --i) {
            r[i] = min(r[i], r[i + 1]);
        }

        int h = 0;
        bool possible = true;
        vector<int> ans(n);

        for (int i = 0; i < n; ++i) {
            if (d[i] != -1) {
                h += d[i];
                if (h < l[i] || h > r[i]) {
                    possible = false;
                    break;
                }
                ans[i] = d[i];
            } else {
                // Try to take d[i] = 1 if it keeps h ≤ r[i]
                if (h + 1 <= r[i] && h + 1 >= l[i]) {
                    h += 1;
                    ans[i] = 1;
                }
                else if (h >= l[i] && h <= r[i]) {
                    ans[i] = 0;
                }
                else {
                    possible = false;
                    break;
                }
            }
        }

        if (!possible) {
            cout << -1 << '\n';
        } else {
            for (int i = 0; i < n; ++i)
                cout << ans[i] << " ";
            cout << '\n';
        }
    }

    return 0;
}

nice

Fashionable array can also be done without sorting, hence reducing the time taken to sort...

can C be solvable using dp? any idea how?

The first time I participated in a CF match, I failed in c because TLE with dfs

Can someone please tell why does this fail for C: Racing Submission : https://mirror.codeforces.com/contest/2110/submission/321334485.

Here i'm maintinig the maximum it can climb up for each i, and I'm taking the future d[i]'s into account. So test cases like these are passing :

1

4

-1 -1 -1 1

0 2

0 2

0 2

1 2

or

1

5

-1 -1 -1 1 1

0 1

0 2

0 3

0 3

0 3

For B i ended up counting the number of independent perfect bracket sequences that are in the string, for example: ()(()) -> has two '()' and '(())' and if we event encounter that such independent prefect bracket sequences are present then the ans would always be YES and otherwise NO. 321348376

As a tester, I have a proof that upvoting this comment will lead to positive delta. But the proof is too long to fit the margin.

No way I spent like 3 hours solving B problem. But eventually did it by myself.

Thank you for Editorial !

Can someone help me in fixing this? I've no clue why this won't work. I know that there is a simpler reduced version of the dijkstra based off the constraint $$$ u_i \lt v_i $$$ but I wanna know what's wrong here...

Submission

Need help

For Problem C(Racing), my solution says "wrong ans on test case: 2". I couldn't find my mistake. For which case scenario, my solution might not work properly? I am genuinely seeking help, please don't down-vote me.

Here is my submission: https://mirror.codeforces.com/contest/2110/submission/321800281