ouuan's blog

Codeforces Round #564
By ouuan, history, 5 years ago, In English

Hi!

We are glad to invite you to take part in Codeforces Round 564 (Div. 1) and Codeforces Round 564 (Div. 2), they will be held on Jun/07/2019 15:05 (Moscow time). The round will be rated for both divisions.

Participants in each division will be offered 6 problems and 2 hours to solve them, including 4 shared problems for both divisions, and one of them has two versions with the only difference in constraints.

The problems were written and prepared by me, Sulfox, QAQAutoMaton, ODT, ccz181078, rushcheyo and PinkRabbitAFO.

Great thanks to 300iq for coordinating and testing the round, we enjoyed the experience of preparing a round with him.

Thanks to Um_nik, KAN, isaf27, xht37, ButterflyDew and DKACVenus for testing the round, too.

Of course, thanks to MikeMirzayanov for amazing systems Codeforces and Polygon!

Last but not least, thanks to everyone who participates in this round, for making our efforts meaningful.

Both English and Chinese editorials will be available after the contest.

UPD 1: The scoring distribution will be:

  • Div.2: 500 — 1000 — 1500 — 1750 — (1250 + 1250) — 2750

  • Div.1: 500 — 750 — (750 + 750) — 1750 — 2500 — 2750

UPD 2: Congratulations to the winners!

Div.1:

  1. Rewinding

  2. maroonrk

  3. WA_TLE

  4. zeronumber

  5. nhho

Div.2:

  1. foreverlasting

  2. wifiiiiii

  3. liuxiao

  4. Joysh

  5. YenSean

UPD 3:

The English Editorial and the Chinese Editorial are published.

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

Comments Comments (192)
| Write comment?
»
5 years ago, # |
  Vote: I like it +141 Vote: I do not like it

Wish everyone have fun!

→ Reply
»
5 years ago, # |
  Vote: I like it -32 Vote: I do not like it

hope short problems and high rating!

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

Friendly time to Chinese！

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

    It's Happy DuanWu Festival match

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

      happy DuanWu Festival to all the Chinese

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

    But bad time for people

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

      I think it's good for Chinese people!

      (After 10 p.m. is too late

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

      I think this is really a good time for Chinese

      Chinese needn't stay up until midnight QwQ

      We are able to have a good sleep after this contest qwq

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

Time :)

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

Div1+Div2, Dragon Boat Festival, UTC+8 20:05, Chinese editorial. Si Bei Yi Man!!!

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

Which problem will have two subtasks?

→ Reply
»
5 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Hope my name to become orange again qwq.

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

Could you promise no anime pictures in contest?

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

    Yes, of course. Because ODT promised to write the statement in March, and finally said he wouldn't a week ago, so I wrote the statement.

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

    You can find this problem very difficult and give it up as soon as possible by the anime pictures.

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

I hope this round will not be full of hardcore math problems :(

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

    I think this round will be full of data stucture problems because of @ODT

    → Reply
»
5 years ago, # |
  Vote: I like it -9 Vote: I do not like it

A task that has two versions counts as one task or two?

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

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

Chinese editorials? Cool!

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

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

long live china , I love all Chinese

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

Could be my chance to get to purple.
All I have to do is +22 rating...
Seems easy enough (not)

Also. Wish everyone a happy Dragon Boat Festival!

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

This round is so friendly for Chinese QwQ

Let's have fun in this round QwQ

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

I am ready to face data structure problem !

9-G8-SPh0-Cyz-Ee-Az-SEVKZepvn-DRlc

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

Wow,that will be so cool to have a such great contest in Dragon Boat Festival! :)

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

Chinese round =earlier time

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

i hope this contest will make me green and i will not be newbie anymore ... :/

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

    Good Luck and remember dont focus on ratings but on learning from the contests and your rating will automatically increase :)

    → Reply
»
5 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Chinese editorials that cool,but why there is not Chinese problems?

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

Nice time for Chinese！I wish the problems' statements can be understood clearly.(maybe making the unuseful background into another paragraph is a good idea?)Hope for an excellent competition experience.

→ Reply
»
5 years ago, # |
  Vote: I like it -23 Vote: I do not like it

I need an anime-themed contest.
We need an anime themed contest.

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

Chinese round again...It's great, but I think maybe I should get ready to face hard data structure.

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

Am I right that one of the problems has different constraints in different divisions?

Because if there are two similar problems with different constraints in one contest then there is a problem:

  1. Solve v.1 of the problem
  2. Block it
  3. Watch other solutions
  4. Find solution of guy who have passed v.2 with the same solution in v.1
  5. Copy his solution
  6. Send it to v.2
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    no, since it will only be possible to block both of these subtasks.

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

    When a simple and difficult version of the problem is solved, then it will be possible to block the task.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

thank you for the earlier time for me
maybe we can have zongzi as a snack when we are in the contest?
Wish everyone high rating!

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

repeat the math)

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

Could we view the problems in Chinese?

→ Reply
»
5 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Orz Sooke, QAQAutoMaton, ODT, ccz181078, rushcheyo and PinkRabbit and wish everyone have fun!

→ Reply
»
5 years ago, # |
  Vote: I like it -20 Vote: I do not like it

Orz LJC00118, Sooke, PinkRabbit, for they AKed IOI! Good luck to everyone!

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Well sorry about orz . But that's really a good DW contest .

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

I hate difficult data structure problems because I can't even write it out.

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

Can you tell me if a person with rating not less than 2100 can participate in Div2? I do not know because I am not used to codeforces.

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

    If the round is divided into 2 divisions, then no (you have to either participate in Div1 or wait until it's over). Otherwise, if it's a Div.2-only, it's free to do so. ;)

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

Oh my, only a year and you've gone from a green to an orange problemsetter. ;)
Congrats for your (and also the other guys') first round! ;)

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

    I always remember you since that comment :) Thank you for your encouragement!

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it
      1. Never thought my comment would leave such a deep impact. :P
      2. Too bad I couldn't participate, it's close to my dinner time and I'm shifting my focus to final exams :< but I would virtual soon. ;)
      3. Wow, first time I see a mirror of Codeforces. Well, the Great Firewall is strong. :D
      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        Oh, I use the mirror by mistake again..

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

I am very confused whether to participate in contest or watch Federer vs Nadal.

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

It's time to take back what I've lost!!!!!!!!!!

→ Reply
»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Chinesse round!!!Yes!!!! but maybe there are many data stucture problems.(maybe there are full of data stucture problems) my rating will down.....

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

Why is that m1.codeforces.com, m2.codeforces.com and m3.codeforces.com not available these days?

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

What's the score for each problem and what problem have to subtasks? QAQAutoMaton ODT ouuan

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

why not show us the scoring distribution?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -12 Vote: I do not like it

Bruh!

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

How to solve div 2 C?

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

    For each element, find the required number of moves to put it in place. Then, for each element, find the required number of moves to put it in place after moving it the maximum required times from the previous iteration. Keep going until this maximum number doesn't change. That's the answer.

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

      Binary search the number of zero moves required + number of elements to put in place?

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

        I didn't use binary search. Thinking about it now, I'm not convinced my solution wouldn't be O(n^2) in worst case. It did pass system testing, though, so take that as you will.

        I suppose if you use binary search in a clever way, you can guarantee a worst-case complexity of O(n log(n)), but I guess that wasn't necessary for this problem.

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

    The idea is to play X blank cards, where X takes values from [0, N]. Then, you should check if you can play the cards 1, 2, 3, ... N in order. Check if you can do it with X == 0 first and then do a binary search. Only the binary check function remains, and there's many ways to do it with some data structures, I used a std::priority_queue to effectively sort the values of the cards in hand. It's O(n logn) and I hope it passes the tests after the hacks, too.

    EDIT: I failed after second system testing :(

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

    /In worst case, we need to take all cards, then play all cards in order. How much can we shorten this?

    Case 1: There is an sorted postfix in b. So we can simply play all cards in order. Then number of moves is n-(len_sorted_postfix). All numbers must be available. Just check if this is possible.

    Else, we need to take (or have on hand) card 1, then card 2, then card 3...

    So, min moves is max of: pos(card 1)+n, pos(card2)-1+n, pos(card3)-2+n, ...

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

    You don't need binary search at all, you can separate it into 2 cases: 1. The first k numbers are already in the deck, and you will be able to place cards such that you finish in n-k turns. We can find k easily, then we make sure that it's possible by ensuring that for all cards in the deck besides the last k, we will get them in our hand soon enough to play them, that is, their index + 2 is at least their value — k. 2. You have to collect cards in your hand for a while, then you can place them all into the deck 1 at a time. In this case we just check for each card the time to get it into our hand and then back into the deck in the right position, and the answer is the max over all cards in the deck of their index + 2 + (n — their value).

    → Reply
»
5 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Mathforces...

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

    I dont understand why people complain about math? Most of programming reduces down to mathematics...

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

    What, you wanted ScienceForces? I guess having maths problems is not a problem.

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

      Well,I once saw a problem about balancing chemical equations,but that can be reduce down to Gaussian Elimination,so ScienceForces may become Mathforces in the end

      → Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it +61 Vote: I do not like it

I did not have 2 seconds to send the solution of the problem D, because my mouse lag (((((((((

UPD: if this solution will get AC, I`ll break my mouse.

UPD2: Accepted

UPD3: Mouse RIP

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

Real Mathforces...though I expected some data structure

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

How to solve Div2 c ????

UPD : there is my submission https://codeforces.net/contest/1173/submission/55271422

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

    Binary search the number of zero moves required + number of elements to put in place. https://ideone.com/WgHMmm

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

      What do you mean by binary search number of zeros ?

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

        from zeroes i mean number of empty moves you will perform before starting the sorted sequence. let me rephrase it as number of cards with value zero that you will play before playing other cards. Once we find this minimum number by binary search we can add n to it to get the answer.

        Be sure to check value zero before hand (case where we don't need to make any zero move). have a look at my submission here https://codeforces.net/contest/1173/submission/55269800

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

Found out where i made a mistake on 2C in last 5 seconds
submit
"contest is over"
R.I.P rating
;(

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

I wasn't able to solve any problem in div1... is the color of my name wrong?

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

    don't worry, just pretend you didn't participate, your rank will not drop anyway

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

but it was nice problem really close from solving it :(

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

How to solve div2D?

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

    Passed pretest with this — Root the tree. Fix first position as root. Each subtree will occur consecutive in circle. Then rotate the circle.

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

    $$$n \cdot \prod_{i=1}^n deg(i)!$$$

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

      proof?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 3   Vote: I like it +28 Vote: I do not like it

        First observation is that the solution is valid if and only if each subtree is in consecutive points on the circle.

        When given a subtree of root $$$i$$$ and a range of points of its size, how many ways to place it ? It has $$$deg(i)-1$$$ subtrees of its own that can be in any order which gives $$$(deg(i)-1)!$$$ and the root can be anywhere between them, $$$(deg(i)-1)+1=deg(i)$$$ possibilities which gives $$$deg(i)!$$$ and the same goes for each subtree independantly.

        For the root it's almost the same, you have $$$n$$$ positions for the root on the circle and then $$$deg(root)!$$$ for placing the $$$deg(root)$$$ subtrees.

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

      Could you please explain how this works?

      → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +28 Vote: I do not like it

We're so sorry. We tried to hack the $$$\mathcal O(n\sqrt{n\log n})$$$ solution for 1F, but hacked webmaster's treap solution unintentionally.

Writer's solution can pass in $$$1.5s$$$ in $$$\mathcal O(n\log n+m\log^2 n)$$$.

upd: It seemed that I'm wrong.. He said his solution is not in correct complexity..

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

    Why sorry?

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

      Because his solution is correct with big constant.

      upd: It seemed that I'm wrong.. He said his solution is not in correct complexity..

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

The fact that if this round was combined it wouldn't make any difference XD

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

When will we see the problem rating? After the system test done?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

When it takes you so long to debug C and understand D that you can't debug the indexes in your trivial code in time :/

solution to D
→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice job！The problems are so hard, and I just guess a conclusion when I solving the C2.(since if there is not a conclusion like that, I think I have no solution to run a code below the time limits).Wish to not fail in the system test.

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

dishonest guys:

div2C:

55261994 I_love_HellHoleStudios (link to reformatted code: link)

55261355 Zzzyt

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

Nice, neat and tidy problem set, although I will lose a lot of rating because I spent a lot of time debugging Div1.A and C1 and failed to rush C2.

Maybe it'd be better if the duration of contest is longer, e.g. 2.5h or 3h?

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

    I felt the same. It would have been great if it was a 3-hour contest. Missed to submit my solution for Div2D by 2 minutes.

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +37 Vote: I do not like it

How to solve Div1C?

I tried iterating the steps; during one step...

$$$E(i) = \frac{w_i}{\Sigma w_i} \times (w_i + a_i) + (1 - \frac{w_i}{\Sigma w_i}) \times w_i$$$

... and then I use the expected values as the new weights, but this doesn't seem to work (fails on the 3rd example).

Can anyone explain why this doesn't work and what the proper solution is?

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

    If I pass the system test, the most important observation is that everything is "similar" if you split a picture of weight $$$w$$$ to $$$w$$$ pictures of weight $$$1$$$, or merge two pictures of weight $$$a$$$ and $$$b$$$ to one of weight $$$a + b$$$. Then you may see that the expected weight of a picture is proportional to its initial weight (If you consider only liked or disliked pictures).

    Now you should solve the problem where there is only one disliked and one liked picture (whose weight equal to the sum of weight of all pictures of its kind).

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

      Why does this work — why is the "expected weight of a picture is proportional to its initial weight (If you consider only liked or disliked pictures)" but why does the solution described by mouse_wireless (which relies on proportionality in a different way) not work? I can't figure it out.

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

        Think of a picture of weight $$$w$$$ as $$$w$$$ pictures of weight $$$1$$$.

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

      Why does multiplying the expected total weight of liked pictures by w[i] / (initial total weight of liked pictures) (assuming ith picture is liked) give the expected weight of ith picture?

      EDIT: Never mind, got it from the editorial.

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

    mouse_wireless Did you figure what's wrong with your solution ?

    Why can't we use expected weights of $$$m-1$$$ operations to compute new weights?

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

I felt q(D) easier than q(C) Div 2. Is there anyone else ?

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

    What is the proof of D's solution

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

    +1. Infact from last 3-4 contest I am finding B to be difficult than C and D that's why I started today with D.

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

    Same here. I took around 1+ hour for solving+debugging div2c. When i saw div2D, I solved it in around 20-25 minutes, missed to submit the solution for just 2 minutes :/

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

I realize that giving a problem in two easy and hard versions in Codeforces is weird. In IOI-style contests, solving the whole problem gives you advantages over solving each subtask separately, as it saves lots of time to implement subtasks' solutions. However, in Codeforces, even if you can solve the harder one, you should solve and implement the easier version. In this contest, solving C1 quickly gives you lots of points in compare to submitting both C1 and C2 at the same time, when point has dropped dramatically.

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

    On the other side difficulty/points in C2 is ridiculous. It is only more than 250 points compare with A.

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

      Hmmm. It is not that ridiculous. You should consider the value of the problem C2 1500, not 750; as implementing the solution for problem C2 gives you both points of problem C1 and C2. This is the reason why in IOI-style contests, harder subtasks do not always worth more points than easier ones. But again, it supports my point that subtasks are only suitable for IOI-style contests, not Codeforces rounds.

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

      C1 is easy. I don't consider C2 worths 1500. Assuming D is 1500 and have the same difficulty and you will solve only one of two. C1 + D > C1 + C2. Dividing subtasks decreases the price of the problem.

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

Just found this explanation "Nauuo is very naughty so she didn't give you any hint of the third example." ;)

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

can anybody explain Div2 B, pls

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

    There are various answers possible. First, find $$$m=n/2+1$$$ (the order of the matrix). Then print the indices of the first row. Then print the indices of the last column (remember not to print the last element of the first row again).

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    So you can prove that if we sort n chess pieces based on their rows index, the chess piece i will occupies the diagonal from (1, i) — (i, 1). So there is 2*m-1 diagonals and n <= 2*m-1. Construct the answer is placing the chess piece accordingly in the each diagonal

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

    thanks

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

I think I figured out the solution for D (though couldn't solve it during the contest). The answer is $$$n*$$$$$$(product$$$ $$$of$$$ $$$the$$$ $$$degree$$$ $$$of$$$ $$$all$$$ $$$nodes)$$$. But I can't prove it. Can someone please explain?

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

Wow!My solution ran 3884ms on the problem C2!And I have just passed it!It's so exciting for me to look at the status for 1h. It just reminds me to be careful next time when I notice my pretest using time nearly to the time limits.

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

Spent 40 minutes debugging div1A and got WA/RE for 3 times because of my stupidness, then found out that B and C1 were a piece of cake, and at that time their points had dropped quite a lot ...

R.I.P. my rating.

Maybe I should get my brain updated.

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

    same here but in div2 I thought C won't be that hard spent 30 minutes thinking then I started to see there's a missing point in my solution then went to B but my brain got it slowly
    I made really bad decisions I will take a break from contests until I finish exams

    → Reply
»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Is $$$O((n+m)\cdot \log^2 (n))$$$ time and $$$O(n \cdot \log (n))$$$ memory intended in E?

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

    $$$O(n\log n)$$$ in time and $$$O(n)$$$ in memory. I thought you asked F, sorry for that.

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

      Don’t you think that the limits are a little too big? I’ve implemented it and it’s get TLE (OK, it can be squeezed) and is close to MLE (which is worse). 55268190

      → Reply
»
5 years ago, # |
  Vote: I like it -34 Vote: I do not like it

another mathforces round

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

Now I know my brain is made of rubbish.

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

Your solution 55245407 for the problem 1173A significantly coincides with solutions Roniee1612/55245407, wjk00/55247411. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

I got this message from the system after the coding contest. I just want to make it clear that there may be some coincidence for this problem

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

can anyone plz explain how to solve c in simple words

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

    For Div2 C:

    For each element, find the required number of moves to put it in place. Then, for each element, find the required number of moves to put it in place after moving it the maximum required times from the previous iteration. Keep going until this maximum number doesn't change. That's the answer.

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

Can anyone share the solution of div2C?

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

why this is getting TLE I can't understand
v.erase(v.begin()) is making the TLE ? removing first element in vector is O(1) right ?

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

    Erasing from the end is constant time. Removing the first element is O(n). (Where n is the length of the vector)

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

In div2 C when will ans be 2*n. my test case 12 is showing runtime error and in test case 12 answer is coming 2*n

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

Can anyone please explain Div2-B that why the number of columns is (n+2)/2 ??

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

    Consider needing to place n pieces. This means that our board must be big enough to have a distance of n between the first and last piece. Looking at a board, this means (WLOG) the top left and bottom right corners must be n squares away. In a board of size m, the top left and bottom right corners are (m-1) + (m-1) = 2*m -2 away from each other (m-1 to get to top right, m-1 to get to bottom right). So, we need that 2*m -2 >= n, which means we need m >= (n+2)/2. Since C++ rounds down, we can just set m = (n+2)/2 to guarantee m >= (n+2)/2.

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

      Great explanation

      Thank you so much sir

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

For number B Div 2, the case when n is equal to 1, is it feasible from the statement that the position of the piece will be at (1,1)? Because, if we say |i-j| == 1, not considering the fact that there is only one piece, and then the left hand side of the equation in the statement becomes 1+1 = 2 which is not greater than or equal to 1. So why have this case? Why not set the constraints from 2?

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

    When comparing the same piece to itself, both the left and right side of the equation would be 0.

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

      So, it will be subtracting 1 from 1 and not nothing from 1? And any reason as to why it will be like that? When I solved it, I had just put in a statement like if n is equal to 1 then print 1, (1,1). It was sort of an intuition and I didn't get to this by reading the statement.

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

        "for all pairs of pieces i and j" means the condition needs to be satisfied only if there exists a pair of pieces.

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

In Div2D / Div1B: What is the use of the arrangement being a circle when the positions are marked. I feel it's same as permuting 1 to n vertices over a straight line when edges can pass only above the line.

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

I came up with a unproven, long shot approach for C2. Basically, I calculated the expected value for $$$w_i$$$ after each step, and treated the result as the new initial weight. In other words I did the following $$$m$$$ times:

  1. Let $$$S = \sum\limits_{i=1}^nw_i$$$
  2. For each $$$i$$$, update $$$w_i$$$ to the following value:
$$$w_i = \begin{cases} \displaystyle w_i + \frac{w_i}{S},& \text{if } a_i = 1 \\ \displaystyle w_i - \frac{w_i}{S},& \text{otherwise}\end{cases}$$$

However, my maths aren't strong enough to understand why it doesn't work. I'm very curious though, because it sounds so intuitive. If someone could give me some clarity as to why it's wrong, I'd be grateful.

→ Reply