vovuh's blog

Codeforces Round #611 (Div. 3)
By vovuh, history, 5 years ago, translation, In English

Pay attention to the unusual round start time.

UPD: We cannot determine difficulty of some problems thus we recommend you to read all problems and think about each of them.

<almost-copy-pasted-part>

Hello! Codeforces Round 611 (Div. 3) will start at Dec/28/2019 20:05 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria nooinenoojno Stepanova, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</almost-copy-pasted-part>

UPD2: Editorial is available!

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

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

![ ](mem2)

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

Three back to back contests today — AGC 041, Codechef December Lunchtime, CF Round 611. GLHF!

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

When I registered for this round my rating was less than 1600. But will this round be rated for me if my rating become 1600+ before starting the round (after updating rating based on Educational round 79)?

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

??????THE BEST HAKER?????

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

Funny magic！

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

Huh, really friendly time for us:

For Chinese users.

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

Before yesterday's contest, I had a rate of 1599 and it was planned to have 0 rate change so that I could participate in today's div3 contest, and yes I am 1599 again :D

My plane now is to get +100 rate change, Can I achieve my goal again? :3 I hope sooooo

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

vovuh always have good contests so I hope it will be one of them. good luck everyone :D

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

![ ](cf)

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

Some experts are listed as official participant. Please fix it.

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

    Checkout the magic option at your profile page. You can change your color from there (I am not an LGM :3). This feature gets activated around each new year. Maybe they are not experts, they just changed their color :3

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

What does the post mean by "Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes." Does this mean 10 minutes is taken off your clock for a wrong submission?

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

    yes (A wrong submission adds to your time penalty).

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

      I took part in a competition yesterday that also had this penalty and nothing happened to my time when I submitted a wrong solution, what was happening there?

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

        I checked your results in the last contest, your total time without counting the penalty for wrong submissions is 39 + 15 = 54. You had 3 wrong submissions -> 3 x 10 = 30. Therefore your total time penalty is 54 + 30 = 84 (This number is shown under penalty in the standings).

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

          Oh i thought it meant you would have 10 less minutes to do the problems.

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

    No! This mean that your penalty is increasing by 10.

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

0h5 — 2h5 AM I'm here :(( but i will try participate.

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

UPD: We cannot determine difficulty of some problems thus we recommend you to read all problems and think about each of them.

Hmm, something's fishy.

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

    At last the fishy thing was Task-C. Weak pretests and some solutions don't make sense

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

      Near one third of the solutions for c were hacked (including mine:( )

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

Today's leaderboard will be colorful :)

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

    You're definitely misleading people with that photo...

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

The announcement for E was very late Costed me 2 wrong submissions Pls look into it

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

    "For example, let the initial positions be x=[1,2,4,4]. The final ones then can be [1,3,3,4], [0,2,3,3], [2,2,5,5], [2,1,3,5] and so on. The number of occupied houses is the number of distinct positions among the final ones."

    You could infer it from the statement.

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

      Still the statement was pretty unclear. Look at statement now, its perfect

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

Nice F, thanks)

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

numberline forces

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

I couldn't understand problem F completely. Can someone clarify it more ?

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

Difficulty : A < B < C << D,E << F

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

    I think E was a lot easier than D in Implementation. Though getting the idea was the main thing.

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

what is the 4th/7th/11th test case in problem E? or what can it be?

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

    Yes I was also geting WA on tc 4 with my without DP approach I dont know what is wrong

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

    try these cases:

    5
2 3 3 3 4

    ans: 1 5

    9
1 1 2 3 4 6 7 8 9

    ans: 3 9

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

Great Contest. Managed to solve 4 problems.

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

How to solve D within the time limit?

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

    Greedy problem using a priority queue (min heap) and a flag checker.

    you can keep minimum distances in the queue

    For example, n = 2, m = 3, x1= 1, x2 = 5 Then initially, you need to push (0, 1) and (0, 5) // (dist, position) and set(1) = visited and set(5) = visited

    If -pq,top.first != 0, then add this position to your answer array. and check whether you can insert position+1 and position-1 with your checker. If position+1 is possible, then push(-(dist+1), position+1)

    until you gather m position

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

      I did the same thing nearly but got wrong answer on test 3. Is it because of unordered map? It would be great if anyone can help me find my mistake!! my submission Thanks .

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

E was dp or greedy ?

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

    dp i maintained 3 states, first calculate frequency array for input from 0 to n+1 and if it is greater than 4 make it 3 States are as follow: 1) idx : index of location or houses 2) x : number of friends previous location is asking to me 3) y : number of friends i will give to next location

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

    Greedy af

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

Can we use bfs to solve problem D? i always get memory limit exceeded on test 12 :(

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

1283E - New Year Parties is similar to 1203E - Boxers .-.

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

    I would say it is half-similar :) Btw I cannot understand how didn't I remembered this problem, lol.

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

    Except for the fact that we couldn't go from 1 to 0 in the old problem

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

Thanks for the contest!

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

I had an hour after solving C. I looked D and thought set+pq naive. But I thought it's not the model solution, and gave up. 10 minutes left, I started to code naive, and I've done it after contest. Submit it, AC.

wtf

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

    this happened with me in E , i solved very late and forgot to memoize the dp.Till then i memoize it time was over :(

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

$$$F$$$ was cool. Here's a fun fact: You can prove that number of trees in $$$n$$$ vertices is $$$n^{n-2}$$$ if you have a working algorithm for $$$F$$$!

Your algorithm is deterministic, so it generates exactly one output for each input. Also, as each output corresponds to a unique ordering of edge importance, each output will correspond to exactly one input. But number of different inputs with $$$n$$$ vertices $$$= n^{n-1}$$$ and number of different outputs $$$= nT(n)$$$ where $$$T(n)$$$ is number of undirected simple graphs in $$$n$$$ vertices which are trees. (We are multiplying by $$$n$$$ because same graph with different roots are considered distinct in the output.) Thus, as inputs and outputs have a bijection, $$$n^{n-1} = nT(n)$$$. Thus, $$$T(n) = n^{n-2}$$$!

This is kinda similar to other proofs of Caylee's formula like Prufer Codes and proof of Caylee's formula by double counting.

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

Can someone help me figure out what is going wrong in my submission for Problem E 67835042. Thanks in advance.

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

HOW TO SOLVE E? PLS EXPLAIN IN BRIEF!

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

    Max can be computed by sorting the array and greedily shifting elements as left as possible to maximise the houses occupied. My logic is going wrong on min (So I don't know)

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

      There is also a possibility of you shifting to the right

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

Why should C problem this submission 67826496 should be ac? Something wrong with the judge program?

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

What are the hacks for C ?

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

I really liked this Div $$$3$$$ contest because

  • The difficulty balance was decent. It was not too difficult, yet not too easy.
  • The problems were not very implementation based (like $$$598$$$ for example). After getting the basic idea, it was easy to implement it.
  • There were no subtasks

A great Div $$$3$$$ Contest to end the year !

mango_lassi I generally refer your solutions. How to solve $$$F$$$ ?

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

In C, can we also change the value which is not 0 ?

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

problem D I used unordered_map but I got TLE. I instead of map is AC??? why? I think umap is faster than map. please explain for me, thanks!

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

    I had the same issue!

    https://codeforces.me/contest/1283/submission/67820013. Here you can see my first implementation using unordered_set. This submission received TLE on test case 6.

    https://codeforces.me/contest/1283/submission/67838787. AC submission. In this submission I only changed the unordered_set to set.

    Initially, I thought that this discrepancy was due to unordered_set having a very large constant factor, but the strange thing is that it seems that in general, unordered_set performs better than set for this implementation. For example, in test cases 3, 4, and 5 (which all have very big n), the unordered_set implementation has about 1.5 to 2.5 improvement over set in runtime. It seems that test case 6 is an outlier where unordered_set performs at least 5x slower than set.

    I didn't know that unordered_set could be exploited. Is there a different reason that this may be happening?

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

    umap uses an inbuilt hash function to map the values and as you all know that hashes are collision prone hence that TLE you got.umap is O(1) as long as it doesn't face collisions but as collision increase its complexity turns O(n), it's basic knowledge.

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

      everything is basic for future LGMs

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

        Its sad to see that we lost a one and only n(b)oobita of ours :(

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

      Thanks, I had never gotten into this kind of situation before, so I was thinking the inbuilt hash functions are really efficient XD , I will be avoiding unordered stuff from now onwards XD

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

        There is a chilli hash which i dont remember but is known to be quite efficient so its recommended to use chilli hash when using unordered map. IDK if any hacks of it have been found yet though

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

    Yeah, because unordered_map can have a lot of collisions because it's implemented as a hash table...

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

For all who is surprised by why this was the accepted solution: I am surprised not less than you. Thank you badcw for noticing this.

I will try to explain why this happened: when I wrote the checker I forgot to check the stupidest thing — check that all $$$nf_i = f_i$$$ for such $$$i$$$ that $$$f_i \ne 0$$$. I don't understand how could I forgot to do this, but this happened. As you can understand, nobody noticed the mistake and during the round nobody informed me about such weird thing. The comment above is the first source where I found this issue.

I'm very sorry about my stupidity and I didn't want to ruin your fun from participating in this round. I apologize to everyone who was and will be affected by this mistake. I know that MikeMirzayanov who is the (usual) author of the whole problemset is upset by this fact and I understand that many of you are also upset by this fact. Now I cannot do anything with it and can only apologize.

We will make a decision to make or not make this round unrated a little bit later and will inform you as soon as possible.

P.S. I can't even imagine how many participants can be affected by this issue and I'm so scared to find out it :(

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

    Rated!

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

    It appears the person who you linked got hacked. Did anyone else get affected by this error?

    If not, even if there was an error in the checker, nobody really got affected. I don't think the round should be unrated in this case.

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

      In fact, all my checker does is check if the printed array is a permutation without fixed points. So any solution that prints any permutation without fixed points can be accepted. And, as I can see, we already had 400+ hacked solutions and... further — more.

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

        Just out of curiosity, are most of the hacks occurring because of incorrect checker, or just because there was some case that people failed to check/some wrong idea that would have failed even with correct checker?

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

          I cannot check all 550+ hacked solutions (wow, 150 hacks during several minutes) by hand but I think that there are not so many people who wrote absolutely incorrect solution on purpose. I think many hacks are because of some special cases, but because of incorrect checker it can happen that these cases appear in the test data but checker just didn't checked them.

          And the second issue I forgot about (but compared to the incorrect checker this is a small issue): almost all 15 tests I add are useful, but this is not enough to cut off all incorrect ideas and possible bugs. I forgot to add test cases to this problem. But because of the checker it does not matter now.

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

            So the issue is that the incorrect checker just made pretests weaker?

            Because people who passed weak pretests still ended up getting hacked, so the checker didn't make incorrect solutions become correct.

            In that case, no round should be unrated because of weak pretests. If that was true, CodeCraft should be unrated every year.

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

              Yes, the mistake of the checker was false negative (correct me if I'm wrong in the terminology) (accept some incorrect solutions, but not vice versa).

              But I don't sure we can say that this issue can be reduced to "bad pretests" because at least the solution I linked above cannot even pass the first example.

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

                So this is the reason of so many hacks going on, thanks for confirming that anyways

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

                Nope it's false positive. falsely label wrong solutions as right.

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

                That's fair.

                I still don't believe it should be unrated, because at least people could check sample, but it would definitely make sense if it was.

                Thank you for confirming the issue.

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

            We cannot even see the test case on which our solution failed. I even don't know the corrected checker is working fine or not.

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

              Resubmit your hacked solution and you will definitely see the error in the output (and in that way you can make sure that the checker works fine now).

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

                I didn't wrote wrong solution on purpose for problem c ! but if known during the contest I would have changed code ! submitted my code again and it shows WA on test 17 ! It's unfair. Please keep the round unrated !

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

                  @_@ your solution is WA :)) this case, you distribute into slot but don't check index == value :)) not relative!

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

                nvm

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

                  I think your solution will be rejudge :3

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

    I think you should make it unrated for only affected people, so every one wil be satisfied :D

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

      The total amount of rating changes should be zero if I get it right, so everybody will be affected.

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

        Rating is negative sum game, but your point still holds.

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

        No it's not necessary.

        The same thing happened in codeforces round 601 and they made a form for the affected people.

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

      i solved abcde at the time of the contest but i've got c hacked. Despite that, i don't want that the round be unrated for me.

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

    Will hacked solutions be rejudged?

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

      Read this comment. All solutions that which are hacked are already "rejudged" in some way (after the checker fix).

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

        Sir, Please let the round remain rated as the ones who got C accepted by wrong means will be hacked by the end of hacking phase.

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

          yeah. I would love to end the year at blue rating

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

    Rated!! It isn't the checker's fault if people randomly submit without testing sample cases.

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

    vovuh you are a lucky guy! The round is rated!

    Only 15 official participants have been affected noticeably by the issue in the problem C checker: I reviewed all the verdicts after the final testing and found such submissions that failed on the examples (but didn't fail on them while the contest). Only 9 of them have non-positive rating changes. So I excluded all of them from the official participants. They are:

    Miracles happen! Happy New Year!

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

      Thank you! You can imagine how glad I am when I got the top 750 for the first time and it's rated @@

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

      I got stuck in C for about an hour and you just saved me from getting -100!
      Thank you so much MikeMirzayanov and Happy New Year!

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

My approach for problem C is to sort the array containing not_occupied position. Iterate from 1 to n and if at any i ar[i] is 0 and i!=maximum_not_occupied_position ar[i] = max_not_occupied_position else ar[i] = min_not_occupied_position.

Still my soln gets hacked what is the counter case please tell

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

in problem 3. if we print n 1 2 3 4 . . . n-1; for all n. will it be correct solution ??

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

Can we hack randomized solutions for C? https://codeforces.me/contest/1283/submission/67811299

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

    The probability that a random permutation is a derangement is approximately $$$1/e$$$, and that is dense enough for randomised solutions to work.

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

What is the correct way to solve C ?

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

    You can maintain two sets:

    The one which are bad positions set (i.e Index = unfilled element in array) and the other good positions set(i.e are missing from array but no problem as their value != unfilled_position in array)

    Now, you just need to handle the bad positions set first.

    I did it in the following way, there can be various other ways.

    for example, if my array was 3, 4, 6 of bad positions. I would circularly assign positions, example a[3] = 4, a[4] = 6, a[6] = 3;

    and for the remaining 0's positions, you can assign as you wish from good_position set.

    Here is my submission — https://codeforces.me/contest/1283/submission/67828215

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

    I listed all the ones who did not give gift and all the ones who did not receive gift. sorted these 2 lists.


    compare a[i] and b[i] 

if equal:

swap a[i] and a[i+1]
5
2 1 0 0 0

a=[3,4,5]
b=[3,4,5]
i=0
a becomes [4,3,5]
i=1 
a stays the same
i=2
a becomes [5,3,4]
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      When i==1, swap shouldn't happen as now a[i]!=b[i] ?

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

    Let s be the set of people who didn't give their gifts yet. Let t be the set of people who didn't receive their gifts yet.

    For every person in s, assign to him any person (different from him) in t. Note that this is possible for all people in s except the last one (If we assign greedily). However, it's guaranteed that at most 1 person will be assigned to himself. Assume this person p exists. To fix this issue, choose any person (!= p) in s (This is guaranteed since it's given that the size of s is at least 2) and swap his answer with the answer of p. Done :)

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

Hello everyone... I need help >_<. Can anybody check what's wrong with my solution of problem C if you don't mind. (Although it's already hacked xD, but I don't know how to see the test case) https://codeforces.me/contest/1283/submission/67820446

I'm trying to figure out the correct way to solve this. Thank you!

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

    Already found my mistake. :"D

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

      Can you tell me on which testcase your code is going wrong as my solution for problem C is also been hacked but still I'm not getting my mistake. Thank You!

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

This should happen with me too

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

Very nice contest with interesting problems. Thank you vovuh.

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

Can anyone here tell why using unordered_set is giving me TLE on D , where as using only set is passing the tests?

unordered set solution,
set solution

the unordered set soln was working fine until test case 5, which is of same order as test case 6, but giving TLE in test case 6;

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

same E from past div3 round https://codeforces.me/contest/1203/problem/E

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

The procedure in F defines a bijection between set of all trees with labeled $$$n$$$ vertices with one vertex picked and set of sequences of length $$$n - 1$$$ with entries from $$$[1, n]$$$, which proves, that there are $$$n^{n - 2}$$$ labeled trees with $$$n$$$ vertices. Really nice :).

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

Press F for vovuh :(

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

For C task, were we aloud to change spots that weren't 0 or not? Cause the task says we need to fill in spots that have 0s in them, but during hacking phase I saw a solution that just printed sequence 2 3 4 5 ... n 1 (which was accepted).

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

Can someone help me find the reason why my submission for problem D get TLE on 12, and it's memory is too large, it works pretty fast before test 12.

67830125

Thanks in advance :)

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

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

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

Problem D is a beautiful application of all-sources BFS.

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

How to solve F?

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

Code Can Someone help I am getting WA on testcase-19 of Problem E

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

How to find the first answer in problem E?

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

Can someone provide an explanation to the greedy solution for task E. I am able to calculate the max value ; however I am slightly missing something while calculating the min value

Why Am I saying SLIGHTLY MISSING can be found looking at my answer and jury's answer to the failing test case

I think there is maybe some more ways to merge than I have taken into account. A deeper insight on the greedy approach to the problem would be appreciated. Thanks in advance.

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

      well first of all thanks for the reply. But isn't it invalid input as numbers need to be less than or equal to n ( Mentioned in input format )!

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

        Yeah. I didn't notice it. But it doesn't matter.

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

          Oh thanks now I get it. Basically I am seeing 2 and 4 first ; dragging them to mid 3 ; and thus we will be left with 1 5 and lots of 10s.

          Then that 1 5 increases the answer. The first thing that is coming to my mind is switching the order in which I wrote down the conditions. I don't know whether that will work or not... but I am going to try that.

          Update : Oh ; that also fails. Now I need to do something clever I guess...

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

          Could you give me some hints on :

          1 : How could I correct that. 2 : How did you come up with that test case. I mean your thought process while test case design !

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

    well i was stuck on max so i used your idea and got AC. here is what I did for min:

    sort array and remove duplicates in array



    last = -2
for( i=1;i<array.size();i++) 
    if x[i]-last >1 :
        x[i] += 1
        last = x[i]
    
    else:
        if x[i] - last ==1:
            x[i]-=1
            last = x[i]

    then you count all unique numbers

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

    Update : Done ! Code : https://codeforces.me/contest/1283/submission/67847724

    Special Thanks to stefdasca and tribute_to_Ukraine_2022 for providing valuable inputs whether related to test cases or the code/approach itself !

    I think stefdasca's idea to find min is really really simple ; both to think and prove ; those benefitting from this discussion should really look into his code https://codeforces.me/contest/1283/submission/67847914

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

I see too many hacks for C...wonder why??

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

Code

Could anyone tell me what problem is in my code? (min part)

I merged 3 consecutive values to center one. (I marked flags)

And then I merged 2 consecutive values to right one. (I marked flags to avoid a wrong move)

Finally, I merged possible (exist none exist) cases to the center(none).

Thank you for helping me!.

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

Here is my solution for problem C. It is been hacked but still I'm not getting any testcase where it is going wrong. Can anyone please look into my code and say where will it go wrong!

67816712

Thanking you in advance for your help

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

    6
    6 0 2 0 3 1

    i don't know what the problem is, but here is a wrong test case.

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

Is the round rated?

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

Really weak pretests :(

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

So what's the result after about 12 hours of discussions. Is it rated?

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

    Yes, only 15 official participants have been affected noticeably by the issue in the problem C checker. The ratings will be updated in 10 minutes. I unrated all the participants from this list who has non-positive rating change.

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

My first 1700+ !!

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

I hacked 7 people in open hacking phase but still didn't get any positive response on my rating or my total score, isn't it weird ??[user:vovuh][user:MikeMirzayanov]

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

Nice contest, especially F problem))))

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

    I understand that there are n lamps and n-1 wire And you need to chooce a root lamp and every lamp can connect max 2 other lamps.

    What is the required, can you clearfiy it a bit ?

    → Reply