Serval's blog

By Serval, 5 years ago, In English

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

  1. ihdignite
  2. KassiJulgus
  3. mmmod_Iqs
  4. kidddddddddddddddddddddd
  5. xianhaoming
  6. __Ressed__
  7. nikolapesic2802
  8. xiaowuc1
  9. ei133333
  10. Kho0007

Div. 1 + Div. 2

  1. ihdignite
  2. 244mhq
  3. KassiJulgus
  4. uwi
  5. step_by_step
  6. mmmod_Iqs
  7. mmmod_lqs
  8. teja349
  9. RDDCCD
  10. quailty

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

  • Vote: I like it
  • +490
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +56 Vote: I do not like it

I wish after this I wouldn’t be able to participate in Div2

»
5 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Another Chinese Round is coming!

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    But the time is not friendly...

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +31 Vote: I do not like it

      We wanted to hold it earlier but the time was conflicted with Atcoder Beginner Contest. :)

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Maybe earlier than Atcoder Beginner Contest?

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          That's toooo early. If so, this round should be started before 18:00 UTC+8. :(

»
5 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Cool Now I know I can't solve interactive one xD

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wish to be able to participate in Div1 after this contest.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    So why U dont participate?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, I really want to participate, but I had something others must be done. QAQ

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I wish I'll be able to attend Div.1 after this concert. :)

»
5 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Contest once in a week!

Too much pain in one line.

»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Got -60 twice in div3, will try this one

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +19 Vote: I do not like it

    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 :)

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

i hope get some points in this contest!

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Chinese Round, interesting.

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

hope to be expert this round

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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).

»
5 years ago, # |
  Vote: I like it +71 Vote: I do not like it

In the problem statement, mistakenly I read 'Serval' as 'Several', several times.

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I've met the same thing before..

»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Was Codeforces down for everybody for the period of around thirty minutes or was that just me?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Every other website was working, so I doubt it's me. People probably will be complaining after the round =)

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I've tried refreshing for a few times, only helped after ~30mins

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    I was using and refreshing Codeforces constantly (to see friend's standings). Didn't even go down once for me.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    It was down for me also

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    During last few seconds, I was not able to submit. But not for 30 minutes for sure.

»
5 years ago, # |
  Vote: I like it +17 Vote: I do not like it

What approach can be taken to solve Problem D?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What do you mean by relative order? I used a similar dp state, but cannot get it right. Thanks in advance.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +25 Vote: I do not like it

    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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    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.

»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

How to solve D?

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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...

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    write the formulas open the formulas and integrate it. no very good observations pure math

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      can you please explain your solution in detail?

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it +52 Vote: I do not like it

        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.

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 4   Vote: I like it +30 Vote: I do not like it

        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$$$.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    The solution of F is DP. Editorial will be out later. :)

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same here probably not couting some flush or idk...

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    sorry

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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. :D

    Weird, but I won't blame anyone. Today I learned. :">
    Thanks Codeforces and the setter team for the round. ;)

»
5 years ago, # |
  Vote: I like it +59 Vote: I do not like it

Amazing round!

Problems were very cool!

»
5 years ago, # |
  Vote: I like it +56 Vote: I do not like it

What a beautiful contest! thanks for this interesting round and looking forward to your next rounds.

»
5 years ago, # |
Rev. 2   Vote: I like it +35 Vote: I do not like it

Enjoyed the round, especially D. Time to upvote contest announcement. :P

Can anyone explain their approach for F?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C ?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    try to make '(' from left and ')' from right ....

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    Code

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any idea about test case 6 of C?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it's probably something like this

    10

    (?)?)??(?) which should print (()()()())

    found that bug in my solution but hadn't enough time to fix it

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    maybe 6 ???)??

    answer should be ((()))

»
5 years ago, # |
Rev. 7   Vote: I like it +15 Vote: I do not like it

Oh, nooo! There were 10 seconds left, I tried to submit my solution for E(pressed the "submit" button)

This

but the website was slow and just showed "502 Bad Gateway".

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Same, I tried hacking but cf was too slow at the end :(

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
5 years ago, # |
  Vote: I like it +53 Vote: I do not like it

D and E were interesting problems with the ideal difficulty for div 2 contests, hats off to round writers.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It seems that I will never be able to solve an interacive problem :(

How to solve E and F?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hint for E: Answer for the query == 1 (mod) 2 iff exactly one of ends of snake lies in asked rectangle.

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks, but actually, I’ve thought about it before, and I still couldn’t solve it.

      upd: Hey, I think I got it. Thanks!

»
5 years ago, # |
  Vote: I like it +47 Vote: I do not like it

I think D problem is an easy version of this problem 538E. (Used the same solution and passed)

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +46 Vote: I do not like it

    I feel sorry about it but we havn't seen this problem before this comment. :(

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Trying to submit the solution is the last 10 seconds, but the submit page didn't load :(

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For problem C why my logic will fail?

https://codeforces.com/contest/1153/submission/52703030

EDIT: Above submission is just for explaining my logic

This is my final solution https://codeforces.com/contest/1153/submission/52709706

Here i am checking the string by reversing also.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Even I was doing the same mistake for almost an hour :(

    Then suddenly striked a test case

    6 ((?)))

    Your Output: :( Correct Output: ((()))

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You use a greedy way for parenthesis completion, which fails to form a valid solution in several cases. Try:

    8 (????)))

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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 ((())).

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Isn't :( correct for 6 (())?? since (()) is a valid bracket sequence prefix?

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I meant when the input is 6 ???)??, the only correct answer is ((())), but when executing his code, print :(, because the string becomes (())??.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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... :(

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

»
5 years ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

got WA on pretest 4 on problem A 4 times and raged
skipping problems
finally found out B is simple
solved B at about 01:31
found dumb mistakes of A and got AC
found dumb mistakes of C and got AC
me:rage
(when you participate on time but got the first AC at 01:31)

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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?

  • »
    »
    5 years ago, # ^ |
    Rev. 5   Vote: I like it +11 Vote: I do not like it

    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. :D

    My solution, for reference: 52716310

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. Very good explanation))

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can also search for single column/rows to find it.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody elaborate how to do D? I can't can't seem to make formula for each dfs.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My approach using some observe:

    1. max node would ignore all small number from subtree
    2. min node would sum all number from subtree
    3. result of a subtree is bounded with its size

    try it!

    https://codeforces.com/contest/1153/submission/52707952
    (I traverse with bottom up)

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      "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".

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 5   Vote: I like it 0 Vote: I do not like it

        Well, I solved D like this:

        1. Make an array, say, dp[n]. Now, assign dp[i] = 1 to each leaf of the tree.
        2. 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.
        3. 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.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          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 ?

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          What does dp[node] denote?

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hi phyzzmat , Can you please explain all these 3 steps ? why are you doing so ?

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I wish after next contest i will become a master.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey teja349 can you explain your code of C ?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

»
5 years ago, # |
Rev. 2   Vote: I like it -37 Vote: I do not like it

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?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +48 Vote: I do not like it

    We feel sorry about forgetting to explain it, but I wish you can get it from the first sample and its illustrations. :)

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -51 Vote: I do not like it

      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.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +52 Vote: I do not like it

        But how does that make a difference? The grid is square.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +55 Vote: I do not like it
        1. It makes no difference.
        2. 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')
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it -45 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +24 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it -22 Vote: I do not like it

              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.

»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Nice contest with a good problem difficulty distribution. I really enjoyed it.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Kudos to the writers !!! A balanced round with gradually increasing difficulty in problems.

Really liked it !!!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell what fails test case 6 in problem C https://codeforces.com/contest/1153/submission/52718031

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 queries

52719905

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice round!! Can't wait to see the editorial

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Serval is winning ACM ICPC in the future.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Someone Share their Approach for Solving E. Thank You.

»
5 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Nice problems. And especially cool samples illustrations.

»
5 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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...

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello! Can anyone help me with last problem F?) Will the analysis be posted?

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Japari is here.jpg

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

wish i can be "expert" in next context :)

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Really nice contest, thanks for the problems!

»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

It's a great Chinese round I think.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A

why min{ ((a-t)%b+b)%b } is wrong?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
5 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Is it possible that the guy at first place had his tasks done by someone else ? Is it allowed on Codeforces?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's not allowed, but I did everything on my own so don't worry.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please upload the editorial for problem D.