Educational Round are the best for me, good luck for all participant <)(>.

Goodluck all participants <3

hope I become a specialist today !!!! :)

Can anyone guess what the rating range problem C would be??

Hope problems are less Ad-hoc and more algorithmic this time :/

Always love educational round.

I can not thank you guys enough. Thankyou so much for your efforts.

Educational rounds seems brainstroming to me. Does this happens to others also? But, Happy to attend these contest thinking one day these hard problems would be easy for me. Best of luck guyzz.

For the love of back to back rounds. <3

Hope that I will not mess everything up again.

Thank you for the contest

If the score is more than 2100, why do people with a score of more than 2100 participate in the ranking

Probably one of the best question sets I've seen this entire year!! However, I made one typo in question C which costed me 20 more minutes and 4 penalty attempts :(

Probably one of the best question sets this year!! However, I made a typo on question C which costed 20 minutes and 4 penalty attempts :(

Only solved A-C again :(

Maybe I should have a rest……

Educational speedingforces

Dude, really 6500+ people solved C?

Speedforces

What was the approach for D? Weren't we supposed to multiply the number by its biggest digit each time or I am wrong?

What's the proof for C???

I think today's contest was easy as compared to normal Div2 rounds

I spent 30 minutes thinking that C could be solved greedily, then I said let me just try to perform the K swaps no matter what, and it passed LOL

What was the idea behind E and F?

God damn it! So everyone knew how to solve F except me. I lost my chance to became Master.I'm so sad now....................

Can anyone hack me? Unordered map Your text to link here...

How to solve F?

What's the intuition behind D??

In task D, How to know that memorization in a map will not exceed time limit?

Trash E.

It only takes me 5 minutes to manage out a way to solve it using something like Matrix multiplication and Segment Tree or binary lifting.

But there are TOO MANY GOD DAMN DETAILS that I failed to accept it before the contest ends.

I hope there will be more brain-consuming problems (maybe greedy or constructive ? ) instead of such complex and meaningless ones.

I use DFS to solve problem-D, but get TLE. :D

158223688

Can someone share the approach for problem F ,how to solve it using disjoint sets

Why are there orange people in the official standing?

Can we solve F using smaller to larger technique ?

What a bullshit D.

First time solved 4 problems in div 2

What the meaning of D? I can't imagine the reason to put a rubbish standard dfs in the place of D.

Is it so hard for you to simply delete this problem? I can come up with hundreds of problems like this.

And for the difficulty, many people can't solve it just because they aren't dare to use such a stupid method in fourth problem. Why not put it in the place of A?

Kind of sad that $$$O(N (\log{N})^2)$$$ approaches passed in F.

I initially had an interesting $$$O(N^2 \log{N})$$$ solution where I run a re-rooting DP on each edge weight separately, to calculate contributions of that edge weight (a range sum data structure was used for this, thus the log factor). I sped this to $$$O(N \log{N})$$$ by using the DFS times for each node and simulating the DFSs for each edge weight by just looping along occurrences of each edge weight in the DFS order, using only $$$O(\text{occ}(x) \log{N})$$$ for each weight $$$x$$$, where $$$\text{occ}(x)$$$ is the number of occurrences of $$$x$$$.

Edit to add:

Since people seem confused, I will explain my solution in some more detail. Firstly the $$$O(N^2 \log{N})$$$ idea. First root the tree arbitrarily. Now, we find the contribution for each edge weight separately. I will describe how to calculate the contribution of edge with weight $$$x$$$.

Notation:

$$$\text{comp}(u, x)$$$ is the size of connected component of if only edges with weight not equal to $$$x$$$ are considered, $$$\text{sz}(u)$$$ is the size of subtree of $$$u$$$, $$$\text{par}(u)$$$ is the parent of node $$$u$$$, $$$\text{anc}(u)$$$ is the set of proper ancestors of $$$u$$$, $$$\text{sub}(u)$$$ is the set of nodes in subtree of $$$u$$$.

Define $$$\text{dp1}[u] = \text{comp}(u, x)$$$ if the parent edge of $$$u$$$ has weight $$$x$$$ and $$$0$$$ otherwise. Similarly, define $$$\text{dp2}[u] = \text{comp}(\text{par}(u), x)$$$ if the parent edge of $$$u$$$ has weight $$$x$$$ and $$$0$$$ otherwise.

How to compute $$$\text{dp1}[u]$$$? Some careful thought yields:

and

With these expressions, $$$\text{dp1}[u]$$$ can simply be computed with DFS and a range sum data structure (on the Euler tour of the tree). After computing all values of $$$\text{dp1}$$$, the $$$\text{dp2}$$$ values can be computed with DFS and a range sum data structure, noting that $$$dp2$$$ value of a node $$$u$$$ will be used when $$$u$$$ is an ancestor and $$$dp1$$$ otherwise. So, these values can be switched in the range sum data structure during DFS.

Contribution of weight $$$x$$$ is simply $$$\sum \text{dp1}[u] \cdot \text{dp2}[u]$$$.

How to make this $$$O(N \log{N})$$$? Well, since only particular $$$dp$$$ values are ever non-zero for a weight $$$x$$$, we can simulate the entire process by just looping over the positions of these nodes in the DFS order.

Code: 158206764

Problem D was so frustrating. Still can't figure out why DFS would work?

Also, can anyone point out what is the issue with the idea of always multiplying with the largest digit in X? This should give the largest possible number in some number of moves, right?

158229061 what should I add for this D problem submission so it will work? Or at least give TLE..

The contest is nice but there are plz skip them ... bcz problems A B and C are in Youtube !

I think I solved E during contest but was lazy to implement (though might TLE in theory). Tell me what you think.

I looked at the doors as a layered graph. Each layer has 2 nodes (doors), and there are only edges between nodes of adjacent layers (the distance in the matrix between the doors of consecutive layers). So in total there are 4 edges between 2 layers.

Now for the preprocessing, I want to calculate the distance between the doors of special layers (0 with 300, 300 with 600, 600 with 900). I'm using 300 but actually I would take sqrt(10**5).

This is a simple DP such that in the end each node in each layer has a pair (d1,d2), where d1 is the distance from the first node (corresponding to top door) in the previous special layer, and d2 is the distance from the second node (corr. to right door) in the previous special layer.

Observe there is never any need to travel back and forth between layers. Only one direction.

So now, assume I get a query (x1,y1), (x2,y2). Suppose the first is in layer i, and the second in layer j. All I need is to calculate the distance from x1,y1 to both doors in layer i, then. Then use my preprocessing to calculate the distance from doors of layer i to both doors of layer j (4 distances), and then calculate the distance from both doors of layer j to (x2,y2).

This could take up to 900 operations per query (300 for layer i to special naively, 300 for special to special using preprocessing, and 300 for special to j naively). But notice that if you do the preprocessing in both directions, this can be done in 302 operations per query (the distance to the next/previous special layer can be done in one operation).

Of course this isn't really 302, but more like 302 * 4? (because every calculation I consider 2-4 different options?). So it might be TLE, but it might just work. I'll probably try to implement later and see ^_^

Is it possible to solve $$$F$$$ using centroid decomposition? I tried to write it, but couldn't do it in time and don't know, will it work.

Also, has anyone noticed, that during contest "cses.fi" went down? I only loaded my submission there for a centroid decomposition problem, and after several minutes the site stopped working.

I can't control myself to complain the weak pretests of problem D. A way to express this feeling is to hack myself :(

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

• A: Game with Cards
• B: Card Trick
• C: Double Sort
• D: Required Length
• E: [Labyrinth Adventures: Under maintenance
• F: Unique Occurrences

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

please try to hack this one , my solution is already hacked , i just want to confirm whether my new solution is correct or not. link-158229941 thanks in advance.

For D why a DFS with memoization works? From any starting number x you just multiply it with {2, ..., 9}, and there are only 4 prime numbers in that set: 2, 3, 5, 7.

That means you actually just multiply x with those four prime numbers and in the worst case you start from 1 and use 64 multiplications with 2. But some of those 64 multiplications can be 3, 5, 7 as well. So that is really at most 64^4 (imagine you divide 64 positions into four segments for 2, 3, 5, 7). The real number will be much smaller because for 3, 5, 7 you probably don't need 64 multiplications.

SpeedForces, in two consecutive days QAQ SPEED IS NOT MY FORTE It's shocking that a D problem can be solve by brute force?? I'm trying to do recursion or dp, without even thinking that this problem can be sooooo easy! and I am sad that I mistake $$$bj$$$ to $$$bj_{th}$$$ in problem B.

and I am sad that because my func for sort() returns false when two elements are equal, I received 3 Runtime Error..

My only bug on E was forgetting to initialized my binary lifting array with INF...easily the stupidest bug I've made out of not solving one of the hardest problems in a contest

I also find it kind of funny that samples didn't even catch this bug

I solved problem D using recursion + memoization. only prime numbers which will be multiplied by x are only 2,3,5 and 7 and each prime number occurrence will not be more than 60,40,24,28 respectively. so we can memoize the count of each prime number.