ouuan's blog

By ouuan, history, 12 days 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, Sooke, QAQAutoMaton, ODT, ccz181078, rushcheyo and PinkRabbit.

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

  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
  • +389
  • Vote: I do not like it

»
12 days ago, # |
  Vote: I like it +141 Vote: I do not like it

Wish everyone have fun!

»
12 days ago, # |
  Vote: I like it -32 Vote: I do not like it

hope short problems and high rating!

»
12 days ago, # |
  Vote: I like it +85 Vote: I do not like it

Friendly time to Chinese!

  • »
    »
    12 days ago, # ^ |
    Rev. 2   Vote: I like it +92 Vote: I do not like it

    It's Happy DuanWu Festival match

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

      happy DuanWu Festival to all the Chinese

  • »
    »
    11 days ago, # ^ |
      Vote: I like it -47 Vote: I do not like it

    But bad time for people

    • »
      »
      »
      11 days 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

    • »
      »
      »
      11 days 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

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

Time :)

»
12 days 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!!!

»
12 days ago, # |
  Vote: I like it +33 Vote: I do not like it

Which problem will have two subtasks?

»
12 days ago, # |
  Vote: I like it -15 Vote: I do not like it

Hope my name to become orange again qwq.

»
12 days ago, # |
  Vote: I like it +19 Vote: I do not like it
  • »
    »
    12 days 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.

  • »
    »
    11 days 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.

»
12 days ago, # |
  Vote: I like it +41 Vote: I do not like it

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

  • »
    »
    12 days 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

»
12 days ago, # |
  Vote: I like it -7 Vote: I do not like it

Chinese Round! Happy Dragon Boat Festival!

»
12 days ago, # |
  Vote: I like it -9 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it +209 Vote: I do not like it

»
12 days ago, # |
  Vote: I like it -11 Vote: I do not like it

Chinese editorials? Cool!

»
11 days ago, # |
  Vote: I like it +76 Vote: I do not like it

»
11 days ago, # |
  Vote: I like it +31 Vote: I do not like it

long live china , I love all Chinese

»
11 days 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!

»
11 days 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

»
11 days 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

»
11 days 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! :)

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Chinese round =earlier time

»
11 days 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 ... :/

  • »
    »
    11 days 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 :)

»
11 days ago, # |
  Vote: I like it -13 Vote: I do not like it

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

»
11 days ago, # |
Rev. 2   Vote: I like it -14 Vote: I do not like it

DuanWu كل عام و انتم بخير بمناسبة حلول عيد ال

أعاده الله علينا بالبركات

Trans :

Happy DuanWu Festival

»
11 days 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.

»
11 days ago, # |
  Vote: I like it -23 Vote: I do not like it

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

»
11 days 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.

»
11 days 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
  • »
    »
    11 days 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.

  • »
    »
    11 days 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.

»
11 days 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!

»
11 days ago, # |
  Vote: I like it +18 Vote: I do not like it

repeat the math)

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Could we view the problems in Chinese?

»
11 days 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!

»
11 days ago, # |
  Vote: I like it -20 Vote: I do not like it

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

»
11 days 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 .

»
11 days 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.

»
11 days 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.

  • »
    »
    11 days 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. ;)

»
11 days 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! ;)

  • »
    »
    11 days 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!

    • »
      »
      »
      11 days 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
      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        Oh, I use the mirror by mistake again..

»
11 days 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.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 days 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.....

»
11 days 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?

»
11 days 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

»
11 days ago, # |
  Vote: I like it +12 Vote: I do not like it

why not show us the scoring distribution?

»
10 days ago, # |
  Vote: I like it -11 Vote: I do not like it

How should I register? I haven't registered yet and so not able to submit.

»
10 days ago, # |
Rev. 2   Vote: I like it -12 Vote: I do not like it

Bruh!

»
10 days ago, # |
  Vote: I like it +15 Vote: I do not like it

How to solve div 2 C?

  • »
    »
    10 days 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.

    • »
      »
      »
      10 days 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?

      • »
        »
        »
        »
        10 days 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.

  • »
    »
    10 days 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 :(

  • »
    »
    10 days 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, ...

  • »
    »
    10 days 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).

»
10 days ago, # |
  Vote: I like it -9 Vote: I do not like it

Mathforces...

  • »
    »
    10 days 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...

  • »
    »
    10 days 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.

    • »
      »
      »
      10 days 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

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ABC can be worked out on paper, just think about the problem and write it down and the rest is implementation.

    I complain about mathforces only when I have to use advanced math formulas and tricks that I would have knowledge of only if I was a math olympian or something like that.

    Some basic math involved into implementation is perfectly fine by me, in fact, it is necessary to produce fun problems.

»
10 days 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

»
10 days ago, # |
  Vote: I like it +11 Vote: I do not like it

Real Mathforces...though I expected some data structure

»
10 days 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.com/contest/1173/submission/55271422

  • »
    »
    10 days 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

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What do you mean by binary search number of zeros ?

      • »
        »
        »
        »
        10 days 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.com/contest/1173/submission/55269800

»
10 days 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
;(

»
10 days 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?

  • »
    »
    10 days 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

»
10 days ago, # |
  Vote: I like it +66 Vote: I do not like it

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

»
10 days ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve div2D?

  • »
    »
    10 days 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.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

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

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

      proof?

      • »
        »
        »
        »
        10 days 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.

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

      Could you please explain how this works?

»
10 days 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 stO'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..

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

    Why sorry?

    • »
      »
      »
      10 days 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..

»
10 days 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

»
10 days ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
10 days 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
»
10 days 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.

»
10 days 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

»
10 days 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?

  • »
    »
    10 days 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.

»
10 days 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?

  • »
    »
    10 days 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).

    • »
      »
      »
      10 days 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.

      • »
        »
        »
        »
        10 days 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$$$.

    • »
      »
      »
      10 days 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.

»
10 days 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 ?

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

    What is the proof of D's solution

  • »
    »
    10 days 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.

  • »
    »
    10 days 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 :/

»
10 days 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.

  • »
    »
    10 days 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.

    • »
      »
      »
      10 days 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.

    • »
      »
      »
      10 days 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.

»
10 days ago, # |
  Vote: I like it -8 Vote: I do not like it

I think i am out of competition.o(╥﹏╥)o

»
10 days 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." ;)

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody explain Div2 B, pls

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    After observing some test case, you can find that for say ith chess at coordinate (xi,yi) we can put it in (xi+1,yi) or (xi,yi+1) and it will satisfy the distance condition for all it's previous chess pieces, now following this you can construct the answer. :-)

  • »
    »
    10 days 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).

  • »
    »
    10 days 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

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks

»
10 days 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?

»
10 days 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.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

This was a really good one. Appreciate the writers. For a beginner like me, those problems gave me a lot of insight. :)

»
10 days 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.

  • »
    »
    10 days 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

»
10 days 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?

  • »
    »
    10 days 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.

    • »
      »
      »
      10 days 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

»
10 days ago, # |
  Vote: I like it -34 Vote: I do not like it

another mathforces round

»
10 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Now I know my brain is made of rubbish.

»
10 days 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.com/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

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the editorials be released?

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone plz explain how to solve c in simple words

  • »
    »
    10 days 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.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone share the solution of div2C?

»
10 days 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 ?

  • »
    »
    10 days 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)

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for the super speedy tutorial !!

»
10 days 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

»
10 days 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 ??

  • »
    »
    10 days 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.

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

      Great explanation

      Thank you so much sir

»
10 days 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?

  • »
    »
    10 days 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.

    • »
      »
      »
      10 days 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.

      • »
        »
        »
        »
        10 days 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.

»
10 days 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.

»
10 days ago, # |
  Vote: I like it -13 Vote: I do not like it

I think the div1E is difficult to write in two hours(Especially for me)

Even the standard code is so long……

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey guys, I have made a new app Coding List which keeps you updated with all live, upcoming programming competitions from hackerearth, kaggle, codechef, codeforces, topcoder, aigaming, hackster, codinggame, hackerrank, projecteuler, atcoder and many more.

A must have app for programmers. Please rate and review it. Try it here https://play.google.com/store/apps/details?id=io.github.vikasgola.coding_list