Hello Codeforces!
The series of Educational Rounds continues thanks to the support of the Neapolis University Pafos.
On Jul/30/2024 17:35 (Moscow time) Educational Codeforces Round 168 (Rated for Div. 2) will start.
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, 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
My planned post contest discussion stream
as a cyan (specialist) participant I hope to reach blue (expert) after this contest
update: I failed T_T
will try again
Good luck to you and me. Good luck to everyone
Good luck!
wu
I've made it! :D
hopefully specialist after this one, good luck everyone
Good luck for becoming specialist
I wish the same. Good luck dude.
good luck to everyone :)
Educational Rounds always make sure participants learn something new every time. Good Luck Everyone !!
What is so educational about them? They don't seem so different from normal div. 2 rounds.
From my experience, educational rounds have more straightforward problems that use a single kind of well-known technique which is supposed to be learnt by the participants during the contest.
exactly
Hoping to cross the 1300 barrier after this contest. Wishing luck to everyone!
Good Luck everyone. May this contest give you a minimum of +100!!
Tough, but thank you
Wow that's a wonderful delta isn't it
yeah!!
Hoping to reach blue in this contest, good luck to everyone!
potato
I am close to green, So I hope today I may reach it again, and best of luck to each participant !
Me too. (I only need 7 to reach green) Good luck to you, me, and everyone!
Wait, no testers ?!
as specialist i hope to reach expert after this contest
That's a really big jump though considering you are 1446
i know but like i said "i hope"
Btw did you just begin cp or it's a new account/you were doing on other platforms? Because specialist in so less contests is amazing!
I just hope the pending can be faster.Why pending is often slow?
Started to do CP recently, I am finding it hard to select the which technique should be used for each problem and finding it is a big task any ideas and tips to improve the learning and improving
I don't have much experience, but I can say that only practice helps. It can be useful to review the problems and solutions of past competitions (but at the level you feel you can understand at the moment). My mistake was that I analyzed the solutions of the more difficult problems, although I could not solve the easier ones on my own. So I recommend solving gradually, it is better to solve an easier problem yourself than to understand or remember the solution of a harder one
Also at your level I recommend to pay more attention to past div 3 and div 4 contests, usually problems there easier than div 2
thanks for the insight I have been working on it and most of the times I do make the mistake of analysing past problems but some times I can get the most optimal intuition but unable to convert the logic to code
Hope to reach grey.
I have faith in you :)
Hope to reach cyan today
Cheat from youtube
Do
A,B and Cin $$$1.5$$$ hrsI prefer hard way :)
Congrations you are cyan now.
Thanks)
also D
Yeah, that was a good contest for me, I managed to do ABCD. Hope it won't get hacked
Guys the waiting queue is really long(my last submission has already waited for 30 mins),will it be all right before the contest?
Let me go back to Expert,CodeForces!
Hope to reach....... Realising NO HOPE LEFT
Only 20 points :)
manifesting to reach blue today fingers crossed
My first unrated Div. 2
You are lucky to get it unrated.
Really hoping to learn more. Always been told I couldnt do cp
the worst round ever. 4 update messages in 20 minutes.
You updated your comment 3 times.
I haven't changed anything. only when the fourth came
What I'll miss is that in the first 20-30 minutes there were four updates to problem B's condition, but problem D is a nightmare. The problem writer has 0 creativity. It’s like I’m reading a study problem>. Worst round
problem B seems much harder before updates
i mean, there should be no updates. the testers should fix this before the round
I agree that it is pretty classical but this is an Educational round.
If problem D has 0 creativity , why you donot solve it
there is no connection here. the problem may not be creative, even if I haven’t solved it
I agree, I solved it and it is not creative at all.
speedforces :'(
because of people like you, who copy paste ABCD as soon as they get them from telegram.
Y are a cheatforces
ok so my code that used a Node class and new() TLEs but it runs in 50ms with n=200k on my system.
when i get rid of the Node class and use ints it runs slightly faster on my end but AC
whats the big deal with new() taking forever???
Use global variables, they are faster. Preallocate memory, rather than allocating runtime memory for better performance.
There are disadvantages also, you need to make sure, you are not allocating more than required, or you will get MLE.
12k did C? lol.
so true lmao
more people solved C than B, despite B having a way easier algorithm
Guess what, aryanc403 bhai has tried C-problem 4 times. He is quite experienced and knows most of the things in CP. If it takes him 4 tries then the problem must be little challenging. and yet 12k people solved it.
Definitely C is leaked. xD .
Even D is leaked. In last 10 min D submissions increased from 3k to 5k. Looking weird:(
C was quite easy as per aryanc403 he may have bad day
I have seen the intended solution.
I'm sure I will miss it, irrespective of what day it is and what time it is.
Not the kind of problem I'm good at.
C was easy compared with other Div 2s.
Exactly i was unable to solve B but did C in less than 10 minute, also got idea to solve D but was not able to write code :(
tbh if you figured out only condition where one region becomes 3 it was easiest to implement check out my submission for more details
Actually the problem was I didn't read the constraint properly which was stating, initially there will be at most 1 region.
ohh I was getting notifications again n again so I carefully read the problem
c was literally valid parenthesis from leetcode. It is one of the foundational problems for stacks. I think 12k submission is not justified. But it should be higher than usual div2 c. I solved it using rust as I am learning it.
C is not just valid parenthesis lol
I just built a valid parenthesis and summed it up and got accepted. What is so hard about it ? And the cheaters gonna get skipped anyway. So I don't think it doesn't matter.
well, u just answered to urself. You didn't prove why it will be minimum cost, and just guessed.
I think we have to close the open bracket as soon as possible then only we can get minimum cost.
Bro can you prove why there exists only one solution.
It wasn't valid parenthesis problem, this problem's solution had some objective (greedy) and constraints, which is totally diff.
Yes it was, you just need to observer when the cost is minimum and fill the blanks accordingly.
agree, such cheater ruined codeforces
is this rated for GMs , LGMs, IMs??
no, only for people with rating less than 2100
then why are they in official standings ?
They are, but after system testing you will be able to see the standings for Div. 1 and Div. 2 separately.
ohh cool :)
no bro, only till 2099
Ok thx
WTF ????????????? HOW NEWBIES AND PUPILS WITH < 150 PROBLEMS SOLVED ARE SOLVING D ????
5000 ACCEPTED ON D IN A DIV2 ROUND IS JUST INSANE.
Because it is very easy and classical, however I won't deny the presence of cheaters.
its standard problem, cheaters are there tho
can you tell me about that standard problem
i mean say we are on node v with value a[v] and the smallest element from every subtree of v is mn, and then a bit of case handling, if (mn<= a[v]) we go on with mn as the minimum value for the subtree that includes v , else we return (a[v]) + (mn — a[v])/2 that is simply getting both the values to their centre point .
The idea is that dfs is returning the minimum element in the subtree of the node.
You can see this soln 273567246 and its standard cuz its the simplest of DFS
Why do we take values to their center? And how does taking to centre ensure that these values of subtree nodes will always be >=0 in the future.
so look i need to set the entire tree up in such a way that the minimum value in the subtree of 1 is maximized , excluding the value of node 1. Why? cuz if the minimum value is increased that means i can perform the operation on node 1, more times before the minimum value in subtree reaches 0.
For the "if" case, say i have a node with val 5, and it has 3 children with values 3,7,9 now i will simply return 3, why? cuz if i perform any operation on node with val 5, the val 3 will decrease thus decreasing the minimum.
For the "else" case, say i have a node with val 2 and it has 2 children with values say 7 and 9, so the min value of the subtree currently is 2, but we can make it better , as the minimum value of the child is 7, if i perform the operation twice the values will become 4, 5,7 . so i took them to their centre value. And more operations are clearly of no use as the minimum value that is currently 4 will start decreasing.
So the idea is MAXIMIZING the MINIMUM in every subtree, beginning from leaf nodes to root.
For the second case you can maximize the root to 11. And the tree after the operations becomes 11,0,2 Can you explain this else case again?
alright so in the second case, lets say x has value 2, and it has 2 children y and z with values with 7 and 9, and x is connected to node 1.
so the tree is like 1->x->(y,z)
so the DFS begins, for y it will return 7 and for z it will return 9. now for x the minimum value amongst it's subtrees,i.e. y and z, will be 7. But its own value is 2 which is lower than 7.
For better understanding , lets suppose we dont do any operations and simply return the minimum then we return 2. and now we are at node 1 , and the minimum element in all its children's subtrees is 2, so that means i can just increase the value of node 1 twice before one of the elements in the tree gets 0.
Now, suppose we did some operations on x, so minmum amongst it's child subtrees was 7 and it's value was 2, how many operations should i do, such that the minimum of the entire subtree is MAXIMIZED and not only the value of node x? i should do (7-2)/2 = 2 operations so value of x would become 4, value of y and z gets 5 and 7, so the minimum of the subtree gets 4 and i return it , this is the maximized minimum of the subtree. And now i can perform 4 operations on node 1 :).
Let's say what if i did more oerations on x ? say 2 more operations , x's value becomes 6, y and z become 3 and 5, now the minimum of the ENTIRE subtree is 3 , so that means i can only do 3 operations on node 1, which is not the best possibility , Thats why i take values to the center
Great explanation! i did it in the same way
IT is a pretty straight forward Tree DP Question. And not everybody learns mostly off codeforces, I just do codeforces for the contests, but rarely for Practice Purposes (except if they appear on USACO Guide)
But yeah, 5k on D is still quite a lot.
if you don't mind what other resource are you using?
I personally just do mostly USACO Guide. Doing Bronze to Silver and knowing some techniques from Gold should be enough in my opinion. Also it is very important to do the actual codeforces contests, since it does also help with general problem solving instead of just solving problems tied to specific topics
Tbh as a newbie i found D easier than other div2 rounds but sadly i was not able to write code
Does anyone else keep getting WA on test case 19 for problem D? Solving E and losing rating is tough :((
Yes
What is the exact tc?? I also faced the same :/
YESSSSSS :( 273588603
In your code, val can grow exponentially. Keep a check, if it is greater that 1e9 return false.
You're right, thanks!
If you passed the number Y to dfs, which must be subtracted from all the numbers in the subset, then Y may have become greater than 2^64
Me too, no f... idea what's wrong in that case 19...
Okay, got it now though, happy days, jeeez...
I tried problem E, Got the correct solution. Exceeded the time limit :(
Imagine looking for an overflow for 30+ mins while telling yourself the following code snippet "definitely isn't the cause, its bounded by $$$n \cdot max(a)$$$".
Wait this causes an overflow? :0 Can you explain why?
Consider a line graph with the following values of $$$a_i$$$
$$$1 \rightarrow 0 \rightarrow 0 \rightarrow 0 \rightarrow 0 \cdots$$$
Then if our starting "cost" (i.e., how much we want to add to the root) is $$$1$$$, then the corresponding values of cost for each node becomes:
$$$1 \rightarrow 1 \rightarrow 2 \rightarrow 4 \rightarrow 8 \cdots$$$
So the value simply overflows for any such line graph of more than $$$32$$$ / $$$64$$$ nodes depending on whether you're using 32 or 64 bit ints.
Got it, thanks! So we just need a special check once the the value is greater than $$$10^9$$$
The contest was really easy, the first 4 problems felt like Div. 3, and problem D was very classical.
The B question is something! How are they able to make such tough problems! I bet even gpt cannot solve these problems
It was not that hard. You just have to find the free cell that serves as the only bridge to 3 free cells. You can look at my post contest submission to figure it out. I misread the problem statement and I thought there could be more than 1 sets. I solved it in that way in contest.
Thank you! But after writing the comment I wrote, I was able to understand the problem.
couldn't solve D
I'm so retarded,
doing cf for year and still nowhere near blue
It's ok it took me more than a year for expert
You are specialist so you are definitely not retarded. I looked at your profile and 70% of your solved problems are below 1400, so maybe practice harder problems.
his real account is madboly(I think I spelled it right)
how to solve F, I tried many dp approaches but it didn't work.
Note that tokens behave like fibonacci sequence, you have $$$f_1$$$ $$$f_2$$$ and can create some $$$f_i$$$ for $$$i>=3$$$ using $$$f_{i-1}$$$ and $$$f_{i-2}$$$ or to change $$$f_i$$$ for $$$f_{i-1}$$$ and $$$f_{i-2}$$$. You can also freely change $$$f_1$$$ to $$$f_2$$$ and vice versa. So $$$f_i$$$ means token on position $$$i$$$.
First convert all tokens to $$$f_1$$$ and $$$f_2$$$, let the number of them be $$$s$$$. Note that, because you can change $$$f_1$$$ to $$$f_2$$$ and vice versa, all that matter is their sum ($$$s$$$). You want to use minimum number of tokens to represent $$$s$$$. One token means some $$$f_i$$$. If you have $$$1000$$$ $$$f_{10}$$$ tokens maximum $$$s$$$ you can get is $$$55000$$$.
Now you do greedy, for every sum $$$s <= 55000$$$, you go through $$$f_{30}$$$ to $$$f_1$$$ and try to fit sum $$$s$$$ in minimum number of tokens (there is proof for fibonacci numbers that greedy is optimal).
Now for some sum $$$s$$$ you have $$$min[s]$$$ which represent minimum number of tokens to represent it. We want such $$$s$$$ that $$$min[s] = m$$$.
Lastly we need to calculate in how many ways can we get sum $$$s$$$ using $$$n$$$ tokens on first $$$x$$$ $$$f$$$s. Define $$$dp[i][sm][p]$$$ as in first $$$i$$$ $$$f$$$s you placed $$$p$$$ tokens and their sum is $$$sm$$$, this dp has at most $$$10*55000*1000$$$ states, transitions are in $$$O(1)$$$.
Now you just sum $$$dp[x][sm][n]$$$ such that $$$min[sm] = m$$$
273592555
This might also help.
i had about the same idea but the 10*55000*1000 dp sounds really scary to me
in fact, if you limit $$$sm$$$ to $$$n\cdot fib_i$$$ (instead of $$$n\cdot fib_x$$$), the total number of states is only $$$n^2\sum_{i=1}^x fib_i=1.43\times10^8$$$, so it runs really fast :D
Man A screwed me
really I thought A was really easy I just thought that chose the substring with longest repeating chars and just insert the different char than the present one in between of that substring
now I realised that we don't need to find even longest substring though just find 2 repeating chars and insert the different char in between them. I am such a noob :(
It's ok I first understood that it requires minimum time and implemented a brute force solution and got wa1 and then sent another solution still wa1 and then realized it wanted maximum
lmao, xD thats tough
I also WA in test1 2 times and chuckles. I know today im gonna screw up by not having enough time again
I was thinking why the time limit was 2 seconds. I literally did not make any sense.
it's just standard time limit in educational contests
someone please tell how to solve E
do it in different ways when $$$x \le \sqrt n$$$ and when $$$x \gt \sqrt n$$$. The former can be pre-calculated, while the latter can be solved by binary searching on prefix-sum
Wow I didn't think of that
but what is the prefix sum?
One observation is that, when $$$x \gt \sqrt n$$$, the level would never exceed $$$\sqrt n$$$. Then we can calculate prefix sum on the number of monsters having level $$$ \ge k$$$, for all $$$k$$$ s from 1 to $$$\sqrt n$$$ —- the monsters to encounter having level k
UPD: Sorry, got hack on this. The complexity is actually $$$O(q\sqrt n \log n)$$$, approximately 10x slower than $$$O(n \log^2 n)$$$ for $$$n = q = 2e5$$$, maybe not fast enough even for a time limit of 4s. One mending might be brute-force to $$$h = 2000$$$ instead of $$$\sqrt n$$$ (Than the overall complexity would be $$$O(hn + \frac{n}{h}q\log n)$$$ which is $$$\lt O(q\sqrt n \log n)$$$)
I did exactly that and got TLE on testcase 63
You can precalculate an array of indices for each $$$k$$$, where the indices show where the last update of level happened. I did it with merge sort tree in $$$O(n \cdot log^3_2{n} + q \cdot log_2{n})$$$.
I did the same, but got TLE :(. The way I wrote seems like having large constant factor.
First let's call $$$S(x)$$$ the set of indices where you can win the game. Then if $$$x > $$$ then $$$S(y)$$$ is a subset of $$$S(x)$$$. So let's compute for all $$$k$$$ from $$$n$$$ to $$$1$$$
We can see than when $$$k = n$$$ then all indices will be true. Then let's loop now.
What do we do for some $$$k$$$? We can notice that the remaining indices will be divided into blocks of size $$$k$$$. In the first block you will be level 1, in the second block level 2, and so on. So let's loop through the blocks. For the block we are currently on, we will repeat the following process:
If hhe minimum element in the block is less than the level, then this index will be removed and we will reprocess the block
Otherwise we will exit the block and go to the next block.
Note that when you remove an element, a new element might become part of the block.
After you process $$$S(k)$$$ for the $$$k$$$ you are currently on, just loop through the queries with $$$x=k$$$ and answer them depending on whether $$$i$$$ is in $$$S(k)$$$ or not. Note that you are answering offline.
Time complexity is $$$(nlog^2n + q)$$$ since for each $$$k$$$ we are going through $$$n/k$$$ blocks and each time we get the minimum using seg or something. Here is my code 273590110
NekoYellow .-__-. Abito thanks
i have an idea that we can group the queries by k
then for each can simulate the game by using segment tree in $$$O((n / k) log(n))$$$
so we can do this in $$$O(n * log^2(n))$$$
someone please correct me if i'm wrong.
Notice that the level you can reach by the $$$i$$$-th monster is non-increasing as $$$k$$$ increases.
Let $$$need_i$$$ represent the minimum $$$k$$$ for which our level will be $$$\leq a_i$$$ when we reach the $$$i$$$-th monster.
We can binary search on the value of $$$need_i$$$. To check if $$$need_i \leq k$$$, we want to know if the number of monsters we would have fought till $$$i - 1$$$ is $$$\lt k \cdot a_i$$$, or formally $$$\text{cnt}(need_j \leq k$$$ where $$$j \lt i) \lt k \cdot a_i$$$.
To check this $$$cnt$$$ quickly iterate in increasing order of $$$i$$$ and store the values of $$$need_i$$$ in a fenwick tree, then $$$\text{cnt}(need_j \leq k$$$ where $$$j \lt i)$$$ is just $$$sum(k)$$$.
Code — 273568637
can you elaborate on how to find for each k i.e
we want to know if the number of monsters we would have fought till i−1 is <k⋅ai, or formally cnt(needj≤k where j<i)<k⋅ai.can you explain thiswon't it be non-increasing??
Oops, yeah I accidentally reversed the meaning in my mind while writing this. Fixed it now.
Check my comment.
Bad round, seriously
for what reason? like the problems were easier than div 2?
I think, problems were easier than hard div3
yeah maybe
Go and solve E, F, if problems are easier than hard div 3 :)
Questions A to D are easier than usual,but E and F are still challenging
this is like the 2nd or 3rd contest where i spend an entire hour on D and swept E in 20 mins from start to end
How do I approach problem D?
for each node u it is optimal to have $$$A[u] <= min(A[each \ node \ in \ subtree \ of \ u])$$$
then answer is just $$$A[1] + min(A[each \ node \ in \ subtree \ of \ 1])$$$
https://mirror.codeforces.com/blog/entry/132049?#comment-1177386 see my approach explained in this comment
What is the idea for E?
https://mirror.codeforces.com/blog/entry/11080?#comment-946680
can you please explain
If a $$$k$$$ doesn't scare monster $$$i$$$, then all $$$k+1, k+2, ...$$$ won't scare it. Therefore you can binary search on $$$k$$$ and find how many monsters are also not scared with a segment tree (or Tree Order Statistics), thus finding the level you're going to be at at this index with a specified value $$$k$$$.
273560444
I don't understand why we used a sum segment tree for this problem. If I want to determine whether a specific value $$$K$$$ can scare the fourth monster in the array $$${x, y, z, M}$$$, how does knowing the sum of $$$x$$$, $$$y$$$, and $$$z$$$ help me decide that? I think the ordering of the three numbers might differ. Sorry if I misunderstood the code.
We are not summing the values themselves, but we are rather calculating the amount of monsters at indices $$$1...i-1$$$ that would not be scared with a value $$$k$$$.
That can be calculated by storing the minimum $$$k$$$ we found for indices $$$1...i-1$$$ in another array $$$freq$$$, where $$$freq_j$$$ denotes how many monsters stay when $$$k = j$$$ but leave when $$$k < j$$$. We will then query for $$$\sum_{l=1}^{k} freq_l$$$.
why my code failed for D ? link my solution
May be return earlier when its impossible, long long int may not enough.
yes just added val = min(val,inf); it got ac link AC solution I wish I could have thought this in contest :(
Data structure to solve E: https://mirror.codeforces.com/blog/entry/11080?#comment-946680
Screencast with commentary
$$$O(NX + N^2/X\ log(N))$$$ should be enough to E? I chose $$$X = 1000$$$, and I saw in the worst case it would do like $$$9\times 10^8$$$ operations, and the code executed fast enough, 640ms.
First brute force up to 1000 (ordering queries), then the next I solved doing binary searches in prefix sum to each level up to 200, to find the point of each upgrade.
I think in E you can actually optimize the large $$$k$$$ case using harmonic sums so it becomes $$$O(n\sqrt{n}+nlog^2(n))$$$. i.e. for each level only iterate $$$k$$$ up to $$$\frac{n}{l}$$$ (or so).
You can solve E in $$$O(nlog^2n)$$$, for each $$$i$$$ you can define $$$f(i,x)$$$ as 0 if $$$i$$$ runs for value $$$k=x$$$ or 1 if $$$i$$$ doesn't run for value $$$k=x$$$. See that $$$f$$$ is monotonic so you can binary search it. ($$$f(i,0)=0$$$ for all $$$i$$$ for implementation sake)
Go through all elements and binary search $$$x$$$ such that $$$f(i,x)=0$$$ and $$$f(i,x+1)=1$$$, in order for element $$$i$$$ to run for some $$$x$$$ there should be $$$a[i]*x$$$ elements that don't run on prefix. You can use ordered set, for calculating how many elements stay/run on prefix. Answering queries is straight forward just compare $$$ans[i]$$$ with $$$x$$$. 273562301
I solved in your complexity. I TLEd under X=1000 and ACd with X=2000.
It can be solved in $$$O((n+q)\sqrt n)$$$ without Binary Search if you maintain both prefix sums and lists of indices that need fight for each $$$k \leq \sqrt n$$$: 273605589.
I had to use $$$2\sqrt n$$$ for the brute force part to get the memory under 512MB :/
Everyone is doing binary search for D while I did entry and exit times with lazy minimum segment tree lol
Hahahha what, I solved it with basic DFS
Yea I overcomplicated it so much I basically just took the minimum in the whole tree and if its a leaf then break otherwise i take the minimum in the minimums subtree (not including the minimum) and lets call that mn2 i increase minimum by (mn2-mn+1)/2 and decrease everything in its subtree by that. I keep repeating until the minimum is the leaf then i just increase root by the minimum in the whole tree other than the root.
I solved same way
Same but the segment tree not lazy ahaha
i ditched binary search because i kept getting WA with it lol
I got 4 times TLE with binary search. I seriously don't know, why
Log(2e9) * 2 * 10^5 gets TLE.
https://mirror.codeforces.com/contest/1997/submission/273568701
man...penalty sucks
As a pupil, I'm hoping to reach legendary grand master after this contest. Wish me luck!
Worst contest ever taken...
B question was very poorly written i thought if i am not able to do b then how can i do C and further question , it took my whole contest time . Only because it wasnt mentioned clearly that in the starting only at most 1 region is given.
It was mentioned under the second picture.
I also didn't check the announcement and wasted a lot of time on B.
Same took 40 minutes solving B because of it
who else got WA test 19 on D for binary searching ??
one of the worst rounds I have ever done, especially B, I couldn't do it while I solved C in 5mins.
Ignore
Lol I got cooked in a for starting the matching character check from 1 to n and not 0 to n.
Why do I always RE on the D question?（Python）
u need to extend the recursion limit for that
I've used sys.setrecursionLimit(1000000)
Unlike C++, the stack size of Python runtime is fairly small (I think it's 1MB that's Windows' default), and this doesn't change even if you call
sys.setrecursionlimit(), so heavily recursed solutions will get RE anyway.Can someone please check my 2 solution for D and tell me where i could optimize i'm feel defeated at it please anyone spare few minutes on my solution if u want i can explain what i did in my code
Submission 1 TLE Submission 2 MLE
it was more like div 2.5
worts round for me :( all my progress is gone in just one contest. B was so poorly written, and i couldnt figure out the integer overflow on D. why do i even do cp lmao
Could a solution with time complexity $$$O(n \cdot \log(n)^4)$$$ pass for E or would it be too slow?
I implemented a solution around
O(N log(N)^3 + Q log(N))and barely managed to pass.I thought in problem E O(Nlog^3(N)) would fit in TL, but it didn't :/ Submission Can finding the next index from current index i for which count of monsters >= current level is equal to k be done in O(log(N))? I tried binary search + fractional cascading in O(log^2(N))
Hi fellow Sarthak.
It looks like the runtime of your solution is more to the effect of
O(n^2/k)rather thanO(nlog^3(n))since you have nested for loops (iterating by 1 and ~ k respectively).The approach I took was to find the smallest k for which monster
icould fight Monocarp, each inO(log^2n)time (hint: I used a binary search + seg tree). This allowed queries to be answered inO(1). Hope this helps :)I did it in$n \cdot log^3_2{n}$ by walking on the segment tree.
Yes, you can do it similarly to the range k-th order statistic problem.
Let $$$b_{x,i} = [a_i \ge x]$$$ for $$$x \in [1, n]$$$, i.e. each $$$b_x$$$ is an array that contains $$$1$$$s on the positions where $$$a_i \ge x$$$ and $$$0$$$s on the rest. Now, let's build a range sum point update segment tree $$$T_x$$$ on each of those arrays $$$b_x$$$. Finding the next index is just a matter of descending $$$T_x$$$, where $$$x$$$ is the current level, but building those trees naïvely is too slow. However, if you make those trees persistent, then all you need is to build $$$T_n$$$ in $$$\mathcal O(n)$$$ (since level does not exceed $$$n$$$), and then $$$T_x$$$ can be obtained from $$$T_{x+1}$$$ by replacing $$$0$$$s with $$$1$$$s in the positions $$$i$$$ where $$$a_i = x$$$. Since you do $$$\mathcal O(n)$$$ point updates in total, the construction of all $$$T_x$$$ works in $$$\mathcal O(n \log n)$$$.
I don't know if my code is readable, but just in case: 273556813.
Please can someone explain what is the error in this appoach for D 273594204. although i know this is failing in test case one only but i am doing the same thing what question says or am i interpreting it wrong please someone explain
Please can someone tell me whats wrong.
I had this idea for D, but couldn't submit it in time. But I keep getting a runtime error on test 19. I'm using Python; can anyone see what's wrong with this submission? My submission to D (RE on test 19)
recursion limit 1e5
Still didn't work. I even increased it to 2e5, but that gave memory limit exceeded
I've found a solution. A bootstrap function I copied from @pajenegod, a GM who uses Python. It manages the call stack manually, and avoids recursion limit errors. I actually had it in my template, but didn't think to use it until now. It was accepted :)
Thanks. Feel free to check out my template (or pajenegod's code, I just don't know where to find it) for the bootstrap function. You can then use it as a decorator for the recursive function, and replace all your return statements with yield to get it to work
@pajenegod orz, once again
can anyone tell why this code for problem D failed at test case 19:
OOf. I solved B for the general case where multiple regions are present. Took me 50 minutes to come up with solution. At that point C already had like 6k solves. Thought solving D will help but nope. Ended up with a Pupil level performance even after solving D. D should not have more than 2k solves imo(even if we take into account how standard it is). Hope the cheaters get pruned.
In question B,it is said that the given grid contains at most 1 connected region;
Yaa i was also thinking about the general case first and using bfs in problem B Also problem D was a bit standard problem but still 5k submissions in quite high. Anyways best of luck for the next contest
What was your approach for solving the general case?
Assuming that there are multiple regions present you can do a bfs on the grid to identify and mark all regions. Blocks belonging to region 1 will be marked with the value 1 and so on. While you do this you also have to keep track of the size of every region(can be done using a map). Now the only conditions are: 1. There is one region and we use the editorial logic. 2. There are 4 regions and regions made of a single cell can be blocked to make the total regions equal to 3. 3. Lastly if you have 2 regions and you block a cell such that a region gets divided into 2 regions. 4. The number of regions is 3 and you block a cell in a region which has a size greater than 1(I missed this case actually). If the number of regions is greater than 4 then blocking one block will not be enough. I might be wrong tho.
it's messy for the when there are 3 regions. You can only block the end points of regions. Apart from that I also don't think there can be cases for greater than 4 regions. Your solution seems correct to me.
Overflow may be the cause of the Wa test19 on D. When recording the value that needs to be provided to the parent node, it is essential to verify whether this value exceeds the upper limit that the subtree can provide. Otherwise we can construct a case such that all the a_i equals to 0 and the value being transmitted could be vey big.
how come 12k solved c. is it that easy.
it was easier than B
Cheaters most probably, no matter how easy it was aint no way 12k people solved it suddenly. Also I noted that it happened too quickly. One moment my rank is 2.5k, within minutes it's 6k. But whatever.
Problem D if you WA on test19,please check your data scale. In the process of DFS,when the val exceed 1e9 you should return the process.
Can u explain why the if check is required, overflow issue ??
Maybe your solution is different to his,no need for the if check,but
If you use binary search to solve D.Being able to construct data where all a_i values are 0 would result in leaf nodes requiring very large values, causing them to exceed the range of 'long long'.
i got it.
I guess I should re-learn how to read statements after implementing a much harder version of problem B and then deleting almost all of it...
(But please, something as important as "at most 1 connected region" should be bold or in capital letters, or have a bigger font size, whatever, the next time around please...)
Is $$$O(nlog^3(n) + qlog(n))$$$ enough to pass E? If it is, could someone explain why my submission got TLE?
I also got TLE. Try Fenwick tree, it works for me.
Your precomputation step's complexity is actually $$$O(nlog^4n)$$$.
For each of the $$$O(nlogn)$$$ level changes you do a binary search which adds a $$$O(logn)$$$, and your query method has $$$O(logn)$$$ calls, and calling lower_bound inside adds an extra $$$O(logn)$$$.
I actually had the same issue, the query method can be changed so that the binary search is done inside the query.
Ok I miscalculate the time complexity, my bad :(
Could you explain the way to modify those binary search inside the query?
Instead of just returning a count you can return a count and also the position where it is reached. Also there is a maximum count you don't want to exceed and you need to remove a prefix which is not within the range of the query. You can take a look my submission
To do this you can use a method called 'Walk on segment tree'. Basically it uses the structure of the segment tree in such a way that you don't have to do an additional binary search. You can read about it from here.
I slightly modified your submission to use this concept and got AC:273649483
As you can see, instead of using the
qrymethod along with binary search, I made another method calledqry2which makes use of walk on segment tree.that is around
O(N log(N)^4 + Q log (N)), you may want to use walk on the merge sort tree to cut off a log(N) coefficient.Okay, I just remember about the "finding the kth largest problem" and know how to walk on the merge sort tree. Thanks for your help.
my best ever contest. First time abcd solve in div. 2. authors were also very nice, I had a very nice and friendly interaction with them while asking questions. Overall, loved the contest but ngl, D was a little bit easier
I don't think I've ever blundered this hard in a contest, forgot a return statement in A and forgot to check one cell in B, so by 53 mins I had only C solved + multiple WAs for A and B. (+ I couldn't find the issue in B till the end of the contest :( )
Some people like problems like B, but I think such subtle statements in the problem statement reduce readability. It becomes more about reading the problem than actually solving it. (Might just be skill issue)
is this solution of E hackable ? (https://mirror.codeforces.com/contest/1997/submission/273599912)
D : For all the nodes u, find the maximum value they can have such that all the nodes in their subtree will have the final values atleast equal to the final value of node u . Now for root , the maximum increase in its value is " the minimum of the final values of all its childs " .
Code
Recently cheating has increased quite a lot on CodeForces although problem D was bit standard more like leetcode contest hard question(6 pointer not 7 or 8) but still 5k submissions is really high, the contest went really well for me but still got around 2.7k rank. I have been stuck at specialist rating for some time now due to the high level of cheating. Hope CF will increase action on these cheater
i wanna know they got the question before the contest or they interact each other ? how they do this ?
I guess these solutions are shared in telegram groups during the contest due to some companies using coding platform rating as screener but still it gets really unfare for genuine users
I definitely think a person being stuck at a rank has more to do with their skill level than cheating.
It is not that people have stopped becoming experts, have they? We should focus on what we can focus on, rather than finding excuses.
While cheating is absolutely a thing, I don't think attributing being stuck at a certain rating point to it is a good idea. What you're essentially claiming is that 5k people couldn't have solved D, casting doubt at each person with an AC.
Sorry didn't meant it like that just wanted to point that cheating does effect user rating as such assuming even just 5-10% users cheat. I understand it might also be difficult for codeforces due to high number of false positives in a stricter plag checker Also as you are a candidate master can you suggest mistakes to avoid and increase ones problem solving skill with time
awoo orz.
for D i try binary search and dfs .it looks right but i wa on 19 for 3 times so sad :(
make the if condition in the dfs function if(v > 2e9)
thx very much i learn that the v will overflow long long int
solved.
D without binary search and overflow —
Let $$$dp[i] = $$$ maximum possible minimum value in the subtree of $$$i$$$ with optimal operations. We have —
$$$ dp[i] = \begin{Bmatrix} a[i] & \text{ if } i \text{ is a leaf} \newline \min\limits_{j \in \text{ child of } i}(dp[j]) & \text{ if } \min\limits_{j \in \text{ child of } i} (dp[j]) \leq a[i] \newline \left\lfloor\frac{a[i] + \min\limits_{j \in \text{ child of } i} (dp[j])}{2}\right\rfloor & \text{ if } \min\limits_{j \in \text{ child of } i} (dp[j]) > a[i] \newline \end{Bmatrix} $$$
Submission — https://mirror.codeforces.com/contest/1997/submission/273602376
I read your comment so I went to fix the overflow in my code and got Accepted, lol
It was confusing I kept asking, what is so different in test 19
same approach. Fist bumps!
Same here, however it is better to describe the approach instead of giving those formular, as it will be scare for people who didn't know how to do this.
similar approach but I don't know why I stored it in a segment tree tho, kinda dumb xD and a waste of time!
can anyone help show me what's the wrong test in my solution problem D: 273557414. My idea was collecting points from leaf to root
nevermind I found the error, only put parents that have no child left into the queue. Skill issue again
Long time without writing segtree at contest + bad approach (ignored few cases) cost me -3 at final standings.
Approach: let's solve problem offline for each $$$k$$$ in queries.
If $$$k\leq K$$$ (let's choose $$$K$$$ later), than solve with stupid method (just implement statement), requiring $$$O(n)$$$ for each $$$k\leq K$$$, overall $$$O(nK)$$$.
If $$$k>K$$$, there is at least $$$ceil(\frac{n}{k})$$$ monsters to be passed before level up. Since there, we can make $$$ceil(\frac{n}{k})$$$ steps for each $$$k>K$$$. Where $$$W$$$ -- magical constant, stated as time to be done following: gived fixed $$$r$$$ -- left edge of interval and $$$lvl$$$ -- our current lvl, find minimal $$$i\geq prev$$$, such that $$$count(a_j\geq lvl, r\leq j \leq i)=k$$$. It can be solved in $$$O(\log^2(n))=W$$$ time using segment tree storing sorted vectors of elements on array.
So, let's take $$$K=1000$$$ and final complexity is: $$$O(Kn+n\cdot \log(n)+\frac{qn\cdot \log^2(n)}{K})$$$
WA during contest: 273573012 OK: 273599991
It's sad to see that constraints on problem B were corrected(mentioned for the first time) around after half an hour.
I just solved D after the end by less than a minute, very sad
How do we solve D without binary search?
Check my comment above.
Yes, we could use greedy. Knowing that if we goes up to a root of some subtrees, those children in this subtree won't be higher (as the operation will make them decreasing by $$$1$$$ each time), so we will aim for maximizing the minimum of all value of this subtree (including the root of this subtree as well).
let dp[u] be the max smallest value of subtree u after doing operations
for node u: without doing any operations then the min val would be min(A[u],dp[v]) where v are all the children
you could spend one operation to increase A[u] but that would decrease dp[v] by 1
so let a = A[u], b = min(dp[v]) if a > b then do nothing (aka dp[u] = b)
otherwise do k operations until min(a+k,b-k) maximizes (which just so happens to be (b-a)/2 operations) -> dp[u] = min(a+(b-a)/2, b-(b-a)/2)
for the root/final answer: you could freely do the operation so the answer is A[0] + min(dp[v])
check my approach explained in this comment https://mirror.codeforces.com/blog/entry/132049?#comment-1177386
can anyone explain me no. B simply, what should i do?
if you delete a cell then the most number of regions that can be created is the number of open cells that neighbours it directly -> it must have 3 empty neighbours
now imagine this:
1 v 3
a 2 b
v = the node you're deleting
if a is an empty cell then region 1 and 2 are actually the same region so you'll only get at most 2 regions -> a must be blocked
same for b and region 2+3
so the answer is just the number of patterns that are either
. . .
x . x
or
x . x
. . .
Nice approach. Even i did the same way..we do not need visited array if we make it directed graph.
very bad contest for me wasted almost 1 hour 40 minutes just because i thought x is capital and in the end i somehow figured out what was the mistake anyway cheating has been at it's peak today
By the way, the custom invocation tab wasn't working today. I tried benchmarking my F to account for hardware differences, but it wasn't responding. Fortunately, it did not matter to me today, but you should probably fix it before the next big event.
I don't know who introduced the Cloudflare checking system to codeforces (to check if I'm a human), but I suffered the worst. The problemset was quite standard but it took me aound 7 minutes to enter the contest as 'The system was still checking if I'm a human'. Then after solving A, I could not submit any problem as the same problem kept happening. I tried mobile cf, other browsers, tried to change my net, nothing worked. I guess yeah, my network was quite slow but I could not enter the whole contest after that! I do not blame anyone but it was really a sad contest for me as I was quite hopeful I could solve upto D.
same to me...
Idk why my code is giving RunTime error on a particular case Question D With exit code 1:
Here's my submission Submission
Maybe anyone is interested in non-recursive solution for D, I did it during the contest because was afraid of hack, I thought that recursion depth of 2*10^5 will cause overflow. Also left there recursive function for comparison: https://mirror.codeforces.com/contest/1997/submission/273588364
any body knows how to fix the friend glitch, i am unable to add or remove anyone?
Please check my approach for D, is it hackable or not ?? 273621989
For Q-D wa on testcase 19 , putting a condition in dfs function as a base case that if the required subtraction need to be done from the subtree > 1e9 , return false may work !!
1
Many people solved F with a Fibonacci idea. What was the actual idea?
Can someone link some blogs to read about it and also some problems of a similar idea.
TY in advance :D
Greedy for D works too, basically we add to each node until that node is less than or equal to the minimum in its subtree (excluding itself). I did this during the contest
273574835 why my this solution for C is giving TLE?
String formed = "";formed += '(';The string concatenation is slow because the new string is created every time, you can use
StringBuilderfor better performance.StringBuilder formed = new StringBuilder("");formed.append('(');You can replace with these and submit again.
damnn! it worked. thanks a lot!
this is something new which I have came across. do you know any specific reason for this behaviour?
StringinJavais immutable which means it can't be modified. The way it handles the update is to clone the current one to the new one, then apply the changes on this new one, then assign the result back to the original one. This performance would be really slow for big string and especially in the loop.thanks for sharing!
It's really a good round. Thank you!
Where's the text solution?
Hack my solution to E.
Can anyone explain why the rank is decreasing during the hacking phase? Thanks!
Basically some people originally above you in the rankings got their solutions hacked.
I am sorry I meant increasing in my mind it was decreasing I had a rank of 5880 something but during the hacking phase it went up to 5960
In that case you are probably seeing unofficial rankings, which includes virtual participants as well.
Oh yes, that makes sense. Thanks!
Can anyone please help me find why below solution got me WA . I am binary searching on the maximum increment that i can do on the root node.
Thanks in advance....!
Someone tell me why my solution to problem D is giving TLE? 273573102
When you call the function
traversal, the function will make a copy ofm. So if it is calledntimes, themwill be copyedntimes, which will cause TLE. You can pass the reference ofmto the function so it won't be copyed when you call the function.Thank you! I will remember it for future problems
second question was a quite tough for begginers maybe but finally i did it without using bfs. I use mapping for both strings and then solved it further.It was such satisfying and good experience. Thank you.
i dont think it was tough , it was just a pattern that needed to be observed , if you can make a 'V'OR 'A'with x at the vertices, its done.
(B,C,D) <<<< A <<<<< (E,F)
F is a beauty!! loved that the Fibonacci is hidden in plain sight idea!! it had everything, memory optimization, knapsack, and lovely math.
"This round will be rated for the participants with rating lower than 2100." Is this contest was rated for newbie or not ??
yes its rated for newbie
But it is showing unrated on my profile
wait till system testing
still not updated
D was a very great problem, but some of my friend get WA on the 19th test
he didn't handle the overflow like me
oh, i see!
first time to solve problem D in contest, and hope to solve problem E in contest one day :)
Hi, can somebody tell me about the complexity of 273675185
$$$O(nlog^4{n})$$$ assuming the LTE function is $$$O(log^2{n})$$$, I don't know wavelet trees.
I have used the implementation in this link. it says that, Counting elements less than or equal to $$$x$$$ in a given range is $$$O(\log {n})$$$.
Hmmm, that is very OP, what is the point of merge sort trees then?
given that, the counting happens in $$$O(\log n)$$$ time. the complexity of this solution should be $$$O(n\log^3{n})$$$ . but it is giving TLE. can you spot any mistake in this.
I don't understand your code sorry. Are you sure that your complexity is $$$n log^3{n}$$$, I solved it in $$$n log^3{n}$$$, maybe your constant factor is too high.
Editorial when?
I am wondering why someone with red name is official participants. (20240731 08:05 GMT)
However, it said "This round will be rated for the participants with rating lower than 2100" in the announcement.
After system testing you will be able to see the standings for Div. 2 separately.
Thank you very much!
In edu rounds, every participant is "official", but only participants with 2100- rating will be rated.
Thank you
What is wrong with the following submission, it is giving a? as output for s = "a", locally it is working fine.
https://mirror.codeforces.com/contest/1997/submission/273676836
Your first for loop starts from s.size()-2, but input size is 1. Maybe this causes undefined behaviour.
Yeah, size returns unsigned it which causes the issue. Casting it to int solves the issue
In this part of your code:
The function
s.size()returns the type ofunsigned int, so it can't be negative.However, you have written
int i = s.size() - 2.So $$$s.size() == 1$$$ and then $$$s.size()-2 < 0$$$.
Therefore, $$$i$$$ becomes a extremely big number, then will be somewhere successfully match the scentence
if(s[i]==s[i+1]), and $$$n$$$ will also become really big, that is, $$$n$$$ will not be $$$-1$$$.Thus, it cannot get into the block
if(n==-1).Tricky but interesting problem F, enjoy it.
qp
Good luck!I hope I can achieve green after this contest if I have time to participate in this contest.
Heyy anyone solve D using BS?
Lots of people.
I want to know that why system testing take much more time than div 1? Can you explain me?
First, open hacking phase adds an extra 12+ hours delay.
Second, actually easier rounds (educational/div3/div4) are more appealing to lower-ranked people, which actually holds the majority of the users, resulting in more participations, and more codes to rejudge.
Ok,that means no of participant fact.
This time especially was slower due to crazy amount of TL hacks on E, which was solved quite a lot for its position, and most of solutions on it used a few seconds on each test. Each solution alone took 5-15 minutes to be fully judged.
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Wow! Now everyone is rated for EDU!
Is this round rated for DIV1 participants?
MikeMirzayanov Why was this contest rated for me even though I've long been a master??? I want my rating back.
it was better when you make the error
I found my contest submission had got a TLE, but when I resubmitted it after the system test, I passed. What's wrong with it?
contest submission, resubmission
The running time depends. The running time of your resubmission is 3406ms, it's also very close to the time limit. So maybe submitting during the contest again also makes you accept.
I was hacked after the contest, and as far as I know, resubmission doesn't count in the system test.
How would i know which contest is rated for me and which is not?? Like an upcoming contest is Codeforces Round(Div 2), will it be rated for div 4??
if ur rating is below 1400 then div4, div3, div2 are rated for u. if ur rating is below 1600 then div3, div2 are rated for u. if ur rating is below 2100 then div2 is rated for 4
Failed to pass F during the contest but passed after finished 8min...
But I reach CM!!!
I have one doubt regarding Problem E. In this problem when i used segmented tree my solution exceeded the time limit in test case 12 but when i did the same with fenwick tree it passed . Can anyone tell me the reason behind it? although the updation and query time complexity for both the data structure is same ,that is O(logN). 273965828 Fenwick Tree , 273964980 Segmented tree.