VK Cup 2017 Round 1 and CF Round 405 div1+div2
By Errichto, 8 years ago, In English

Hello.

The round 1 of VK Cup 2017 will take place on March 18 at 18:35 MSK (check your timezone here), along with standard div1+2 Codeforces Round #405. The contest "VK Cup 2017 — Round 1" is for teams qualified from two Qualification Rounds. The top 400 teams will advance to the Round 2, while other ones will have one more chance in the Wild Card Round 1 in April. Those who don't participate in the VK Cup can take part in the Codeforces Round #405 individually (problems will be available in English too). All three rounds last 2 hours, and all are rated.

I want to thank: KAN for his help in the contest preparation, MikeMirzayanov that we are here, AlexFetisov for testing, the VK company for this nice annual contest.

I'm a setter and I hope (and expect?) that you will enjoy the problems. During the contest, remember that you can read many problems and try to solve those that fit you most.

I wish you great fun and no frustrating bugs.

div2: 500-1000-1500-2000-2500
div1: 500-1000-1500- 2250 -2500
vk-cup: 250-500-1000-1500- 2250 -2500

The contest is over. See the editorial here. Congratulations to all who advanced to the next round, and congratulations to winners of each contest.

Specifically, the winners of VK Cup Round 1 are:

  1. Zlobober, zemen
  2. LHiC, V--o_o--V
  3. Arthur, kefaa
  4. map, Babanin_Ivan
  5. felix, Trumen

The winners of parallel rounds are:

Div. 1:

  1. -XraY-
  2. Laakeri
  3. Lewin
  4. dotorya
  5. RAVEman

Div. 2:

  1. rupxup
  2. YES_RPG
  3. T0RRES
  4. HXLLL
  5. Len

I'm sorry for letting some slow solutions pass in the Rectangle Strips problem. I tried really hard to prepare tests there but apparently didn't succeed.

Announcement of VK Cup 2017 - Round 1
  • Vote: I like it
  • +286
  • Vote: I do not like it

Comments Comments (151)
| Write comment?
»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

limak is back :)

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

will the VK cup round 1 questions be available in english??
Or atleast will the questions of VK cup round 1 be a subset of union of rounds 405 div1 and div2 ??

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

Number of problems?

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

    There are 7 problems. 5 for each division and 6 for participants of VK Cup. In more detail: div2 gets 1-5, div1 gets 3-7, vk-round1 gets 2-7.

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

      Please add this detail in the blog.

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

"May the Force be with you"

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

During the contest, remember that you can read many problems and try to solve those that fit you most

What does this mean? Does it mean that it is possible that A could be harder than B and the order is toughness will be random.

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

    No. Problems are sorted by the expected difficulty. That sentence means that maybe a problem B is some unpleasant geometry in 2D and you don't like it, while a problem C is about geometry 3D, what is your favorite topic. Then maybe you should solve C first.

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

      Thanks , I will unregister :D

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

        You can read D instead.

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

          Thanks I don't like Machine Learning

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

          Is D about 4D geometry (my favorite topic)? :D

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

            And problem E is like Polymeric Falcighol Derivation?

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

              Poor problem A.

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

                It's quite rare for having a tree in such depth in comment section

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

                  I'll just increase the tree

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

                  Yours made it reach max depth so I can't increase it anymore :(

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

                  Depth first Search

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

        when some sub-sub-.. comments have more likes than the blog.

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

        You are still registered :P

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

      Thanks.

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

      And if both of them aren't your favorite topic, read problem D or E, which is geometry + insane amount of math.

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

When I registered for VK Cup Round 1 Contest,the system showed me the information which told me that I registered for Codeforces Round #405(rated,Div2,based on VK Cup 2017 Round 1) before and I needed to unregister before continuing.However,I didn't register for Codeforces Round #405(rated,Div2,based on VK Cup 2017 Round 1)at all,what's the matter?And please tell me how I can successfully register? (I competed in the qualification round and got qualified.)

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

    In case if your name does show up on Codeforces Round #405(rated,Div2,based on VK Cup 2017 Round 1)'s registrant list, you can unregister yourself by going to http://mirror.codeforces.com/contestRegistrants/791/friends/true and click the "x" next to your handle.

    If that's not the case then I don't know D:

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

      I didn't find myself in the website you offered,so maybe it's not the case.

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

        Yeah I just checked that as well. I suppose that's not the case then...

        Hopefully someone can help you soon.

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

    I have the same problem and don't know how to fix it :(

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

    Yeah, the same information was shown to me and my partner. It said that I have registered for div.2 and my partner has registered for div.1. I don't know what to do to manage this, as in fact we have done nothing before. Hope someone could solve this matter. I don't want to miss the chance to take part in VK Cup.

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

      Just for information: you are not allowed to take part in Round 1 if you are not Russian-speaking. I urge you to respect the organizers and other participants. In addition, Codeforces team did an additional job in order to allow parallel participation of users from all over the world.

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

        Yeah thats fine.But if someone had by mistake written qualification round and qualified then now he has no other choice than to participate in round 1 because it now doesnt allow to register for parallel round

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

I can't register for Round 1. Each time get this message

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

Mike to the rescue.

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

How is the average rating of a team calculated? And how will the ratings be updated for the official round?

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

I always meet extremely frustrating bugs. LOL ...

Thank you for your wish.

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

I know that you love it Errichto, especially for you I'm posting it earlier than normally. :3

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

Excuse me, the terms of agreement of this contest are written in Russian :( (I suppose it is same as usual.)

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

Is is the first time on Codeforces history that a problem gets only 250 points score :\

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

    No, sometimes you have a Div 1 + Div 2 round with a Div2-C problem that is only 1250 points worth, so Div1-A (which is the same problem) is only worth 250 points.

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

      Frankly, the VK Cup A should be worth 0 points as the corresponding Div2B problem is worth 1000 points...

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

    For example, Task A from Codeforces Round #329 (Div. 2)

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

    Smooth dynamic scoring will also give 250 for most A's, as is described in this post. I met with a 250-point problem A on my first contest on CF :)

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

May be this contest bring high ratings to everyone. All the best :)

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

"May the logic be with you."

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

Rating prediction: div1 div2

Рейтинг команд мои приложением, к сожалению, пока не рассчитывается.

Extensions:

Have fun & high rating:)

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

Poland STRONK!!!!

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

WTF difficulty?

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

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

D is cool :)

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

    Do you know how to solve it?

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

      You should solve problem for one vertex and solve for other vertexes using answer of a parent.

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

        Still don't understand. Could you elaborate, please?

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

          You basically root the tree in any node and do two DP/DFS passes:

          First, compute the solution for all subtrees — you can easily do that by storing number of nodes in distance d mod k from the root in current subtree. The solution is then the sum of jumping distances in all children + number of nodes in distance d mod k == k-1 in all children.

          In the second pass, you just need to compute remaining distances using DP values in parent of every node: sum of distances above the node = sum of distances above its parent + sum of distances in all parent's children except for the current node + the same trick with modulo (index hell inc.)

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

      Tried using centroid decomposition.... Still got a TLE on pretest 9... I guess I need some optimization

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

      No

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

From last 5 minutes, when I am clicking on Hack a Solution, page does not open. Is this due to slow internet connection or everybody else is facing a problem?

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

    That's frustrating... a lot of solutions for B in my room were wrong -- mine included -- and I couldn't hack anything at the end of the contest =|

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

    I had 3 successful hacks on DIV 2B

    4 4
1 2
2 3
1 4
3 4

    answer is NO

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

The hacking system seems to be down for me :(

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

Hope all my solution passes and I will finally become candidate master.

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

is there any better order for (DIV1)C than n^5 ?

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

    O(n) solution: 25615179

    Edit: This is for Div. 2 C, not Div. 1 C.

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

      I guess he meant div1C.

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

      The first letter of each name should be uppercase, while the other letters should be lowercase

      while (x) {
    cout << char('A' + (x % 26));
    x /= 26;
}

      ¯_(ツ)_/¯

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

        Oops.

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

          As it turns out, I screwed up in the same place

          if x < 26:
    return 'A' + chr(x+ord('a'))
else:
    return 'B' + chr(x+ord('a'))

          ¯_(ツ)_/¯

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

How to solve Div 1 C. (unofficial) ?

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

My brain after solving Div1-B.

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

RIP RATINGS...

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

submit C 10 seconds before the end of the contest, waiting.. waiting...

Contest is over !! submission not there

good job servers, this website is so laggy these days

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

Div 2 Problem D is a nice Problem :D

Someone explain his solution please :D

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

Suspicious

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

I am the god of hacking (Problem A in VK Cup)

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

    What is the answer for this test case?

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

      NO

      But the fact is that ( 65538 * 65537 / 2 ) % 2^31 = 98305.

      There were those who used int instead long long.

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

Div1D pretest 9?

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

When u have coded the solution to easy problem in a contest and the computer crashes and never reloads till the end of the contest.

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

When will be rating updated ?

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

Is div 2 D supposed to be a lazy propagation segment tree after doing dfs ordering?

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

    No, it was just a dp on tree problem. For a node add the answer for its subtree and then add answer for all its siblings. For this you just need to store at each node frequency of nodes in subtree with distance%5.

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

      I was doing this, but I couldnt figure out how to get the distances for the paths that go through the father node.

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

        Just go on updating the parent node from it's children node. All the nodes in children's subtree will reach parent node in just prevDistance+1.

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

      It also can be solved using centroid decomposition.

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

IMO the problems are a little harder than usual, but are very nice. How to solve Div1 D?

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

    The editorial is ready but it will be imported only after the system testing. Sorry for the inconvenience.

    And I'm glad you liked the problems.

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

      I don't know about Div1, but Div2 set of problems deserves ⭐⭐⭐⭐⭐

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

        "rated"?

        EDIT: If you didn't like problems, I will be glad to hear what exactly was bad for you. Maybe I can avoid it in the future.

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

          He meant 5 star rating I guess.

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

            Hah, I wouldn't ever think that there is ambiguity in my comment =)
            I meant the problems are superb, like luxury 5 star hotels =)

            I see what's the problem — in different browsers these stars look differently.
            In my main browser they are of gold-yellow color.

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

      When the system testing begins?

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

hack test for problem A (VK Cup): n = 65538 m = 98305 and any edges which unite all 65536 vertices in one component.

let x be number of vertices in component

let y be number of edges in component

Who wrote if (x * (x - 1) / 2 != y) puts("NO") and used int32, failed on this test.

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

    Yep, or n = 92684 and m = 148290... System test 29 |-(

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

How to solve div2 C?

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

what's wrong with this output A A A Aa Aaa Aaaa Aaaaa Aaaaa in pretest 1 problem c Div2

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

    Its too vulgar :-P..

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

    Nothing is wrong.

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

    Your solution gives this output "A A A A Aa Aaa Aaaa Aaaa" on my computer which is wrong

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

    Watch out for Aaaaaaaaaaa, which is 11 characters, any name longer than 10 character is not allowed. I got WA on first try because of this.

    also your output on the judge is

    A A A A A A Aa Aa

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

On task D, div 1, my solution in O(n2) got AC, weak tests :\

An example on which I get TLE: n = 3·105, ti, j = (i+j % 2 ? -j : j+1)

Link to solution

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

    It seems that there is more than one O(n2) solution that got AC. I tried really hard to prepare tests in this problem but I didn't succeed. I'm sorry for that.

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

Tnx for the not copied contest :D

When are we able to solve the problems on problemset?

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

If I took 401 place but 399 place was taken by two people, will I participate in the 2 round?

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

    no

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

      Но. если у кого то место<=400 , определяется плагиаризм тебе повезло!

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

Well, I had some frustrating bugs.

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

Could some good soul who knows python please explain why this code gave runtime error in pretest 11 which has n=m=150000?. This isn't the first I've got such an error doing DFS in python. I really want to know as I'm finding it impossible to figure out on my own.

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

    Dont paste full code in comments, instead paste link to the code

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

    python stack size of quite less. RE is because of Recursion depth limit reach.Similar BFS solution will pass.

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

      Ahh yes your right! Python stack depth is only around 1000. The correct answer here offers a lot of light. Thanks a lot!..

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

    Maybe stack overflow?

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

      Yep that was the problem.. Python recursion stack size is small..

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

Buggy Div2.D !! :D

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

What a pleasure to solve some really original and less typing problems.

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

Happiness is getting into the darker shade of blue:)

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

wtf

is it machine link?

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

In Div 2 B, I used the fact that each in each connected component there should be an edge between each pair of vertices. Hence the number of edges given should be equal to — summation x*(x-1)/2 for each connected component, where x = size of the connected component. I used int and got a WA and when I replaced it with long long it got Accepted. Now my question is if the answer has to be "YES " then sum should be <= 150000 (since that is the range of M in the question) so int should suffice then why did I get a WA?

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

    actually the number of nodes present in a connected component can be of the order 10^5. So if x=10^5 and it is int then (x*(x-1))/2 will overflow. This is the reason why u got WA

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

      but then the number of edges required would be > 150000 so the ans anyway has to be "NO"

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

Hello.All my submissions are not evaluated yet. They are showing 'skipped' in my profile. Can I get to know the reason behind this?

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

    Most likely, you were disqualified.

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

It seems like the max rating and the rating graph has been updated, but the actual rating shown in the profile has not.

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

Ahhhhh finally pass problem E. Just a tiny bug in my reference of Half Plane Intersection, which has been used to solve ten or more problems. TAT....

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

It seems, that Div2C has some duplicate tests in the final test set, most likely due to multiple hacks with same values or something similar.

More exactly, tests #41 and #55 as well as #42 and #45 are the same. I guess this is some sort of bug? Probably not only for this problem?

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

Why is it that the graph and the max ratings have been updated but the present rating has not yet been updated?

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

Errichto Do you really think it's unprofessional to mention the sponsor name in the statement or that's just to match the problem requirments? If yes, why?

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

    I think it's fine. If I thought it's unprofessional, I wouldn't prepare such a problem.

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

Problem B 63ms solution :) In each group of friends,if the group is legal,all points should be connected directly between any pair, so just check if the power of point is equal to the groupsize-1 You may form groups by using union-find set Here's my c++ solution qwq http://mirror.codeforces.com/contest/791/submission/25794980

→ Reply