Hello Codeforces!
On Mar/22/2022 17:45 (Moscow time) Educational Codeforces Round 125 (Rated for Div. 2) will start.
Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.
This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.
You will be given 6 or 7 problems and 2 hours to solve them.
The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.
Good luck to all the participants!
UPD: Editorial is out.
Best of luck
Good luck to everyone !
Hope to be specialist after this round
gl
Bruh !! Why after even commenting, you didn't participate. Believe me you would have easily made it to the specialist!. Anyway next round is coming soon. All the Best , don't afraid , just believe in yourself. I am saying this because i was also in your situation a while ago. But Now i am a solid specialist trying for expert... got a +99 delta too in today's round just +100 points away.
For sorry I get late in colleage and went to the nearest place after 30 minutes of the begining of contest and solve three questions in 30 minutes but with another account, I am sad but i will go up next time isa thanks for advice.
How to prove A?
If (x , y) = (0 , 0) then answer will be 0 because he needn't move Else Sqrt (x * x + y * y) if it is integer then answer will be one Else Answer is 2 and two operations will be Go to (x , 0) from (0 , 0) and sqrt( x * x + 0 * 0) = x is integer Go from (x, 0) to (x, y) and Sqrt ( (x -x)* (x * x) + y * y) = y and also integer
Hope to become CM tonight :> Good luck for everybody!
CM in VNOI + CF is great :>
I love that :>
congrats!!!
thank you
Congratulations on becoming CM
Congratulations! I am so happy for you.
Congratulations bro :-)
thanks, bro
Hope for the best, but prepare for the worst.
Good luck guys!
Hope my rating's downward trend turns around in this contest.
I hope there won't be too much fst in this contest :-)
in a div.1 contest
ooooooof
Harder than AK
Good luck everyone! One day I will be a pupil.
Best of luck to everyone
Hope I will become grandmaster in today's contest
Confident man, I'm sure you'll be the Legendary Grandmaster after tonight's contest.
Sobs.. Finally someone recognized my talent
good luck to everyone this turn!
I am less confident in giving first contest just after getting promoted , it been a while since I get back to specialist . How to deal with this ?
Believe in yourself. Even if you are demoted to pupil after this contest, there are chances in the upcoming contests to be promoted again. If you deserve to be a specialist, you will remain a specialist.
Take it easy and don't start to panick or get upset if everything is not going well. At the end, it's just a title, skills are more important than titles. And right, if you deserve this title, you'll keep it or achieve it soon later on, if you fail today. Wish you good luck!
Thanks a lot mahirlabibdihan and M_bolshakov for boosting my confidence . And yeah I have seen progress and sooner or later I will achieve it if I fail today .
i became a specialist in dec 2020 and still a specialist
I can definitely see the progress , there is lot of difference when the first time you become specialist and now . You are expert now and Yeah I got your point . Your badge doesnot show your skill set .
Yes, good luck mate
Take a look at this post. It talks about the fear of rating loss and shows it's no big deal.
Thanks for the post Deepesson ,that is exactly what I am facing and now after reading it ,I think I can handle it .
Good luck everyone!
Why 10 minutes delay?
Yea, I ate so fast in my mess to give contest, only to realize contest is 10 minutes delayed
In my campus ,we skip dinner in mess to give contest as mess is open from 8 to 10 pm (IST)
Bruh
.
Nice
ate rice instead of puri sabzi uff...
Why many people on codeforces are so demotivating? I see many posts with too many downvotes even though it does not deserves downvote
This post downvotes counts such stupid people
why the start time became 10 minutes later?
Probably technical issues. Codeforces was really slow for me 5 minutes ago.
ya i am experiencing same problem
Good luck everybody!!!!!!!!!!!!
delayforces REEEE
10 minutes delay
I Hope to become Pupil,today.
All the best :)
It is taking some time to load a page, same to you?
You can use mirror. I use it, when sending A, because very slow loading.
set easy questions from next time
noted
Struggling to solve A.
What a contest.
A,B,C Done! Good Night Everyone!
2 consecutive speedforces contests :(
speeeeeeeeeeeed forces!!!! :(
How to solve D.
Is F 2-SAT on edges with implications for every consecutive pair in some path, with LCA to find the actual paths?
Pretty much, but LCA is not needed since the sum of path lengths is O(N).
right, parent, entry and exit times from a dfs are enough for find path in O(|path|)
What was the intended solution for D? Surely it wasn't sqrt decomp with log factor?
Mine was harmonic-like where we notice that units and monsters are basically h * d, group units by cost, and loop over all possible number q of units of each cost (works fast coz sum of C/i for i <= C is O(C log C)); then for each q binary search for max monster that we can kill and compute suffix minimums of costs
Ah that's a lot lot smarter than what I did XD
Can you please explain how that is fast enough in bit more detail
$$$1/1 + 1/2 + ... + 1/n \approx \log n$$$, also known as the harmonic series.
I used a differentiate array storing for each cost c, the max monster H * D we can kill.
Mine was finding all dividers of all numbers <=C (complexity C/1 + C/2 + .... + C/C,)and then doing dp for every k<=C finding the biggest possible h*d, if h is monster's health, d is damage it makes:
if we did from 1 to k-1, for k: for each dividor x of k we calculate biggest answer with x = cost of 1 warrior. And take the maximum of it and answer to k-1.
I did this because it is also enough to calculate dp
DP
We want to select our troops such that
(health / my_damage) < (my_health / damage)
. (Here my_damage is sum of damages).Thus we can compute a dp array where
dp[i] = max value of my_health * my_damage if there are i coins
.You can view my submission here 150514511
By the way, instead of implementing binary search yourself, you can use this:
(See my repaired submission: 150532032)
There is a solution with parallel binary search. Essentially binary search on $$$C^\ast_j$$$ for each monster $$$j$$$, the minimum coins needed to kill them.
If $$$i$$$ kills $$$j$$$ then it must be that $$$H_jD_j < h_i d_i \lfloor \frac{C}{c_i} \rfloor$$$. So you binary search in the range $$$[l,r]=[0,C]$$$. Then consider $$$mid$$$. You calculate $$$g=\max_i h_id_i \lfloor \frac{mid}{c_i} \rfloor$$$. Then you partition the monsters, those with $$$H_jD_j < g$$$ and those with $$$\geq g$$$. For those with $$$<g$$$, you recurse on them in interval $$$[l, mid]$$$ and those with $$$>g$$$ you recurse on them in interval $$$[mid, r]$$$. You stop when $$$l=r$$$. Total work would be $$$O(n\log C)$$$
Here is the submission with the implementation of parallel binary search btw: https://codeforces.me/contest/1657/submission/150555751
Is D supposed to be solved with parallel binary search? I came up with an $$$O(n log C)$$$ in the last 10 minutes but couldn't implement it even if my life depended on it.
Guys, can someone clear this up for me? I got TLs in C problem on GNU C++20 (64), but the same code passed all testcases on GNU C++17...
150525251 — Accepted (GNU C++17)
150522050 — TL on 4'th test (GNU C++20 (64))
The complexity of erase is $$$O(n)$$$.
Oh, okay, thanks
Can anyone tell why my solution for problem C is giving TLE on test 5 ? My Solution
Your code's time complexity is o(n^2),where as given string size has limit upto 10^5. So expectime time complexity becomes o(nlogn).That's why it gives you tle
I made two submissions for D and the first submission appears in the standings currently. What happens if the first one FSTs? will the second submission be used?
How to solve the 4th (D) question?
This one you can apply similar technique to prime Sieve. presumably, d, h is the type you select and D, H is that of monster, if you select n unit then this is true n*d*h > D*H. it's easy to see that d,h individually doen't matter, what matter is d*h.
C is at most 10^6, so what if we calculate the maximum d*h we can get for each cost from 1 to 10^6. Turns out this can be precompute similar to Sieve, and the complexity is cheap.
From there just binary search for each monster to see what's the cheapest cost such that the max d*h you get at cost ith is larger than D*H of monster
I think I get it.
The precomputation of the sieve is fast because there can be only one useful unit (the one with the largest d*h) for each cost c and so you need at most C/1 + C/2 + C/3 + ... + C/C computations which is O(ClogC) (harmonic series). (the unit with c=1 (if there is one) loops C/1 times, the one with c=2 C/2 times and so on)
Very sad is that I got the idea and confused somewhere in implementation during contest :')
Thank you for the explanation. I managed to implement the approach you described 150560762. Correct me if I am wrong, but the maxDH array (where the c'th slot stores the maximum d*h that c coins can get) that results from the prime sieve precomputation will have unvisited slots in some cases. So there is a need to do a pairwise max on this maxDH array from slot 2 to 1000000.
Also, I had to store units information in units where the c'th slot of units stores the (d,h) all units with the cost per troop c.
Yeah, it is necessary to do a 'prefix max' postprocessing of the maxDH array to make sure it is monotonic so that binary search can be applied.
D was based on?
any hint for E?
DP. The given condition can be rephrased as: for any two vertices X and Y other than 1, the weight of edge X -> Y should be no lesser than the weight of edge 1 -> X and 1 -> Y. We have N — 1 edges starting from vertex 1 which could form (N — 1) * (N — 2) / 2 groups. So, DP from weight 1 to K, dp[i][j] means, when we have assigned weights to j edges from vertex 1 and the max weight of them is i, how many choices we have. The transistion is:
dp[i][j] = sum(dp[i — 1][l] * C(N — 1 — j, l — j) * power(K + 1 — i, j * (l — j) + (l — j — 1) * (l — j — 2) / 2) for all l < j which means, select l — j edges from N — 1 — j edges and assign them with weight i. combining them we have j * (l — j) + (l — j — 1) * (l — j — 2) / 2 groups of edges, weight of each group should be in [i, K]. The final answer is dp[K][N — 1]. https://codeforces.me/contest/1657/submission/150515462
Maybe there is something wrong with your text explanation, but your code is absolutely right. I think text explanation should be fixed as below.
dp[i][l] = sum(dp[i — 1][j] * C(N — 1 — j, l — j) * power(K + 1 — i, j * (l — j) + (l — j) * (l — j — 1) / 2) for all j < l which means, select l — j edges from N — 1 — j edges and assign them with weight i.
We have chosen j points (called Vertex Set A) to connect to point 1 before and choose l — j points (called Vertex Set B) this time. Edges between points from A and points from B, as well as edges between two points inside B, should be no lesser than i. That is so called j * (l — j) + (l — j) * (l — j — 1) / 2).
Thanks for your correction.
What do you mean by (N — 1) * (N — 2) / 2 groups? What are groups?
Ah, I got it, sorry, but I did not get why did you do j * (l — j).
Can anyone please explain me the logic of today's A particularly when the ans is 2. How can we prove it that if the ans is not 0 or 1 it must be 2?
You can draw 2 circles, one centered at (0, 0), the other centered at (x, y) such that they intersect and do 2 jumps (0, 0) -> intersection -> (x, y).
Travel parallel to x-axis first to reach the x coordinate and then travel parallel to y-axis or vice-versa to reach the final destination. This way it can be done in at max 2 moves
Cool, I'm wondering if there were other people like me who did DP, after they weren't able to prove it after few minutes
If we can't reach (x,y) in 1 or 2 move then we will first make move such that the x coordinate becomes equal to X coordinate of target(as y coordinate will be same so it will be valid) and in next move we will make y coordinate equal to Y coordinate of target (it will also valid as x coordinate will be same).So in minimum moves we can reach (x,y)
It's crazy I used string hash on problem C.
I almost decided to use Manacher's algorithm before I realized that the first time a character re-appears, it must be a palindrome.
x2, but realized it wasn't needed seconds before actually using it
Not worse than using DP in A. That's what i did :(
Thanks for having the 0 0 test case in the sample for problem A.
XD
Why did $$$O(nc)$$$ pass QD pretests... Doing $$$n = 30000$$$, $$$C = 1000000$$$, $$$c_i = 1$$$, $$$d_i = 1$$$, $$$h_i = 1$$$ easily fails $$$O(nc)$$$...
How did you do O(nc)?
It's technically $$$O(n(C/c))$$$... I guess that's why
Although I admit that I'm just stupid that I didn't see this coming, this is (I think) one of the key elements to the solution, and letting that pass (with 1/10 runtime as well) is just... idk
Take the maximum of $$$d \times h$$$ for every $$$c$$$ first, then start processing using a Sieve-like approach
This should be $$$O(n + C log C)$$$
why did you use O(nC) but ?and your o(nc) runs in 358 ms how is that possible
that's what happypotato said, why did it pass pretests...
anyway I believe we can expect numerous FSTs
Education round does not have system test. Only hack.
They will run all hacked tests again after the open hacking phase.
And then you FSTed oof :D
Is there a better way to solve A other than brute force and dp for all 50*50 square from 0,0? Doing a bfs + dp for all test cases for A seem overkill.
0 , 0 -> 0, integer distance -> 1, other -> 2, because you can always go (0,0) -> (x, 0) -> (x, y)
Wow, that's so simple. I'm retarded today.
0,0 -- a, 0 -- a, b
maximum answer can be 2 if a*a + b*b is not a perfect square because you can go from 0 to x and x,0 to x,y, else ans is 1 or if both x and y are 0 answer if 0
Store all squares till 100^2 in a set. After that simply check if (x*x+y*y) is in the set. If it is in the set answer is 1 else answer is 2 .
One edges case you'll have to handle is 0 0
same on bfs(dp) + brute force :)
i got AC on problem A when almost 7k people have passed A. my bad observation skill :(
Please Tell me randomization will pass F '~'
Only insanity can help you pass F
Actually, once you notice that you need to do some checks and then propagate those checks the only problem is the dependency cycles. and as you can notice it's impossible to make a test with a lot of dependencies without decreasing the number of strings.
So trying some shuffles is good enough to pass this problem.
I went with a more naïve and straightforward approach for the dependencies, more of a constructive algorithm. Honestly I'm not familiar with how randomisation or shuffling works.
Memory limit exceeded on test 169 ^_^.......
I think you have used an array of size N * 26 for 26 characters at each vertex of the tree. I did the same mistake and got MLE on test 169. If you notice, then there will be almost $$$O(\sum{|s_i|})$$$ values required out of N * 26 values which easily gets AC.
Oh, I see. Yes, I did exactly the same mistake on problem F. Thank you, I will fix the mistake :)
I can't believe I tried to solve a problem using hashing in a contest two times in a row!
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 to increase/decrease the constraints.
If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.
Why my D question got hacked in this round, can anyone help me https://codeforces.me/contest/1657/submission/150523841
You are using too much memory. In v and pow vector you are using O(C*n) space in worst case.
Someone asked me in a private message how to solve 1657C - Bracket Sequence Deletion.
Don't write private messages, just ask below the contest announcement (or editorial if there is one). There is a greater chance someone will answer and more people can benefit from such an answer.
Despite that, here my attempt at a newbie guide for overthinking 1657C - Bracket Sequence Deletion:
In this problem the difficulty may be that you have to pay attention to two different rules at the same time. If you notice that your thinking bounces between both rules, you have to force yourself to first pick one and ignore the other.
How do we find the shortest prefix that is a regular bracket sequence? Every bracket that was opened must be closed. There may not be a closing bracket if there was not an opening bracket before. So a valid sequence has to start with an opening bracket. Use a counter, add 1 for every
(
and subtract 1 for every)
. When the counter reaches 0 for the first time after starting, this is the shortest possible regular bracket sequence.Now we pay attention to the second rule: we want to find a palindrome. When dealing with brackets as palindromes it can be useful to think of
(
as 'open' oro
and to think of)
as 'closed' orc
. If you're not used to it()
looks like it can be mirrored and)((()
looks weird. But if you think about them asoc
andcoooc
it's easier to see that the first one can not be mirrored but the second one can be.We could easily check substring $$$s_1s_2...s_k$$$ in $$$\mathcal{O}(k)$$$. It would be nice if we could reuse that check and extend it in $$$\mathcal{O}(1)$$$ to also check $$$s_1s_2...s_ks_{k+1}$$$ for a total complexity of $$$\mathcal{O}(n)$$$. But I don't know how to do that and checking every prefix independently would result in $$$\mathcal{O}(n^2)$$$.
If you're not sure how to solve a problem or you are stuck with your approach so far, it can be a good idea to play around with short or small potential inputs.
((
(oo
) -> palindrome, done, cut and continue with remaining string))
(cc
) -> palindrome, done, cut and continue with remaining string()
(oc
) -> not a palindrome, maybe it's the start of one)(
(co
) -> not a palindrome, maybe it's the start of oneDid you notice it?
()
is already the shortest possible regular sequence so we're also done, can cut and continue with the remaining string.While we're at it... any longer possible regular sequence must start with
((
but that's already a valid palindrome... so we can forget about regular bracket sequences completely and if our current prefix is((
,()
or))
we can continue with the remaining string.That leaves only prefixes starting with
)(
(co
) that could be palindromes. What if there's another(
?)((
,)(((
,)((((
... (coo
,cooo
,coooo
...) — none of those is a palindrome. What happens if we ad a ')'?)()
(coc
) is one! and it also works for all other variants we just thought about:)(()
,)((()
,)(((()
... (cooc
,coooc
,cooooc
...)In summary: Just look at the first two characters. If they are
((
,))
or()
, cut and continue with the remaining string, if it's)(
search for the next)
after that and cut or if there is none you can't do another cut.Applied the same approach, still my solution got hacked link. Can someone look at it? Thanks in Advance.
I guess your
s = s.substr(x);
is the problem. For a string like()()()()()[...]
this results in a total runtime of $$$\mathcal{O}(n^2)$$$.Educate by FST.
Solving A B C can give you a rank of 700 as well as 6500
Yeah so?
Don't you think thats too much sensitive to speed?
Bruh, that's how competitive programming works smh
No, thats because there is a huge difficulty gap between C and D. Usually that is referred to as "Speedforces".
isn't that the part of cp because we cannot expect the rounds to be well balanced always.
Can any one help me out with D...Why is this giving Tle??? 150579927
Think about the case where C=10^6 and n=10^5 with each ci=1 i.e. all the units have cost 1. In this case your Code complexity become $$$O(nC) $$$
yea got it..thanks
Just curious, but I have finished this competition (this is my first ever CodeForces competition). However, apparently, as of 12:13 A.M. (UTC -7), 23 March 2023, I am still unrated. Is this supposed to be a problem? Thanks.
check it again. It's updated now.
My CM dream come true :>.
Thanks BledDest, Neon, adedalic, awoo and vovuh.
Same
+1
in problem D is monster attacking all units with D[i] or his damage dividing between all units?
The monster attack one unit.
And when one of our units was killed, we lose
thanks
https://cfstress.com/status/2406
can you explane me this?
You know when we win??
We win when d1 * h1 > d2 * h2 (d1, h1 is our unit; d2 , h2 is monster)
When we buy x unit of one type, our d1 become d1 * x, our h1 doesn't change (because we lose when 1 unit die).
In this test case:
The monster's power is d2 * h2 = 5 * 6 = 30
If we buy one unit of the second type we have 2 * 8 = 16 => we lost
If we buy five units of the third type, we have 5 * 3 * 20 = 30 => draw
But we have to win the monster, so we have to buy one unit of the first type, or six units of the third type.
Can you help me as well? Thanks
You can wait for the editoral of this contest =))
In D, I used the thing that for each type of squad unit. The min number of troops hence the minimum cost required will be,
I calculated this for each type of troop and printed minimum amongst them. However this logic fails for some very high input (wrong answer 36373rd numbers differ — expected: '802914', found: '808376')
Can anyone help me out, What am I missing?
Here is submission, https://codeforces.me/contest/1657/submission/150576954
May be because u use the float, u should use the ll
Thank you so much, You really helped me. Yes You were right, Now Giving TLE for test 9 instead of WA on test 6. I will wait for editorial now.
i used the same idea and got same verdict
Problem E can be solved in $$$O(kn\log{n})$$$. This solution works in 0.5s for test
1000 1000
(or even about 0.3s if ran under 64 bit сompiler).Also, fun fact. In this comment the word "сompiler" has cyrillic с. It is because if I write the word "compiler" properly, mathjax fails to render the formula. If I misspell anything in this word, everything works fine.
Why is the E time limit at 6 seconds? Is it to let n^2 k^2 solutions pass (they did)? It's an insanely long time especially when most solutions are < 1s.
It's to let $$$O(n^2 k \log n)$$$ pass (my implementation of it is about 1.4s on the maximum test).
I've learned so many.
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).