Блог пользователя ouuan

Автор ouuan, история, 5 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +421
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +141 Проголосовать: не нравится

Wish everyone have fun!

»
5 лет назад, # |
  Проголосовать: нравится -32 Проголосовать: не нравится

hope short problems and high rating!

»
5 лет назад, # |
  Проголосовать: нравится +85 Проголосовать: не нравится

Friendly time to Chinese!

»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Time :)

»
5 лет назад, # |
  Проголосовать: нравится +108 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

Which problem will have two subtasks?

»
5 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

Hope my name to become orange again qwq.

»
5 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +44 Проголосовать: не нравится

    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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -21 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +209 Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

Chinese editorials? Cool!

»
5 лет назад, # |
  Проголосовать: нравится +76 Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

long live china , I love all Chinese

»
5 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

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!

»
5 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

This round is so friendly for Chinese QwQ

Let's have fun in this round QwQ

»
5 лет назад, # |
  Проголосовать: нравится +157 Проголосовать: не нравится

I am ready to face data structure problem !

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

»
5 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Chinese round =earlier time

»
5 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

»
5 лет назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +154 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +108 Проголосовать: не нравится

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
»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

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!

»
5 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

repeat the math)

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could we view the problems in Chinese?

»
5 лет назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

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! ;)

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится
      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
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

why not show us the scoring distribution?

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится -12 Проголосовать: не нравится

Bruh!

»
5 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

How to solve div 2 C?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

  • »
    »
    5 лет назад, # ^ |
    Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

Mathforces...

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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

»
5 лет назад, # |
Rev. 4   Проголосовать: нравится +61 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Real Mathforces...though I expected some data structure

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

How to solve Div2 c ????

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

»
5 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +66 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

How to solve div2D?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      proof?

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится +28 Проголосовать: не нравится

        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.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Could you please explain how this works?

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +28 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

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
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
5 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

dishonest guys:

div2C:

55261994 I_love_HellHoleStudios (link to reformatted code: link)

55261355 Zzzyt

»
5 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +37 Проголосовать: не нравится

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?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +81 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +23 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

»
5 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    What is the proof of D's solution

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +75 Проголосовать: не нравится

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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

      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.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +25 Проголосовать: не нравится

      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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can anybody explain Div2 B, pls

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    thanks

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

»
5 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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

»
5 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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

»
5 лет назад, # |
  Проголосовать: нравится -34 Проголосовать: не нравится

another mathforces round

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Now I know my brain is made of rubbish.

»
5 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can anyone plz explain how to solve c in simple words

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone share the solution of div2C?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 ?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.