### Serval's blog

By Serval, 3 years ago,

Hi Codeforces!

We are glad to invite you to our first Codeforces Round Codeforces Round #551 (Div. 2) which will be held on Apr/13/2019 17:05 (Moscow time). This round will be rated for participants with rating less than 2100. We will be glad to see participants from the first division to join out of competition as well!

In this round, as the best friend of Serval's, you are going to help him to solve the problems he meets.

The problems are prepared by bzh and me. We hope you will enjoy the round. :P

Great thanks to 300iq for coordination of this round, isaf27, vintage_Vlad_Makeev, KAN, mohammedehab2002, Learner99, Aleks5d and Um_nik for testing our rounds, and MikeMirzayanov for the amazing Codeforces and Polygon platforms.

You will be given 6 problems to solve in 2 hours. Scoring distribution will be announced later.

Please pay attention that there will be an interactive problem in this round, so learn more about interactive problems here before the contest.

Good luck & Have fun! :D

UPD: Scoring distribution is: 500-1000-1500-1750-2250-2750.

UPD2: Thank you for your participation in this round! Congratulations to the winners!

Div. 2

Div. 1 + Div. 2

UPD3: Sorry for the delay. The editorial is available.

• +490

 » 3 years ago, # |   +56 I wish after this I wouldn’t be able to participate in Div2
•  » » 3 years ago, # ^ |   +20 Me too！Fighting for the last 30 points!
•  » » » 3 years ago, # ^ |   +16 Congrats!
•  » » 3 years ago, # ^ |   +4 So why U dont participate?
•  » » » 3 years ago, # ^ |   +3 I missed it when I got home it was already started and an hour was passed
 » 3 years ago, # |   +25 Another Chinese Round is coming!
•  » » 3 years ago, # ^ |   +8 But the time is not friendly...
•  » » » 3 years ago, # ^ |   +31 We wanted to hold it earlier but the time was conflicted with Atcoder Beginner Contest. :)
•  » » » » 3 years ago, # ^ |   0 Maybe earlier than Atcoder Beginner Contest?
•  » » » » » 3 years ago, # ^ |   +8 That's toooo early. If so, this round should be started before 18:00 UTC+8. :(
 » 3 years ago, # | ← Rev. 2 →   +3 Cool Now I know I can't solve interactive one xD
 » 3 years ago, # |   0 Thanks for posting the link to the explanation of interactive problems! Before this I didn't even know what interactive problems are. Learnt a lot :)
 » 3 years ago, # |   0 Good luck to the round!!!~(≧▽≦)/~
 » 3 years ago, # |   0 Wish to be able to participate in Div1 after this contest.
•  » » 3 years ago, # ^ |   +14 So why U dont participate?
•  » » » 3 years ago, # ^ |   0 Well, I really want to participate, but I had something others must be done. QAQ
 » 3 years ago, # | ← Rev. 2 →   0 I wish I'll be able to attend Div.1 after this concert. :)
•  » » 3 years ago, # ^ |   +4 *contest
 » 3 years ago, # |   +28 Contest once in a week!Too much pain in one line.
 » 3 years ago, # |   +7 Got -60 twice in div3, will try this one
•  » » 3 years ago, # ^ | ← Rev. 2 →   +19 I got -49 and -41 in two Div.3 rounds when I was a Pupil. Hope you can get rating increasing in Div.2 rounds :)
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +4 [deleted] sorry if this annoy somebody :(
•  » » » 3 years ago, # ^ |   0 ouuan You've improved faster man as per your ratings graph!
 » 3 years ago, # |   +1 i hope get some points in this contest!
 » 3 years ago, # |   -31 Let's get ready to rumblllllllllllllllllllleeeeeeeeeeeeeeeee!
 » 3 years ago, # |   +3 Chinese Round, interesting.
 » 3 years ago, # |   +6 hope to be expert this round
 » 3 years ago, # |   -8 Chinese Round is coming!
 » 3 years ago, # |   0 Each time I try to submit, it says you should be registered for this contest when I registered 2 minutes before the start of the round. What is happening? Please help someone.
•  » » 3 years ago, # ^ |   +6 As I know, you can't register in 2 minutes before the round starts, because registration cancels in 5 minutes before, so you may got a bug with a CF and you somehow registered (but no).
 » 3 years ago, # |   +71 In the problem statement, mistakenly I read 'Serval' as 'Several', several times.
 » 3 years ago, # |   +5 I heard of that some contestant(my friends) got "You have submitted exactly the same code before" when They submit their code of problem A. Can anyone tell me what happened?
•  » » 3 years ago, # ^ |   0 You get this message iff you make the exact same submission without any code change. This actually prevents making the same submission twice (making the submit button idempotent).It might be the case that your friend either made the same submission again or it just happened due to some network issue. In either case, at least once the submission should have been submitted.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Maybe it’s because of the network issue.But the strange thing is that he said that was the first submission in that contest and There’re nothing in My Submission.
•  » » 3 years ago, # ^ |   +3 I've met the same thing before..
 » 3 years ago, # |   -10 Was Codeforces down for everybody for the period of around thirty minutes or was that just me?
•  » » 3 years ago, # ^ |   +5 It was working for me. so mostly only you or maybe I did not do any submit in that 30 min mark to even notice it. But if it happened people would complain here I guess
•  » » » 3 years ago, # ^ |   0 Every other website was working, so I doubt it's me. People probably will be complaining after the round =)
•  » » » » 3 years ago, # ^ |   +8 I've seen connection timeout errors for a few weeks. It appears sometimes even when there aren't any contests on codeforces. Did you try to refresh the page several times? It helps me
•  » » » » » 3 years ago, # ^ |   0 I've tried refreshing for a few times, only helped after ~30mins
•  » » 3 years ago, # ^ |   +27 I was using and refreshing Codeforces constantly (to see friend's standings). Didn't even go down once for me.
•  » » 3 years ago, # ^ |   -6 It was down for me also
•  » » 3 years ago, # ^ |   0 During last few seconds, I was not able to submit. But not for 30 minutes for sure.
 » 3 years ago, # |   +17 What approach can be taken to solve Problem D?
•  » » 3 years ago, # ^ |   +3 Store, for each vertices cnt[v] = number of leaves in subtree rooted at v, and dp[v] = maximum number v can get, if leaves in its subtree are assigned numbers from 1 to cnt[v]. Transitions can be derived by considering relative order.
•  » » » 3 years ago, # ^ |   0 What do you mean by relative order? I used a similar dp state, but cannot get it right. Thanks in advance.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +25 binary search on the value, for a given x, all values >= x will become 1, otherwise 0. then do a normal dfs to find the minimum needed 1s and if it's less that the 1s you have, then it's true, otherwise false.
•  » » 3 years ago, # ^ |   +22 For each vertex find number d such that we need d numbers >= x to get value x in this vertex. For leaves it's 1, for min it's sum of this value in children, for max it's min of this value in children. Now answer is number of leaves — this value in root.
•  » » » 3 years ago, # ^ |   +4 What is x?
•  » » » » 3 years ago, # ^ |   0 Arbitrary number — d is the same for any x.
 » 3 years ago, # |   +7 How to solve D?
•  » » 3 years ago, # ^ |   0 Maybe it's a DP
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 It's a dp problem on tree. You can see my submission later 52702102
 » 3 years ago, # | ← Rev. 2 →   0 Is Problme F about integrating the formula for each possible $k$?Tried to find some "smart observation" all the time and didn't get it...
•  » » 3 years ago, # ^ |   +11 write the formulas open the formulas and integrate it. no very good observations pure math
•  » » » 3 years ago, # ^ |   +9 can you please explain your solution in detail?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +52 This is how I solved this problem. I couldn't submit it but since all the test cases matched, I'm sure that I am right. Also, this solution may be circuitous. First, we can assume that the length of initial segment is $1$, and multiply the calculated answer by $l$ afterwards. Now, instead of choosing arbitrary $2n$ endpoints of segments, let's randomly chose them from a set consisting of $m$ points, which is $\displaystyle {0, \frac 1{m-1}, \frac 2{m-1}, \cdots, 1}$. Then, let $p_i$ be the probability that the segment $\displaystyle s_i = \left[\frac{i-1}{m-1}, \frac{i}{m-1}\right]$ is covered by one subsegment. Then the probability that segment $s_i$ is covered with more than $k$ segment is \begin{eqnarray} \sum_{j=k}^n {}_n C_j \cdot p_i^j (1-p_i)^{n-j}, \end{eqnarray} and each $p_i$ can be calculated by \begin{eqnarray} p_i = 2 \frac im \left(1-\frac im \right), \end{eqnarray} so the expected "expected value" for this situation can be calculated by \begin{eqnarray} \sum_{i=1}^{m-1} \frac 1{m-1} \sum_{j=k}^n {}_n C_j \cdot \left( 2 \frac im \left(1-\frac im \right) \right)^j \left(1-\left( 2 \frac im \left(1-\frac im \right) \right)\right)^{n-j}. \end{eqnarray}Whew, it's hard work to write mathematical equation on the PC. I'll write the rest after I take some rest.
•  » » » » 3 years ago, # ^ | ← Rev. 4 →   +30 Now, supposing that $m$ is infinite, the last equation can be calculated as follows. (Here, we apply the well-known fact that $\displaystyle \lim_{n\to\infty} \frac 1n \sum_{i=1}^{n} f\left(\frac in\right) = \int_0^1 f(x) dx$, but I don't know how this fact is called in English... somebody tell me) \begin{eqnarray} \lim_{m\to\infty} \sum_{i=1}^{m-1} \frac 1{m-1} \sum_{j=k}^n {}_n C_j \cdot \left( 2 \frac im \left(1-\frac im \right) \right)^j \left(1-2 \frac im \left(1-\frac im \right)\right)^{n-j} \end{eqnarray} \begin{eqnarray} = \sum_{j=k}^n {}_n C_j \int_0^1 (2x(1-x))^j (1-2x(1-x))^{n-j} dx \end{eqnarray} \begin{eqnarray} = \sum_{j=k}^n {}_n C_j \int_0^1 (2x(1-x))^j\sum_{l=0}^{n-j} {}_{n-j}C_l (-2x(1-x))^l dx \end{eqnarray} \begin{eqnarray} = \sum_{j=k}^n {}_n C_j \sum_{l=0}^{n-j} {}_{n-j}C_l (-1)^l 2^{j+l} \int_0^1 x^{j+l} (1-x)^{j+l} dx \end{eqnarray}The last integral is Beta function, and the value is $\displaystyle \frac{(j+l)!(j+l)!}{((j+l)+(j+l)+1)!}$. Now we can calculate the answer by $O(n^2)$, which is enough for $n \leq 2000$.
•  » » » » » 3 years ago, # ^ |   -8
•  » » » » » 3 years ago, # ^ |   +11 I think it is called limit as a sum
•  » » » » » » 3 years ago, # ^ |   +11 Riemann sum. From wikipedia))
•  » » 3 years ago, # ^ |   +20 The solution of F is DP. Editorial will be out later. :)
•  » » » 3 years ago, # ^ |   0 Wow. I am looking forward to it.
 » 3 years ago, # |   +6 Makes me wonder, what was that pretest 3 of E?I think I've come up with a right approach, yet not sure if I made any mistakes :D
•  » » 3 years ago, # ^ |   0 Same here probably not couting some flush or idk...
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 sorry
•  » » » 3 years ago, # ^ |   +6 Hmm I'm talking of E, not C. ;)
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I figured my issues and got AC. My submission: 52716310.(For reference, my WA3 solution: 52711736)However, I still think Codeforces judge system worked a bit weird.If my implementation was correct (hopefully I didn't misread anything), any time I read value -1 my code would terminate immediately with a non-zero return code, therefore force-runtime-error my solution. Yet in this case (well too bad I use only 1 exceeded query :"> ), guess the interactor stopped and sent the verdict to the checker immediately before I had my chance to force-RE. :DWeird, but I won't blame anyone. Today I learned. :">Thanks Codeforces and the setter team for the round. ;)
 » 3 years ago, # |   +59 Amazing round!Problems were very cool!
 » 3 years ago, # |   +56 What a beautiful contest! thanks for this interesting round and looking forward to your next rounds.
 » 3 years ago, # | ← Rev. 2 →   +35 Enjoyed the round, especially D. Time to upvote contest announcement. :PCan anyone explain their approach for F?
 » 3 years ago, # |   0 how to solve C ?
•  » » 3 years ago, # ^ |   +3 try to make '(' from left and ')' from right ....
•  » » 3 years ago, # ^ |   +5 Firstly odd strings will never work. Secondly you will always need same number of ( and ) in the final string. Thirdly you want to change ? to ( in the beginning of the string and ? to ) in the last part of the string.Then just do the usual stack code to check if the parenthesis are balanced.
•  » » » 3 years ago, # ^ |   0 For C my logic was to continuosly maintain (number of opening brackets-number of closing brackets)=1 while traversing till the second last element. I can't understand where it went wrong?
•  » » » » 3 years ago, # ^ |   +7 If you have something like (??))), we need to replace the second ? with ( and get balance of 3 instead of 1, or we will not be able to form correct sequence.
•  » » » » » 3 years ago, # ^ |   0 That was helpful! Thank you
 » 3 years ago, # |   0 Any idea about test case 6 of C?
•  » » 3 years ago, # ^ |   0 it's probably something like this10(?)?)??(?) which should print (()()()())found that bug in my solution but hadn't enough time to fix it
•  » » » 3 years ago, # ^ |   0 My code is printing the correct answer for this case but it still failed TC6
•  » » 3 years ago, # ^ |   0 maybe 6 ???)??answer should be ((()))
•  » » » 3 years ago, # ^ |   -8 i initially got wrong answer on this.I was getting wrong ans for below test case 6 (?(?))
•  » » » 3 years ago, # ^ |   0 Yes that was the test case I was getting error at! Thank You
 » 3 years ago, # | ← Rev. 7 →   +15 Oh, nooo! There were 10 seconds left, I tried to submit my solution for E(pressed the "submit" button) This// No time for good code... #include #include #define mp make_pair int n; std::map, std::pair>, int> memo; bool same(int x, int y, int X, int Y) { if (x<1 || y<1 || X<1 || Y<1 || x>n || y>n || X>n || Y>n || x>X || y>Y) throw; std::cout<<"? "<>res; if (res<0) throw; return (res%2==0); } void answer(int x, int y, int X, int Y) { if (x<1 || y<1 || X<1 || Y<1 || x>n || y>n || X>n || Y>n || x>X || y>Y) throw; std::cout<<"! "<>I; } int getx(int x, int y, int X, int Y) { int l=x, r=X; while (l+1>n; for (int x=1; x
•  » » 3 years ago, # ^ |   +5 Same, I tried hacking but cf was too slow at the end :(
•  » » 3 years ago, # ^ |   0 Similar thing happened to me too, but while loading (and eventually getting 502 bad gateway error) there was a notification to browser that said pretests passed
 » 3 years ago, # |   +53 D and E were interesting problems with the ideal difficulty for div 2 contests, hats off to round writers.
 » 3 years ago, # |   0 It seems that I will never be able to solve an interacive problem :(How to solve E and F?
•  » » 3 years ago, # ^ |   0 Hint for E: Answer for the query == 1 (mod) 2 iff exactly one of ends of snake lies in asked rectangle.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Thanks, but actually, I’ve thought about it before, and I still couldn’t solve it.upd: Hey, I think I got it. Thanks!
 » 3 years ago, # |   +47 I think D problem is an easy version of this problem 538E. (Used the same solution and passed)
•  » » 3 years ago, # ^ |   +46 I feel sorry about it but we havn't seen this problem before this comment. :(
 » 3 years ago, # |   +11 Trying to submit the solution is the last 10 seconds, but the submit page didn't load :(
 » 3 years ago, # |   0 So much "Wrong answer" verdict in Problem A.
 » 3 years ago, # | ← Rev. 2 →   0 For problem C why my logic will fail?https://codeforces.com/contest/1153/submission/52703030EDIT: Above submission is just for explaining my logic This is my final solution https://codeforces.com/contest/1153/submission/52709706Here i am checking the string by reversing also.
•  » » 3 years ago, # ^ |   0 Even I was doing the same mistake for almost an hour :(Then suddenly striked a test case6 ((?)))Your Output: :( Correct Output: ((()))
•  » » » 3 years ago, # ^ |   0 I also got the test case.So i also checked by reversing the string. I just put this solution link to explain my logic, in my another submission i checked from both the sides so it should pass.
•  » » » » 3 years ago, # ^ |   +1 Try this8 (??)(??)
•  » » » » » 3 years ago, # ^ |   0 Got it thanks
•  » » 3 years ago, # ^ |   0 You use a greedy way for parenthesis completion, which fails to form a valid solution in several cases. Try:8 (????)))
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 Similarly, when the input is like this,6???)??after executing your code the string s is (())??, and according to Line 40(the third of the five cout<<":(";), print :(, and end. But the correct answer is ((())).
•  » » » 3 years ago, # ^ |   0 Isn't :( correct for 6 (())?? since (()) is a valid bracket sequence prefix?
•  » » » » 3 years ago, # ^ |   0 I meant when the input is 6 ???)??, the only correct answer is ((())), but when executing his code, print :(, because the string becomes (())??.
 » 3 years ago, # |   0 I finally solved the very last problem and all the test cases showed right answer. Feeling full of confidence and delight, I opened the submission page, only to find that contest was over five minutes ago... :(
 » 3 years ago, # |   +8 I'm pretty sure I'm gonna WA on E because there is one case where I use 2020 queries instead of 2019. Feels bad.
•  » » 3 years ago, # ^ |   0 I felt same, but I got AC.
 » 3 years ago, # | ← Rev. 3 →   +8 got WA on pretest 4 on problem A 4 times and ragedskipping problemsfinally found out B is simplesolved B at about 01:31found dumb mistakes of A and got ACfound dumb mistakes of C and got ACme:rage(when you participate on time but got the first AC at 01:31)
 » 3 years ago, # |   +5 Can anybody explain how to solve E? if the shake have only the head and the tail and the field consist from 1 million cells, how is it possible to find them having made only 2019 queries?
•  » » 3 years ago, # ^ | ← Rev. 5 →   +11 A bit intuitively, but we can see a few things: If the chosen rectangle contains exactly one end of the snake, the query result will be an odd integer, otherwise the result will be even. Since two ends of the snake are in different cells, there must be either two columns or two rows that each contains one distinct end of the snake. Our solution will be divided into two phases:Phase 1: Find the columns/rows with the snake's end.Assume that the snake's head and tail stays at different rows, let's denote them as $xa$ and $xb$ (since we don't really care about the order of the head and tail, assume that $xa < xb$). Thus we'll see that: - $xa$ is the lowest row index $x$ such as query ? 1 1 x n returns an odd value. - $xb$ is the lowest row index $x$ higher than $xa$ such as query ? 1 1 x n returns an even value.If searching for the rows didn't do, we repeat the similar process with the columns.In theory, this phase takes up $2000$ queries, but we can shrink it to $1998$, knowing that querying with the last row/column always results in $0$.Phase 2: Find the exact cell in each row/column.This part has a binary search concept.Assume that we're working with rectangle x ya x yb (if the rectangle has the form of xa y xb y, we can do similar things).Assume $ym = \lfloor \frac{ya+yb}{2} \rfloor$. We'll query the rectangle x ya x ym. If the returning value is odd, continue the binary search with that rectangle, otherwise continue with the rectangle x (ym+1) x yb if such rectangle exists.Repeat the search until the rectangle consists of only one cell. That would be the head/tail we need.Each binary search process consumes at maximum $\lceil \log2(1000) \rceil$ queries, or $10$ queries.We have two rows/columns to deal with, so the second phase will use up to $10 \cdot 2 = 20$ queries.In summary, the process (at its most optimal form) will use $2018$ queries at most. Pretty close. :DMy solution, for reference: 52716310
•  » » » 3 years ago, # ^ |   0 Thanks. Very good explanation))
•  » » » 3 years ago, # ^ |   0 You can also search for single column/rows to find it.
•  » » 3 years ago, # ^ |   +4 If the result of a query is odd, then exactly one snake end must be in the rectangle.Query all rows. If both ends are in different rows, we obtain two queries with an odd result and can binary search the cell in both rows.If all rows return an even result, this means that both ends must be in the same row, therefore both ends can not be in the same column. Query all columns to get the columns of both ends. Then, for the first column binary search one snake end. As both snake ends are in the same row, we are done.As binary search takes at most 10 queries for $n\leq 1000$, we have that in the first case we use at most $1000 + 2\cdot 10\leq 2019$ queries. In the second case, we use at most $2\cdot 1000 + 10\leq 2019$ queries.
•  » » » 3 years ago, # ^ |   0 I did not get the case where the ends are in the same row. Let's say that I know that one of the heads is in Col x and other in Col (x + 1) and both are in the same row. How do I find which row from there?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Got it now, that in the first row iteration, a even number(zero in the above case) meant that the heads might or might not be inside. But now as I at least have one crossover, an even number(zero in the above case) will definitely mean that the heads are not inside.
 » 3 years ago, # |   0 Can somebody elaborate how to do D? I can't can't seem to make formula for each dfs.
•  » » 3 years ago, # ^ |   0 My approach using some observe: max node would ignore all small number from subtree min node would sum all number from subtree result of a subtree is bounded with its size try it!https://codeforces.com/contest/1153/submission/52707952(I traverse with bottom up)
•  » » » 3 years ago, # ^ |   0 "Ignore all small number"? I don't understand meaning of it. What is "small" and what is "number". Same with minimum, why "sum" and why "number".
•  » » » » 3 years ago, # ^ | ← Rev. 5 →   0 Well, I solved D like this: Make an array, say, dp[n]. Now, assign dp[i] = 1 to each leaf of the tree. Fill in the array in the following fashion recursively: if the node's property is "max", then assign dp[node] = minimum value of dp of its children; else dp[node] = sum of values of dp of its children. The answer is then number_of_leaves — dp[0] + 1, where dp[0] is root. See https://codeforces.com/contest/1153/submission/52713093 for details.
•  » » » » » 3 years ago, # ^ |   +6 I understand the code, and see that it works. But I still have no idea why it works. Why use min and/or sum in the two cases, and why is the answer = num_leaves — dp[root]+1 ?
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 For a max node, if we know there is a min subtree that has m leaves, we can assign k, k-1, k-2, ... k-m+1 to all these leaves, after applying min operation, that min node will have value k-m+1, we want this value to be as large as possible, thus we want m to be as small as possible. here m means dp[i] in the above code.Hope this helps.
•  » » » » » 3 years ago, # ^ |   0 What does dp[node] denote?
•  » » » » » 3 years ago, # ^ |   0 Hi lollihunter , Can you please explain all these 3 steps ? why are you doing so ?
 » 3 years ago, # |   +2 I wish after next contest i will become a master.
 » 3 years ago, # |   0 Hey teja349 can you explain your code of C ?
•  » » 3 years ago, # ^ |   +8 I used the same approach.It's based on the observation that we should give priority to put open brackets first in the sequence. So we just count in the first iteration that how many open brackets we can put more in the string (Remember you cannot put more than n/2 open brackets).In the next iteration whenever we get a '?' we put open brackets until we have exhausted them all and then put all the closed ones. At each point we check that the balance should not be less than or equal to 0 except at the end of the string where it should be exactly zero.Why this works? Because in any valid sequence you can always replace a closing bracket with a later open bracket.
 » 3 years ago, # | ← Rev. 2 →   -37 Why did you not specify in Problem E whether (1,1) is the top-left or bottom-left or etc.? How do I know that whether you treat as coordinate system or like a matrix?
•  » » 3 years ago, # ^ |   +48 We feel sorry about forgetting to explain it, but I wish you can get it from the first sample and its illustrations. :)
•  » » » 3 years ago, # ^ |   -51 The problem statement should be complete! The samples are for further explanations, not to complement the problem statement. I didn't look at the samples during the contest. You named cells as (x1, y1) which implies coordinate system.
•  » » » » 3 years ago, # ^ |   +52 But how does that make a difference? The grid is square.
•  » » » » 3 years ago, # ^ |   +55 It makes no difference. You didn't look at the samples? Well then guess whose fault it is that you didn't get it? (hint: it's not the problem setters')
•  » » » » » 3 years ago, # ^ |   -45 I don't have to prove to myself in that rush that it's symmetric and it makes no difference etc. The problem statement should be clear and complete! I'm quite surprised that you guys can't understand this and look for fault in me, but not in the incomplete statement.Moreover, author himself says "sorry for forgetting that ...", you don't have to act like smart.
•  » » » » » » 3 years ago, # ^ |   +24 I don't have to prove to myself in that rush that it's symmetric and it makes no difference etc. The problem statement should be clear and complete!What? First, you don't look at the samples, now you don't have to make observations about the problem? Less than that even, you claim you're in too much of a rush to realise that a square is symmetric? You might want to reassess how you spend your time then. You could've asked for a clarification mid-contest, that's what it's there for. Or you could've thought about it for yourself. Instead, you decide to blame the author for your own incompetence. The statement isn't incomplete. There is more than enough information to solve the problem, enough for 213 solves in a div2E.Moreover, author himself says "sorry for forgetting that ..."Yes, the author apologised, because they recognised an area where they could do better. Maybe you should do the same.
•  » » » » » » » 3 years ago, # ^ |   -22 What you fail to understand is that no matter how many people solved that problem (maybe all), or whether I look at the samples or not, the problem statement should be clear and complete! If you think the other way, then it's your problem! I appreciated author's apologies and finding room for improvement but not your advocacy for someone's faults.
 » 3 years ago, # |   +16 Nice contest with a good problem difficulty distribution. I really enjoyed it.
 » 3 years ago, # |   0 Kudos to the writers !!! A balanced round with gradually increasing difficulty in problems.Really liked it !!!
 » 3 years ago, # |   0 can anyone tell what fails test case 6 in problem C https://codeforces.com/contest/1153/submission/52718031
 » 3 years ago, # |   0 Hello, can somebody help me with the interactive problem? My code gets WA 8, telling me that my program asks more than 2019 queries, however I checked multiple times and my program takes either 2*n + 1, 2*n + 9 or 2*n + 18 queries (my binary search throws at most 9 queries each time, although its impossible even those 9. I just don't see how my program could ask more that 2019 queries52719905
•  » » 3 years ago, # ^ |   0 I think that your binary search may take 10 queries. Note that if you start with i = 2^9 it'll be divided 10 times until it reaches 0
•  » » » 3 years ago, # ^ |   0 It will be divided 10 times, but whats inside the for will be called at most 9 times, since the 10th division will give i = 0 and the for will quit.
 » 3 years ago, # |   +1 Nice round!! Can't wait to see the editorial
 » 3 years ago, # |   +3 Serval is winning ACM ICPC in the future.
 » 3 years ago, # |   0 Can Someone Share their Approach for Solving E. Thank You.
•  » » 3 years ago, # ^ |   0 Cool, I found one above .
 » 3 years ago, # | ← Rev. 2 →   +3 Nice problems. And especially cool samples illustrations.
 » 3 years ago, # | ← Rev. 2 →   +1 I am stuck on the problem C , I am getting WA on tc-6 , however I have checked all the test-cases given in the comment section and my code passes on all of them. I have used a greedy logic where the first opening brackets should be closed by the last bracket to ensure no prefix is a valid bracket sequence, now for the remaining brackets I am maintaining a cnt if there is a ? then if cnt > 0 replace it with ")" else replace it with "(" if at any time the cnt < 0 then I try to change ")" to "(" to increase count. Please anyone help me , what is the error I am not able to get it, after spending hours on the question Submission link
•  » » 3 years ago, # ^ |   0 You need to iterate the string "from both sides", or twice. First time counting the opening, and closing brackets. Second time replacing the question-marks. Replace them by open brackets from the left, and closing ondes from the right, make sure number of open and close is same. Check if the resulting string is correct. If yes, then all prefixes of it are not correct.
•  » » 3 years ago, # ^ |   0 you can iterate the string from left to right and replace "?" with "(" as many as you can,you can see that other position must be replace with ")".when you replace all "?" with "(" or ")",just check the string to ensure that the string is correct and any prefixes is not correct.hope that can help you and sorry my English is poor,hope you can understand...
•  » » » 2 years ago, # ^ |   0 Can you please give me an idea of how to prove the above greedy method
 » 3 years ago, # |   0 Hello! Can anyone help me with last problem F?) Will the analysis be posted?
 » 3 years ago, # |   +8 Japari is here.jpg
 » 3 years ago, # |   +3 wish i can be "expert" in next context :)
 » 3 years ago, # |   +3 Really nice contest, thanks for the problems!
 » 3 years ago, # |   +14 It's a great Chinese round I think.
 » 3 years ago, # |   0 Problem Awhy min{ ((a-t)%b+b)%b } is wrong?
•  » » 3 years ago, # ^ |   0 Because time of waiting can go up to a which can be much larger than b, if you arrive before the bus comes for the first time.
•  » » 3 years ago, # ^ |   0 If I understand your formula correctly, $a$ is the time of first bus arrival and $b$ is the period of buses arriving.You calculate answer as minimum of some values by modulo of each $b$, so answer will never exceed $min(b)$. Consider test cases like this: $n = 1, t = 1, a_1 = 1234, b_1 = 1$. There will be no buses until $1234$ time moment but your solution will give $0$ as answer.
 » 3 years ago, # | ← Rev. 3 →   -12 [please ignore earlier posted message, I confused node id and value filled in]
 » 3 years ago, # |   -11 Is it possible that the guy at first place had his tasks done by someone else ? Is it allowed on Codeforces?
•  » » 3 years ago, # ^ |   0 It's not allowed, but I did everything on my own so don't worry.
•  » » » 3 years ago, # ^ |   0 Sorry for saying that, cause I look at your recent stats and I think it's a little bit "not normal"
 » 3 years ago, # |   0 Please upload the editorial for problem D.
•  » » 3 years ago, # ^ |   0 That's already published: D
 » 3 years ago, # |   0 It showed that my solution to problem one was accepted but now shows that it is wrong answer.Why?