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)

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://codeforces.me/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. 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://codeforces.me/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?

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

Here is an enhanced version of the problem F.

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

Can anyone give me a test case where this fails?

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://codeforces.me/contest/2110/submission/321800281

it seems that I found an $$$O(n+m)$$$ dp solution for D?

first, for every node, find how many batteries we need at least to reach node n. second, for every node, find the minimum count of batteries we should use to reach current node, and the maximum count of batteries we can collect before we leave current node. using these info, we can know the final answer.

is it completely correct? my accepted submission

My solution to D that passed (and still passes) is brute force and can reach O(2^sqrt(M)) for a complete graph. 321117884

Anyone knows why this solution for problem B (Down with Brackets) works? I basically check if the entire sequence (i.e., String $$$S$$$) has at least two balanced sequences that are concatenated.

PLZ PLZ PLZ explain me where my code is failing in C(RACING) it is giving wrong ans on test 2 in test case 474 https://codeforces.me/contest/2110/submission/322820237 .. my logic is doing all -1 1 and store indexes in stack ( dont store those indexes where doind -1 into 1 is a necessity) and when h > r .. take the indexes of stack and make it 0 .. can u read the code and tell the failure test case please

how strong intuition needed to solve F

F is amazing! I can't see any of these three facts.

F is a really beautiful problem