Educational Codeforces Round 54 [Rated for Div. 2]
By awoo, history, 6 years ago, translation, In English

On Nov/12/2018 17:35 (Moscow time) Educational Codeforces Round 54 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extented ACM ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov and me.

Good luck to all participants!

UPD: There certainly will be a discussion of the problems on the local Discord server shortly after the contest ends. I might join it as well)

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Anadi 7 266
2 HIR180 6 129
3 mrscherry 6 152
4 Vergara 6 158
5 Jeel_Vaishnav 6 185

Congratulations to the best hackers:

Rank Competitor Hack Count
1 teapotd 100:-4
2 vlad.raw 52:-5
3 MarcosK 32
4 tataky 28:-5
5 knotValid 23
721 successful hacks and 668 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A Dalgerok 0:01
B Nazikk 0:03
C neal 0:03
D tamref 0:14
E shadowatyy 0:13
F killer_god 0:34
G lxrvelory 1:03

UPD2: There was an error in problem D which caused some incorrect solutions to get accepted. We will investigate the number of users who were affected by this issue and decide whether the round is rated.

UPD3: We discussed the issue and came up with the following decision:

Those who got accepted earlier and get WA now won't be affected by rating changes. For everyone else (for those who got correct verdict) the contest will be rated.

UPD4: Editorial is out

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

Comments Comments (233)
| Write comment?
»
6 years ago, # |
  Vote: I like it +36 Vote: I do not like it

2 hours for 7 problems seem to be too less. Any chance extending the time to 2.30 hours? Specially for Educational Round, which should focus on having participants with low-mid ratings attempt more problems. C'mon beloved Codeforces! Give a thought.. :)

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

    "Specially for Educational Round, which should focus on having participants with low-mid ratings attempt more problems".

    Not really that's what Div. 3 rounds are for.

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

      Div3 rounds (both frequency and problem difficulty level) are inconsistent, Edu Rounds are still the best way to get introduced with ideas that can be used in broader extent.

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

    Most of the div2 people solve at most 5 of them anyway. Having 2h for 7 problems is good enough, since it gives a challenge for the better contestants too

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

      I'm saying just for education rounds though, the idea is to Educate, so why not give an extra half an hour?! That will surely benefit lots of programmers like me who are not yet to the level but trying to attempt and solve more problems than they usually do. There're lots of other div2 rounds where better contestants can be challenged by 2 hours time limit.

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

        Pretty sure the meaning of "Educational" rounds was lost a long time ago.

        Back when they started, educational rounds had classic problems which highlighted ideas and techniques that contestans should learn.

        Nowadays they are just normal contests with different rules ¯\_(ツ)_/¯

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

          Maybe they ran out of ideas and techniques that new contestants should learn...

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

    that's a good idea but maybe 2 hours make us want to try faster .. for me at my best I would solve 3 problems in less than 2 hours so it won't make that difference but it could for others so I agree with you

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

Hoping to get some plus ratings in this round :p

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

Lower, or lower and equal to 2100?

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

    educational round == div2 round sponsored by harbour space

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

    If your rating is equal to 2100 then your rating will not change no matter what.

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

Hi, guys, is it rated for me too?

I am participating after a long time and I have heard that some changes have been done in the divisions — div1,2 and 3. What are the rating ranges in these divisions and will my rating be affected if I participate in this contest? Thank you.

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

An Educational round after several bad contests, time to get new high rating.

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

69 ( ͡° ͜ʖ ͡°)

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

what is test 5 on E???????????????????

Why can't we see the test cases?

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

Why in E d can be>n?

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

There was an error in problem D which caused some incorrect solutions to get accepted. We will investigate the number of users who were affected by this issue and decide whether the round is rated.

I am really sorry :( Both bugs (in D and G) were mine.

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

    Screen-Shot-2018-11-12-at-19-49-01

    <3

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

    Why not consider it as a part of the hacking since Accepted here is not a final verdict because there is testing after hacking phase is finished

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

      Just imagine the number of people who attempted to other problems after submiting a wrong solution to problem D and its affection to the rankings...

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

        The tests aren't exhaustive, and Accepted doesn't necessarily mean your solution is correct.

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

      <3

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

    Isn't that the whole point of having hacking-phase or system tests?

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

    You are poset

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

    Please don't unrated. Please. :(

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

    Please turn on hacking phase to hack solutions with cout << 0 (to investigate the number of users who REALLY affected by this issue) and then run system tests.

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

    Such a noob

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

    Please don't be unrated

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

i submit code for problem D with just cout << 0 << endl; and get AC but good vertices in my code ans simple test 1 are different why??

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

NO!!! Plz be rated!!!! It's my first time to be MASTER!!! :(

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

    I was gonna be an expert too:(

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

    Poor you, bro. I hope this contest could be rated.

    How was your result today?

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

      After seeing that "cout << 0" passed all tests in D, it is really unnecessary to consider it should be rated or not:(

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

    I hope it's rated too.

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

    The same thing man, I can be expert for the first time in my whole life after 2 years of work, if this round will be rated, please let it be so.

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

Please don't unrate this contest.

Could we rejudge problem D or some accepted incorrect solutions?

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

    I don't think so...

    I myself didn't solve D, but there might be some guys with little bugs, who would have solved this problem after getting WA.

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

      How does correct checker guarantee that you will get WA for the little bug? The little bug is the most common reason for hacking

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

        It mustn't be that little you're thinking...

        Not everyone solve problem D in on try. But getting AC in pretest means don't working on it anymore.

        And the pretests was really weak, the guy posted above (alireza_kaviani) got AC with outputing only 0.

        → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it -7 Vote: I do not like it

Spoiler Alert:

In D, is it true to:

1- Find MST.

2- If n  -  1  <  =  k then we have reached the answer, otherwise, erase edges starting from leaves until the number of remaining edges equals k.

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

    I think it needs to be tree that grants minimum distances from the node 1 (like, dijkstra-tree)

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

      You're right. Dijkstra tree with the root at 1. Not MST.

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

      Thank you! I had forgot what MST represents, but have just remembered.

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

    Shouldn't it be shortest path tree rather than MST?

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

    Apply Dijkstra from source 1. Get tree with n-1 edges. Start removing leaves edges from that tree. Too bad I had a small bug in Dijkstra and could not submit on time.

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

      @MatPhySC what if # of edges in optimal paths is greather than K, dijkstra tree should answer less edges than the solution

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

        If I understood your question correctly than if K >= N-1 then answer will be Dijkstra tree because all vertices are good

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

          Sorry, poor english, but what i mean is that even when all vertices in Dijkstra tree are good, there could be another ones that belong to some other Dijkstra tree and they are also good edges

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

          consider this case: 3 3 3 1 2 2 1 3 1 2 3 1

          if i understood your solution, it should give 2 1 2

          however, 3rd edge is also good, at least the way i get the problem

          UD: i got it now, it's good vertices, not good edges

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

            There are two Dijkstra tree. You can consider any of them.

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

    Wrong solution:

    Consider the following case - 3 3 2 1 2 2 2 3 2 1 3 3

    Answer is — 2 1 3

    Answer from MST - 2 1 2

    Minimum distance from 1 to 3 is 3 units. MST gives 4 units distance from 1 to 3, so 3 is no more a good vertex.

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

    This will fail. Consider this tree. 1 2 1 1 3 1 1 4 1 2 4 1 There are multiple MST. But taking any MST other then 1,2,3rd edges. Will give WA.

    MST does not guarantee that all edges are at the minimum distance from vertex 1.

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

    Thank you all!.

    Beautiful problem BTW :D

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

    I don't think MST works. I got AC on this problem with SPT(shortest path tree). and maximum number of good vertices is min(n-1, k).

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

What is test 3 in D?

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

First time I wrote a buggy segment tree. :(

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

when I wondering how this guy passed D in 31 ms lol, lmao

I bet a lot of contestant will fail on D :|

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

I am sorry to be saying this but in my opinion it would be extremely unfair to declare this round as unrated because there would be many people who might not have done 'D' and have performed well in today's contest. If some incorrect solutions were accepted then it may as well be considered as a case of weak test cases. I urge you to consider the plight of many like me who believed they did well in today's contest and would be stranded disappointed if it is made unrated. PS Edit1: To all those who down voted this I am sorry to have hurt your feelings. I do respect your opinion and I totally accept that either of the scenarios I suggested would have been unfair. But the final decision taken by the contest makers is fair in everyone's eyes and no one loses out so I believe it is for the best.

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

    feel about those coders who cannot improve his D solution to get actual AC solution. because of he/she already get AC.

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

      I can understand that but that's also the case in many contests when your pretests get passed and your main tests fail. I understand that either decision would be unfair to some but it comes down to which one is more on the fairer side. It comes down to 1 question vs 1 contest and I believe that making it unrated would be more unfair.

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

        My solution on D is actually failing on pretest 2 but during contest it passed Now consider if the checker was correct i would have checked my code again and solved it after getting a WA.

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

          Yes, I understand it wasn't fair to you. I sincerely apologise for ranting out.

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

    To all those who down voted this I am sorry to have hurt your feelings. I do respect your opinion and I totally accept that either of the scenarios I suggested would have been unfair. But the final decision taken by the contest makers is fair in everyone's eyes and no one loses out so I believe it is for the best.

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

make it unrated omfg !!

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

    thats what you wont say when you did a heck good job today (or at least you think so). and the guys who got a crappy AC for that problem will get their ratings back to what they should have in the next contest or two ei?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      1. Your English is not understandable
      2. You have anime profile picture have a nice day :) :P :>
      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yeah i forgot most of the ,s and .s but yeah nice day too :D

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

    you didn't submit any solution for D lol

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

When will we know if our submission for D is correct or not?

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

Why can't simple dfs + 2 multiset pass problem E?

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

    I passed with a simple DFS and a vector of maps.

    Perhaps you got some bugs? Personally I wasted 30 minutes for not realizing I overwrote queries instead of accumulating those lol.

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

    Mine passaed 45632893 (After the contest and the code is probably bad)

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

rated plz!

Just fix the problem(s) of specialjudge.

And those best hackers will get everything done. ;)

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

In system test, the code that pretest is passed can be wrong, naturally. I think there is no reason that this round will be unrated. Moreover, this round is educational round and hacking can't be attempted in the contest. So this round wasn't influenced by something wrong.

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

    If our solution failed on pretests we will have time to make that solution correct. But now we can't do anything. So if round gets rated it will be unfair for all participants whose solution failed on D because of bug in checker. So round should be unrated.

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

      if your solution is this: then you obviously know your solution is wrong.

      and if its something different, how is it different then having very easy pretests if it passes sample correctly?

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

        My solution is not even close to this. And we can't assume all 36/37 pretests are like samples (in running contest).

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

      Same would be the case when pretests are weak. but we don't make it unrated in that case.

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

        36 weak pretests in D! We are not that unlucky

        → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it -9 Vote: I do not like it

Let's hit the unrated button.

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

PikMike said this in Discord server...

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

It seems that the special judge of problem D is incorrect. So I'm thinking about something like ummmmm.. unrated? In fact, I just wanna complain about the awful quality. Please check your contest more carefully.

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

Let's make it unrated

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

I feel that the contest should not be rated. Any opinions?

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

please make it unrated

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

    It say people, who get WA1 on D.

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

I'm wondering why my bruteforce solution on problem E could get Accepted... Can anyone explain why?

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

    Don't worry fam, it's no longer accepted now :)

    The answer to "why" it was accepted before is because pretests are never perfect.

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

Please keep it rated !!

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

please rated

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

So many people wanting the contest to be unrated are people who just did bad, not people who were affected by D.

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

OK ,The contest must be UNRATED!! ;)

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

I solved problems A, B, C, D and F. I was really happy with my results and now my D got wrong answer on test 1 (after the contest). I have A, B, C, F problems accepted, which worth less than A, B, C, D because solving A, B, C, D is faster than solving A, B, C, F. A similar problem was at round 485 (the queue froze during the contest): http://mirror.codeforces.com/contest/987 I lost 166 rating points there, I can't believe this is happening again. Instead of gaining points, I will lose :( Please make it unrated.

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

    If you got wa on even sample who is to blame really?

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

      I never check the 1st example, I don't get penalty if I get WA on test 1. And why would I check after it got AC?

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

I messed up, got stock on C god please make this unrated

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

Am feeling kinda stupid.... Anyways how to solve E ?

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

    Whenever you enter or exit any node, update BIT. I got that idea but implemented it with set instead of BIT during contest.

    solution: http://mirror.codeforces.com/contest/1076/submission/45630591

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

    You can do a simple DFS throughout the entire tree, starting at node 1 (i.e. root).

    Before starting, let's denote accumulated as an integer storing the sum of all added values for the current node. We'll get on with the way it worked below.

    When we start traversing from node z with depth depth, we'll do all these things:

    • Taken all queries that have z as subtree root, and add the x values of all those queries into accumulated.
    • Obviously, these queries don't apply for the entire subtree of z (only those with distance not larger than d). Therefore, we'll use a global array deactivated[] (more info in next steps). For each query with maximum depth allowed of d, add x into deactivated[depth+d+1]. Of course, since d ≤ 109, if depth+d+1 surpasses the maximum depth of the entire tree, ignore it.
    • As a result, we'll have to subtract queries from ascendants' query that no longer affect the current node. To do this, we simply subtract deactivated[depth] from accumulated.

    Then, accumulated will be the answer for vertex z. Store it and start running DFS like usual. When done traversing, remember to undo all the above steps before leaving the function.

    My submission, for further clarity: 45624305

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

We discussed the issue and came up with the following decision:

Those who got accepted earlier and get WA now won't be affected by rating changes. For everyone else (for those who got correct verdict) the contest will be rated.

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

    very well

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

      Please make it rated for those who use cout << 0

      It is clear that someone might get lucky enough to try it and get AC

      But it does not makes sense that many people were able to do it.

      It is clear that they clearly discussed the hack among themselves.

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

    Can you explain what was the issue clearly? Incase if the WA was on hidden pretest then maybe next time make it unrated for everyone having WA after final system tests too in all rounds?

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

      For some solutions in problem D that should be rejected the checking program answered that they are accepted.

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

        How many such users are there? I still fail to understand if a solution gives correct answer on sample tests and gives WA on some hidden tests whats the problem... How is it different from having weak pretests..

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

      The checker wasn't correct,

      It outputs ac if you just printed less than or equal to K distinct numbers from what i understand(even if you print 0).

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

    What about the people who are getting +ve rating change even after being affected by WA in D? It doesn't make sense to make it unrated for them.

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

    Make it like those who got accepted earlier and get WA now won't be affected by rating changes if their delta is negative. P.S. My delta shows positive by predictor

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

      How about being unrated for negative deltas?? Seems cool!!

      But just a question, the unrated people will be considered out of contest(unofficial) or not??

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

    Why “Those who got accepted earlier and get WA now won't be affected by rating changes” ? Why don’t we consider those are Accepted at the time it’s correct and ignore all submissons after that? This contest’s rule is ACM/ICPC, right? In ACM, it’s also rejudge as the way I mentioned. There is no ACM/ICPC contest skip a Accepted submission to judge final submisson in this case!

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

    Why different decisions for similar problem that happened in educational round 51?

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

      BledDest any comments?

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

        When there were only 10 contestants affected, it was easy to check them manually.

        When there are 500 of them, it is much harder since we can't automatically do it.

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

    You should take the "unrated" users out of the rating pool entirely (i.e. make them unofficial). Rating deltas are comparative: if somebody gains rating, someone else is supposed to lose it. If you just make the users not affected by rating changes, you'll have some users who influence the ratings of others but don't get their ratings influenced themselves.

    I hope what I'm saying makes sense, I don't really know how to express my idea.

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

D-Forces

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

It's my first chance to become master, I'd like to see it rated, but if the wrong make the contest unfair seriously, it should be unrated.

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

Can someone explain to me what I messed up?

http://mirror.codeforces.com/contest/1076/submission/45631931

It's just a dfs + 2 multisets. I must have looked over this more than 20 times. (I also put the updates to active/spent before and after the recursion, but that didn't do anything.)

Thanks in advance.

nvm solved, made stupid bug

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

Can someone explain me why this solution for problem A will fail ? http://mirror.codeforces.com/contest/1076/submission/45621631

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

    3 baz

    Your answer is ba when my answer is az.

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

    Deleting biggest one is not the solution check it 5 abcad

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

    Consider this case:

    3 bac

    Your code output "ba", while the correct answer is "ac".

    So, what you have to do is not removing the largest char in the string, instead you have to remove the first char s[i] such that s[i]>s[i+1], as this will result in smaller string.

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

Can someone explain me why I'm wrong? I made a submission to count number of good vertexes and with 50000 edges, one can't have more than 50001 good vertexes.

45607996 // the original one, from the contest 45632353 // the modified one

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

    The edges you give aren't necessarily connected. So you could have tree fragments everywhere. You have to do a dfs to get the edges and make sure they can actually reach the 1 node. (I might be wrong.)

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

      I'm using Dijkstra starting from vertex 1, so the graph is connected for sure

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

I submitted problem D 3 times.

In the second time, I get AC but the system said WA.

When rejudge, My second submission is changed (it exactly the same solution of prolem A). I think this is a bug of Codeforecs. Could you consider my case?

Submission number: 45627317

Before rejudge, WA on test case 3.

After rejudge, WA on test case 1, and the code is totally changed :( why ?

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

is your standing in the leaderboard affected by how many accomplished hacks do you have?

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

Please don't unrated, I probably become specialist after this round TAT.

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

    Don't worry, I think u can become specialist soon ~~~ fight!

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

weird behavior, according to my code it never can be N for 69 but here in cf it is showing N.

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

    Looked at your code — if you use the cin/cout speedup for C++, never mix them with printf/scanf — the streams are desynchronized so the output may not come out in the same order as you expect it to. That's what is happening here.

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

    You should look up what things do before you use them :)

    That #define timesave ios_base::sync_with_stdio(false); cin.tie(0);, isn't some magic fairy dust that you just sprinkle over your program to make it faster. It has some effects.

    To be more specific, ios_base::sync_with_stdio(false) means (as the name suggests) that you are disabling syncing between io with streams (the kind you do with cin and cout) and standard io (the kind you do with scanf, printf etc). You disable the sync, yet in your code you use both methods of io (you use cout for the "No" case and printf for other cases) and then expect them to be synced up.

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

Why “Those who got accepted earlier and get WA now won't be affected by rating changes” ? Why don’t we consider those are Accepted at the time it’s correct and ignore all submissons after that? This contest’s rule is ACM/ICPC, right? In ACM, it’s also rejudge as the way I mentioned. There is no ACM/ICPC contest skip a Accepted submission to judge final submisson in this case!

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

    The thing is that people could check their source once more if they knew that's wrong, but everyone usually stops at the AC verdict

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

    He meant, "those who got accepted due to the bug, and the same submissions got WA after rejudging".

    And for that, it's certain enough to say why it should be unrated (at least) for them.

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

      Thanks, bro. I know his mean now.

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

      Isn't is unfair to those who are getting positive delta but it will be unrated for them.

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

      Can you please proof the problem C ?

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

        It's a pure mathematical problem.

        According to the given formula, we can figure out , thus .

        You can draw the graph of the equation , and figure out a few things:

        • If d = 0, obviously a = b = 0.
        • If d < 4, no solution can be found.
        • If d ≥ 4, the function d = f(a) is a monotone function. Thus, you can binary search the value a, and b can simply be obtained as d - a. Keep in mind that your precision has to be right to fit the output's relative/maximum error criteria.
        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 2   Vote: I like it +5 Vote: I do not like it

          For the last case (d ≥ 4) no need for binary search, instead, solve the equation which is actually a2 - d * a + d = 0. After that, b = d - a.

          Simple.

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

            I feel freaking odd to deny solving this simple quadratic equation and binary searching the answer during contest time :D

            Well, whatever that works :D

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

if i did't got accepted, my rank will up. and now my rank won't up. sad :'(

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

And persons that haven't try the quest D? Is unrated or rated?

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

Yo yo dudes, come on, the ones who got affected should have their rating increased if it shows +, and nothing if it shows -.

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

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

just another [partial unrated educational round rated for div 2]

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

If I got D accepted with a wrong solution, but still managed to gain some rating after my D got WA, I do not see the point of why my rating should't increase.

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

How to solve C?

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

I spent a lot of time for D problem. And i have a nice score . Why my contest won't be rated. I don't do

printf(0);

I do bfs but my solution get wrong answer after rejudge. Please help me!!!.

It is not fair.

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

    You are so right. Why do you ban from contest. Don't accept question but it should be rated for all.

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

Can anybody proof me B problem, pleace

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

    If n is even, then the smallest prime divisor is 2. After subtracting 2 from it, n is still even, so the smallest prime divisor will keep being 2. Therefore, the answer is how many times you can subtract 2 from n, which is n / 2.

    If n isn't even, find the smallest prime divisor d. You do one subtraction and get to n — d. Now, d is most certainly odd, therefore n — d is even, so the answer for n — d (as described above) is (n — d) / 2. Counting the subtraction of d from the start, the total answer is (n — d) / 2 + 1.

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

"Those who got accepted earlier and get WA now won't be affected by rating changes. For everyone else (for those who got correct verdict) the contest will be rated."

This is unfair for the users with positive rating changes even with WA on D. Please see if there is an alternate solution for this issue.

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

Atleast make it rated for those getting +ve rating change, no matter if they were affected by D or not.

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

this contest should be rated for all those who got correct the 4th one but failed later..but still are getting their ratings better than before and unrated for the ones whose ratings would be decreased due to the 4th question.

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

Can anyone tell me how to solve problem D ?

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

    run dijkstra from vertex 1 to all other ones

    that gives you a tree of shortest paths

    all you need to do is remove leaf by leaf untill you have k+1 vertices (and k edges)

    it clearly maximizes the number of 'good vertices' and is always valid as well

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

Can anyone gives me a hint on problem E?

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

Can anybody please proof the problem C mathmatically. It would be greatly appriciated. Thanks :)

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

    • Consider a * b = a + b = d

    • we can get 2 equations for a , a = (a+b) / b = d / b and a = (a * b) — b = d-b

    • d / b = (d — b) -> b^2 — bd + d = 0

    so , we can use quadratic equation to get b , then a = d/b But if there is no valid answer from quadratic equation then answer is N

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

    We know:

    1) (a + b) ^ 2 = (a ^ 2) + (b ^ 2) + 2 * a * b

    2) (a — b) ^ 2 = (a ^ 2) + (b ^ 2) — 2 * a * b

    So we can calculate (a — b) ^ 2 as follows:

    1) (a — b) ^ 2 = (a + b) ^ 2 — 4 * a * b

    We know also that a + b = d & a * b = d.

    let A = d ^ 2 — 4 * a * d

    So we have (a — b) ^ 2 = A

    Now, in order for the problem to have answer, A must be positive. In case where A is negative simply output 'N'. In case it is positive, find it's square root and name it c.

    now we have to equations:

    1) a + b = d

    2) a — b = c

    So a = (d + c) / 2 & b = d — a

    After calculating the values for a & b check them. The problem wants a & b to be non-negative real numbers. So if either of them is negative then output 'N' and else output the numbers.

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

    By Vieta's formulas, we know that the sum of roots of the second degree polynomial ax2 + bx + c is equal to while their product is equal to . So if such numbers exist they will be roots of the polynomial x2 - dx + d.

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

why exactly did people try to submit solutions with cout << 0 anyway?

that feels just odd to me

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

Can someone please explain me why my answer is wrong for problem A in the shown test case? Input 1000 rkqggsabguejnkvqhflwqtndjqakicbgcirayhvustungfyjrvgvxdcpwaoyqmqrorxfjlmvqazvgqwbwkiwypcxclzhskvrjdxrgbanlngwymdlmgurflfvnersfqkwnsmsh...............

Participant's output rkqggsabguejnkvqhflwqtndjqakicbgcirayhvustungfyjrvgvxdcpwaoyqmqrorxfjlmvqavgqwbwkiwypcxclzhskvrjdxrgbanlngwymdlmgu................

Jury's answer kqggsabguejnkvqhflwqtndjqakicbgcirayhvustungfyjrvgvxdcpwaoyqmqrorxfjlmvqazvgqwbwkiwypcxclzhskvrjdxrgbanlngw..................

(why is 'r' being cut instead of 'z'?)

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

    Consider the simpler case:

    3
bac

    Output: ac

    Your code's output: ba

    You should delete the first character s[i] such as s[i] > s[i+1], not the largest character

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

Can anyone make me understand solution of D. Had a terrible round.

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

    My solution is based on dijkstra's algorithm from vertex 1. So while we're running dijkstra , i just pick the first K node(that is not 1) that we visit by dijkstra , if we were about to exceed K just break the loop. (FYI my dijkstra is implemented in a while loop with a priority_queue as the main data structure , you can see the submission from my profile.)

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

    Actually Dijkstra process built a shortest-path tree with N vertices from the graph. So we will build that tree, and repeat this N — k — 1 times: Find a vertex that is a leaf and delete it. This process make sure all the current vertex of the tree has as same shortest distance from vertex 1 as it was before the deletion, and the number of these vertices is largest. This can be done with dfs

    You can make the deletion simpler, by dfs the shortest-path tree and build a subtree of k edges. Here is my submission 45633192.

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

How to solve problem G ?

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

Was the contest unrated for all..as my rating has not been increased.

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

So we have just eliminated everyone affected by D... what?? This is just so stupid. Someone who has done E or F and whose rating might be +100 would be unfair for them!! Make it rated for those with +ve rating change please.

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

" Those who got accepted earlier and get WA now won't be affected by rating changes. For everyone else (for those who got correct verdict) the contest will be rated. " — What if the those contestants will get a higher rating if we skip D submissions of those users?

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

My rating still hasn't changed, is everything fine? I haven't touched D at all.

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it -11 Vote: I do not like it

deleted

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

For those who got TLE on test 64 on D: When implementing Dijkstra, do not check edges from a vertex if it is already visited (in other words, if the distance from the PQ is greater than the one written in the distance array). A vertex can be pushed into the PQ O(V) times and it also can have O(V) outgoing edges, so it can be O(V^2) in the worst case. Furthermore, this can be repeated for multiple vertices and possibly reach O(V^3) in a complete graph.

The generator is:

#include <cstdio>
using namespace std;

int main()
{
	int n = 200003, m = 300000, k = 0;
	printf("%d %d %d\n", n, m, k);
	for (int i = 2; i <= 100000; i++)
		printf("%d %d %d\n", 1, i, i);
	for (int i = 2; i <= 100000; i++)
		printf("%d %d %d\n", i, 100001, (int)1e9 - 2 * i);
	for (int i = 0; i < 100002; i++)
		printf("%d %d %d\n", 100001, 100002 + i, (int)1e9);
}
→ Reply
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

This is unfair to me. Predictor was showing I will get +50 rating. But now this became unrated for me. This is unfair...ummmmmmmmm

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

Is there a way to look up what test was used to hack my solution, in case I want to debug?

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

Is there editorial?

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

For E is it possible to build some type of tour so that we can use segtree for range update and then push all the changes?

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

i was wondering how setters managed to change the rating based on a particular problem's verdict... is it a database sort or ??

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

Why TLE on Test Case 64? problem D

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

I think in "Meme Problem(C)" float and double will give different answers. Both the answers shall be considered valid since logic is same. If programmer is able to give any one of them it implies his/her logic is sound.

→ Reply