first.

GuessForces

Thanks for problem B, quite an interesting idea!

I know number say otherwise(based on submissions)... but anyone felt D easier than C ?... I solved D under 40 minutes, but spent more than 90 minutes, in C :(

so B is just...brute force? uhhh man

problem B is awesome. problem G is genius. problem F is nice (though i have no idea how to come up with a solution for F1 which does not solve F2 by just adding some data structure). finally, sorry for being negative but... problem E..? it is so... obscure... the problem does not feel natural at all. i don't understand why in this problem the cost of a path is defined as it is. making it just the maximum edge on the path would make the problem just slightly easier (except if i don't see some obvious solution) but the problem would make soooo much more sense. and i would even call it a great problem. but the real problem statement just broke my brain.

P.S. also, expression $$$w_{\max_{i=1}^k e_i}$$$ does not make any sense because we can't use an edge as a subscript. it should be $$$w_{\textsf{argmax}_{i=1}^k e_i}$$$

Great problems.

During contest, I came up with a solution that is really hard to implement on F2, and finally completed it after contest.

is there any other solution for problem b

Upload codes

For B,I came up with a pretty interesting solution. We store all number in a map with key as the largest power of 2 which is smaller or equal to number. If one power has more than 2 values associated with it then answer will be just 2 of those 3 with same parity of remainder with the key, other a brute force solution will work because almost 64 elements can be there with no kay having more than 2 values by pigeon hole principal.

this contest was hard for me !

i fell a little too much, but for C i didnt understand why using the largest damage sword is not good for stage 1 ?

i mean if we use the greatest damage say z , and there are swords with x<z and y<z damage

then at the end after all the nonzero-c monsters are evaluated, we will have sword with either damage z or >z

and we will also be left with other n-1 swords in vector a

this is my submission 347754985

When did codeforces add visualizers? This is so useful! Will this be the standard going forward?

https://mirror.codeforces.com/assets/contests/2164/E_ooxathoosh9Oob4quoiv.html

Please anyone tell me why my code is not working on problem C

Admittedly, I had never heard of a reconstruction tree until several people mentioned it to me after the round. But during contest I came up with a solution to E that does not use KRT or anything of the sort; in fact, I believe there are several such solutions. So, for other people who aren't familiar with KRT, here is a quick sketch of my solution. (It's actually probably very similar or equivalent to the editorial solution behind the scenes, but framed without a reconstruction tree.)

Like in the editorial, it is clear that you need an Eulerian circuit, and it is known that one exists if and only if all vertices have even degree. So we will add virtual edges between the odd degree vertices, then take the sum of the weights of all of the original edges and virtual edges.

Let $$$G_i$$$ denote the graph that contains all of the vertices, and the first $$$i$$$ edges. Then if $$$u$$$ and $$$v$$$ belong to the same connected component as $$$i$$$ in $$$G_i$$$, it is clear that we may add a virtual edge between $$$u$$$ and $$$v$$$ which has weight $$$w_i$$$. Furthermore, it's easy to see that this is a complete characterization of virtual edges we can add.

We have this notion that somehow only "suffix mins" of $$$w$$$ seem to be relevant, because for $$$i \lt j$$$, we have that $$$G_i$$$ is a subgraph of $$$G_j$$$, so if $$$w_j$$$ is smaller than $$$w_i$$$, we would like to just use this instead of $$$w_i$$$. However, this isn't quite true, because it might be the case that we want to connect two vertices in a different connected component from $$$j$$$ in $$$G_j$$$. So we introduce the notion of "connected component suffix mins," which consist of edges such that no lighter edge later gets directly connected to its connected component. (It's okay if a lighter edge gets indirectly connected, since remember that we are only adding virtual edges of weight $$$w_i$$$ when looking at graph $$$G_i$$$, and the stuff that gets indirectly connected have labels less than $$$i$$$.) Now, it is easy to see that these are the only relevant edges, because all other virtual edges can be exchanged for one with the weight of a relevant edge. Furthermore, we retain the nice property of monotonicity of suffix mins; that is, if you fix a particular pair of vertices, at some point they end up in the same connected component, and from then on, its connected component's suffix min is monotonically increasing.

We can find all of the connected component suffix mins by merging them small-to-large while we add edges one by one in index order via DSU. In other words, for each connected component, maintain a set of its relevant edges. Then suppose we are adding edge $$$i=\{u, v\}$$$. We merge the sets of relevant edges for $$$\texttt{find}(u)$$$ and $$$\texttt{find}(v)$$$, delete all elements with larger weights than $$$w_i$$$ (because they're not suffix mins), and insert edge $$$i$$$.

Now, we create a second DSU, where we insert the edges one by one in index order, while also maintaining the number of odd degree vertices in each connected component. Whenever we add a relevant edge $$$i$$$, if its connected component has two or more odd degree vertices, we can pair them off until there is at most one, adding an edge of weight $$$w_i$$$ for each pair. By the monotonicity property, it is clear that this is optimal, thus concluding the solution.

In problem B, We just have to run a O(n^2) loop to check if there is a pair exist or not....(no need to check any other cases like 1 even / multiple even).....

Problem E

...

Now we have $$$f_i \le f_{f_{a_i}}$$$ which means it is optimal to pair up two vertex in the same subtree $$$p$$$ with cost $$$f_p$$$ as soon as possible.

MF what are $$$f_i$$$ and $$$f_{a_i}$$$?

I had no idea how to solve problem B without bruteforce. But after reading the editorial, I got goosebumps. It was nice and interesting problem

B was harder than C

As soon as I read the statement of C, I completely forgot that we only need to take max(c[i], x). I ended up spending 1.5 hours trying to solve an extended version of the problem where you only get a sword of strength c[i] after defeating the i-th monster. Totally wasted effort, lol. If anyone actually solved that “unwanted extended version,” I’d love to see your solution!

this was very difficult so so very difficult I have only do 1 problem

can anyone explain the problem H properly .

B is such a good question. I came up with the approach after 2 hours. I want to share my first solution which gave me TLE.

I came up with following conclusion, since we need $$$y\mod x$$$ to be even. Then $$$r=y-x*d$$$ which is remainder should be even. For that if we have 2 even numbers then it solves that case. But for odd case, I went like this:

• If $$$y$$$ and $$$x$$$ are both odd, then remainder to be even, the $$$d= \lfloor \frac{y}{x} \rfloor$$$ must also be odd.
• So now my task was to find the pair $$$x$$$, $$$y$$$ from the odd numbers such that $$$d= \lfloor \frac{y}{x} \rfloor$$$ is odd.
• I approached this as follow:

// odd is the list of all odd numbers
for (auto x: odd) {
    if (x == 1) continue;
    for (ll low = x; low <= odd.back(); low += 2 * x) {
        // What I am trying to do here, is for x
        // I am trying to enumerate x * k, for k = 1, 3, 5, 7...
        // Then for a number y to give the floor(y/x) as odd, it's range should be 
        // between [low, low + x - 1]
        ll high = low + x - 1; 
        auto [l, r] = find_l_r(low, high, odd);
        if (l == -1 || r == -1 || l > r) {
            continue;
        }
        int idx = l;
        if (odd[idx] == x) idx++;
        if (idx <= r) {
            cout << x << " " << odd[idx] << "\n";
            return;
        }
    }
}

• Here is my find_l_r function, this function is just finding the leftmost index $$$l$$$ such that $$$odd_l \gt = low$$$ and finding rightmost $$$r$$$ such that $$$odd_r \lt = high$$$:

auto find_l_r = [&](ll a, ll b, vector<int> &odd) -> pair<int, int> {
    int l = -1, r = -1;
    int low = 0, high = odd.size() - 1;
    while (low <= high) {
        int mid = (low + high) >> 1;
        if (odd[mid] >= a) {
            l = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    low = 0, high = odd.size() - 1;
    while (low <= high) {
        int mid = (low + high) >> 1;
        if (odd[mid] <= b) {
            r = mid; 
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return make_pair(l, r);
};

• The above approach is too naive and it will lead to TLE. I just wanted to optimize it. Does anyone have any idea how to optimize this?

lucky -138

can someone tell why my code is failing for C

347839121

At problem E ,should the graph we build be connected ? I mean the one which has all the odd nodes ? And also if someone could explain the solution a bit? I don't understand how we take the optimal edges.

In problem B, If there is no valid pair of x and y. Then why doesn't it give TLE as the time complexcity is O(n^2) ?

Problem H Part II proof 2 isn't making sense to me, does anyone understand it?

• What do "full circular string" and "Runs(l,r,p)" mean?
• Why isn't $$$S[l...l+p-1]$$$ a full circular string?
• What is an "extremely long cyclic palindromic substring"?
• What is a "loop point"?
• What is "the exponent of a Run"?

zjy2008

Just wanted to share that for problem F2 I used linked list with square root decomposition for inserting and querying specific locations. I had a pointer for every 1000th element so overall it worked in 500*N.

UPD: Tutorials for problem E and H are updated.

I think the updated editorial of H still has some problems.

• "$$$A$$$ and $$$B$$$ are palindromes, and $$$A$$$ is a prefix of $$$B$$$." Does it actually mean $$$B=AC$$$,where $$$A$$$ and $$$C$$$ are palindromes?

• What if the period doesn't occur at least twice,such as $$$BA$$$?In that case,the conclusions about run can't be used,and the effective palindrome pairs might be $$$O(n\log n)$$$,which means the total time complexity might be $$$O(n\log^2 n)$$$.I think one possible hack is $$$S[i]=\log(\text{lowbit}(i))$$$,which looks like abacabadabacaba....

guessforces

C is a great problem.

It tell me a database called multiset

Can anyone figure out why this https://mirror.codeforces.com/contest/2164/submission/349829120 is wrong for problem C

is there a way to see hidden testcases?

Problem E can be solved (I guess unintentionally) in $$$O(n \log^2(n))$$$ by sorting edges by weight, storing vertices in DSU and merging their edges (by smaller to larger), and then doing BFS over edges with smaller index than our current one. And cherry on top: using priority_queue instead of set.

349991751

C can be solved by repeat binary search right? O(nlogn) [edit: im dumb sry]

considering newbies like me please write solutions for problems like D in a more readable format omg T_T