IlyaLos's blog

Codeforces Round #346 (Div. 2)
By IlyaLos, 9 years ago, translation, In English

Hello, Codeforces!

I'd like to invite you to Codeforces Round #346 (Div. 2). It'll be held on Wednesday, March 30 at 16:05 (UTC) and as usual Div. 1 participants can join out of competition. Note that round starts in the unusual time! Also, the round itself will be unusual: there will be 7 problems for two and a half hours.

Me (IlyaLos), Edvard Davtyan (Edvard), Dan Sagunov (danilka.pro), Roman Glazov (Roms) and Vladimir Petrov (vovuh) prepared the tasks for this Round. Great thanks to Gleb Evstropov (GlebsHP) for helping us preparing the contest, to Maria Belova (Delinur) for translating the statements into English and to Mike Mirzayanov (MikeMirzayanov) for the great Polygon platform, for helping on preparing the contest and for ideas for some tasks.

The scoring distribution will be announced later. Good luck everyone!

UPD Score distribution: 500-1000-1000-1250-1500-2000-2500

UPD2 Competition completed! Thank you all! Editorial

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

Comments Comments (205)
| Write comment?
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Expecting a good round :)

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

A regular Codeforces round after a long time :).

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

Just learnt coding about two weeks ago and this is my first round. Wish me luck!

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

Hope to advance to Div1 this time!

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

Just wondering : If there are 7 problems then why not make a Div.1 Round too?

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

    No, because tourist now has a 4000+ of rating. I respect that!

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

    Kinda related, I wonder if it would be difficult to allow for div1 users the option to register to div2-only rounds as ranked competitors. If I'm not mistaken, it's not allowed because div1 users might run out of problems to solve, but if they wanted to register as ranked competitors into div2-only rounds, they'd have to accept that possibility, yet could still get the fun of competing in a ranked round. Many div1 competitors usually can't solve any problems past the first 3 anyway (I know I can't).

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

      It would be nice. We can just have separate rankings, which means some may loose rating even though they solve all problems (but too slow).

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

      Div1 competitors will quickly solve problems and will begin constantly hack others. Poor chance for div2 competitors to hack somebody (and learn how to hack).

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

    Probably because the F and G problems in this round would be way too easy as Div1 D and E.

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

    Is someone going to answer his question!?

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

      I can try. Because the problems are too easy for Div 1?

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

Let's hope this be a nice round for everyone :D

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

Good luck everyone

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

It's been a long time since a totally normal rated Codeforces Round. :(

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

    Except this one has 7 problems and 2.5 hours and is only rated for Div.2.

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

When Soni says something, you repeat it!
When Soni does something, you do it!
When Soni has something, you don't have it!
And that's so because Soni is a cool guy!

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

Why 7 problems for div.2???

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

    maybe for easy problems :-"

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

    I guess maybe they found those problems were too easy for div.1. So, 7 problems for div.2. lol Okay,frankly, maybe just for fun.

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

I wonder if there's something that could tell me my expected ranking to get a +rating. Even 5 minutes before the contest would be great. Don't know if that's even possible though.

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

    you expected rank can't be computed before the contest is finished, because it depends on the people who make at least one submission

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

    Try the NBHEXT extension for Chrome. It is not completely accurate because systest, but you get a rough estimate.

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

      I think that it consistently gives lower ratings because it interprets newcomers as having "0" rating instead of "1500" rating.

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

        Yup, and it also occassionally shows a 0 difference for Legendary Grandmasters when it obviously shouldn't be 0. But like I said, rough estimate.

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

Can I request a 10 minute delay? The bus is slow : O

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

Funny. When using CHelper, you can see "April Fools Day Contest 2016" before today's round. Did that one already happen?

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

Is something changed regarding contest registration. Though I registered, it's still asking for registration while submission.

http://i.imgur.com/35uAN1W.jpg

--- [Edit] Now option to register re-appeared, and can submit after re-registration.

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

.

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

Why is problem A blocked? I want to resubmit my solution.

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

I am not put in a room for hacking, so I cannot hack. Is this a bug?

EDIT: I also registered late, so I don't know if this is the problem?

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

I don't want to see all human defeated by AlphaGo, but this will happen if AlphaGo passes all system tests

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

    His submissions look suspicious though. He got B and C accepted in the same minute, and it only took him 8 minutes to solve G.

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

    By the way, I think that the problem statements are pretty formal and the next challenge for the DeepMind team could be trying to compete in the programming contests.

    Correct me, please, if I am wrong and there is something about artificial neural networks that doesn't allow them to compete here.

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

      Are you joking? Sometimes I can't figure out what the hell the authors want from me by myself, and you want to make computer understand that?

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

        Well, aren't computers better at solving CAPTCHAs than humans already? But I agree that it seems very unlikely to happen

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

        You know that can't be an argument :)
        Sometimes we cannot recognize faces on the pictures, but Google can (despite the millions of years of evolution that crystallized our ability to recognize human faces).

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

    I wanna see AlphaGo vs tourist face-off assuming AlphaGo is AI and not a team/user.

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

Interesting contest, what was the solution to F?

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

    Loop through all the cells. If k is evenly divisible by the number in the cell, and cellnum*m*n is greater than k, then do a BFS across adjacent cells that are greater than or equal to cellnum. If we have processed k/cellnum nodes, immediately print YES, print a matrix such that any cell examined in this BFS is given number cellnum and all other cells are 0, and then return. If the loop completes without finding anything, print NO.

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

      Won't this time out, if all the cell numbers are divisible by k and none have required adjacent cells greater than its value?

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

        You are correct... for example, the 1000x1000 checkerboard pattern of 3 and 7 with a 1 on the bottom right and k=3000000 times out horribly with the wording I gave. I should add, then, that I kept track of which cells I had visited in BFS's for a given factor, so I wouldn't do duplicate work (i.e., a full BFS every time I ran across the number 3). With this addition, it doesn't time out in practice because the number of distinct factors of k such that you will need to examine a sizable subset of the matrix is exceedingly small.

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

        Mine didn't. I used the same approach. But I used some heuristics to reduce the time (eg. I consider only those values in the arr[][] such that k/arr[i][j] <= n*m). Please refer to 17055152.

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

      If you want O(nlogn), you can use DSU on components to store the number in each component and a priority queue to process cells by descending height so that you dont have to process any large amount of area twice.

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

Please someone explain problem 5. I think it is somewhat related to cycle finding or some trick to be used using dfs/bfs.

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

    Answer can not exceed the number of connected components. So define answer=number of connected components. If there is a cycle in a connected component then decrease answer.

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

      Thank you. Now seems it was to easy and seeing many people solve it.

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

    Consider each connected component separately.

    If the connected component is a tree, the answer is 1. This is because there are only V - 1 edges — not enough edges for all vertices. It is not more, we can root the tree and direct all edges from parent to child. Only the root will have no incoming edges.

    If the connected component has cycles, the answer is 0. To see this, take an arbitrary cycle and direct the edges in it the obvious way. Now you can throw out some edges (and direct them randomly) to get a tree for every vertex in the cycle. Direct all those trees from parent to child and you'll see that all vertices have incoming edges.

    So, for each connected component, check if it is a tree, and if it is, add one to the answer.

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

    Alternate (greedy) solution:

    • count undirected edges as "inward" edges
    • use a min-heap to store number of incoming edges to each node
    • assign "inward" edges by popping off min heap

    at the end, the answer is the number of nodes without any "inward" edges (http://codeforces.net/contest/659/submission/17054791)

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

    Consider a connected component If it has a cycle it is possible to assign directions to edges such that no vertex has zero incoming edges
    If it has no cycles there will be exactly one such vertex
    So just count connected components which do not have cycles

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

    if you don't want to find cycles, then just count the number of edges in each connected component, you can do it by summing up the degrees of all nodes in that component then divide it by 2. if the number of edges is equal to number of nodes minus 1 then it's tree and there's no cycle, otherwise there's a cycle

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

Hacking test of B?

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

    5 2 Ivanov 1 763

    Andreev 2 800

    Petrov 1 800

    Sidorov 1 800

    Semenov 2 503

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it 
    3 1
a 1 1
b 1 1
c 1 0
ans a b

3 1
a 1 1
b 1 0
c 1 0
ans ?

3 1
a 1 0
b 1 0
c 1 0
ans ?

3 1
a 1 0
b 1 0
ans a b
    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    4 2 Ivanov 1 800 Andreev 2 763 Petrov 1 800 Semenov 2 503

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

    some people wrote if (list[i][0] == list[i][2]) printf("?"); else print answer, which is wrong (should be list[i][1] == list[i][2])

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

Problem B Hack

3 1

dushyant 1 20

sumit 1 16

snigdh 1 16

Answer --> ?

PS — My submission will fail. :(

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

Look to the solutions of problems B and C user AlphaGo , they sent in 10:48 and 10:51, and had so different style code, i think it wrote by different people

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

why geometry why :'(

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

    I kept trying to solve D for two hours. Did you solve it? . I couldn't get my algorithm right for finding whether a line segment will properly cut any segment of the polygon when extended in the direction given.

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

      All of the left turns are dangerous, while right — not. If we know this, we can solve the problem with no geom using some conditions.

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

        It is never stated that she is travelling clockwise. If she goes counter-clockwise, then a right turn is dangerous, and left is not.

        Edit: I retract my statement, I didn't realise that the staring positions was always the bottom left

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

          if she starts at the bottom left and the first move is to go north, there's no way the water will be on the left side (since you end up at the starting position, see http://codeforces.net/contest/659/submission/17049036).

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

          Checking whether the direction is clockwise is actually really easy. Consider the following equation:

          .

          The direction is clockwise if and only if the sign is negative.

          EDIT: Friggin' Codeforces Latex

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

      the answer is the number of left turns (you can get that by cross product)

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

      My approach to D was to keep a counter for the dangerous turns if the water is on the left and if the water is on the right. While iterating through all the points, use the previous point, current point and next point to determine whether she is turning left or right. If you are turning left, the it would be dangerous for the water to be on your right, so increment the right counter. If you are turning right, the it would be dangerous for the water to be on your left, so increment the left counter. Then when you are done iterating through every point, just output whichever counter is smallest.

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

        Starting point is at the left-bottom most point, there is no way the water can be in the left.

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

          Ah, I didn't see that. I made more work for myself than I needed.

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

      My solution is simply (N-4)/2. Consider 90 degree and 270 degree angles.

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

    After some minutes of thinking how to solve it in a nice way, I give up and seek for pre-written geometry library that do the job for me (I hope there's no bug inside tho).

    For those who solve it without a generic written code, how do you guys managed to write decently? (e.g. without using lots of if)

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

      Which library did you use?

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

      I used 4 ifs (in fact 8 so that the conditions are more clear), is that a lot?

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

      You can solve it with just basic things like calculate area of polygon & CCW

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

        Turns out area isn't even needed because you start at the bottom left...

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

        As it has been said the answer is (N-4)/2 since when you have more than 4 edges on the polygon all the left turns will have one corresponding right turn. I am amazed how almost none of us didn't figure that out, going instead for a longer solution...

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

          Hahaha almost thought of convex hulls and stuff until I realized "hey could I find a pattern". and I noticed it was something like linear (clearly it must) and then I remembered of 90 and 270 degrees.

          Basically if we have an n-gon composed of 90 degrees and 270 degrees suppose there are a 90 degrees and b 270 degrees. Total angle is 180(n-2). Then 90a+270b=180n-360... a+b=n. Solving we get b=(n-4)/2.

          Yay

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

        You can do it without calculating the area or point-in-polygon queries, by just checking 4 conditions regarding the previous and next directions of movement, for each corner point. Please refer 17044429.

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

      Collect all if's in one place and use enums: 17046342

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

Who is AlphaGO?

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

Please suggest an approach to solve F and G.

Thank you.

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

    F is already explained, as regards G I did dp:

    dp[i][0] — the number of ways where you remove something from position i and the remaining height is not greater than h[i+1]

    dp[i][1] — the number of ways where you remove something from position i and the remaining height is greater than h[i+1]

    Obviously if h[i] <= h[i+1] then dp[i][1] = 0;

    Hope that helps.

    Edit: If not, here is the submission implementing that logic: http://codeforces.net/contest/659/submission/17059428

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

    I think it can be solved in a greedy manner, using DSUs. Start processing the cells in decreasing order of their values. When you process a particular cell, check its neighbouring 4 cells. The cells among those 4 which have their values >= value of current cell, are combined with the current one using DSU. After each combination, check whether that set has the required number of cells (if value of the cell is v, the set should have at least k/v elements). The moment this occurs, you have found the answer. Assign exactly k/v cells of this set to v, and assign all remaining cells in the grid to 0.

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

Hack you back.

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

Nice and balanced problem set, perfectly suits for div2 difficulty in my opinion. But, Problem statements were not easy to understand (at least for me).

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

Wasted my whole time on a silly mistake with B, could have easily solved 4 problems :( :( :(

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

Codeforces team: Please check FlappyBird's submissions.
http://codeforces.net/contest/659/room/112
Seems like he wasn't codding alone.

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

Any ideas how to solve C? I did simple greedy algo but it failed on tc #10.

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

    Greedy was okay.. Can you post your code ?

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

    You just made 100100 sized array to mark used toys, but that can be from 1 to 1e9. Your update will fail if used toy is greater than 100100.

    Your code->

    const int N = 100100;

int n, m;
bool toys[N];
    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is approach to solve question D ?

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

    (n-4)/2

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

      Are you serious!? Does that actually work?!?

      Edit: Ah, I see now! First there is the 4 turns which MUST be made to get back to the start, so subtract them. Then every variation other than those 4 turns require 2 turns to go straight again (1 safe turn and 1 dangerous turn), hence the division by two.

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

      Can you provide some explanation for this?

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

        very rough idea

        rectangle-> 4sides,0turnings,take a side possible modification gives 2 turns for 4 more extra points

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

      ...and here I thought I was being clever with my vector solution counting the left turns.

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

        not my idea some in my room did this , i tried to hack but was not able to get any test case

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

        Me too, I also counted left turns)

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

      Lol and here was I dangling with geometric algorithms and what not :P

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

Before that contest finished, I was 1200 and now I have two failed problem and I am 3200. Ohhhhhh noooooo.

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

Anyone else not realize that you couldn't add to piles in problem F? I had the solution but made that dumb mistake ugh.

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

Can someone tell me some hacking tests for 'A'. A guy I know made 11 successful hacking attempts :D

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

    Possible mistake can be giving output a negative number, because of improper modulo operation.

    Mine failed at this->

    10 6 -100

    answer should be 6.

    my code outputs -4.

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

Please enable upsolving !

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

I hate that kind of simple but tricky problems like A!

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

How is this even working?? Problem D. answer is n/2 — 2 ; http://codeforces.net/contest/659/submission/17055800

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

    n/2 — 2 is the exact same as (n-4)/2, to which there are multiple explanations in the above comments. One of them should help you out.

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

The difficulty of C, D, E problems weren't even of Div2 level.. The contest should be renamed to "DIV 3". 1000+ people solved C,D,E

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

    I liked problem E!

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

    But A and B were?

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

    Can you please explain how you solved problem E?

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

      If you are given a tree, then the answer will be 1. Let's say you root the tree from a certain vertex, then we can draw directed edges from parent of all vertexes to them (And none of them will be seperate). Except the root (which has no parent) .. So in a tree we will always have answer 1.

      But, if we add one more edge to the tree. We can satisfy the earlier separated node (i.e root). So, if we have a cycle in the tree. It would have answer 0.

      So finally see all the connected components that doesn't have a cycle (count all the connected components that are actually trees). This could be done easily with a DFS.

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

Please someone explain this solution ( http://codeforces.net/contest/659/submission/17054528 ) for problem D.

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

I first submitted a solution in problem E which got WA in pretest 9, then i get a new idea which gets AC, but i do not understand why my first idea was wrong!!

I gets the in degree for each node and greedlly subtract the highest m value of them (one by one using priority queue ) and the answer is the number of zero in degree after that, and this is the code 17050130

why this is wrong?! what i missed here?!

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

When will the ratings be updated? Has anyone's been updated yet?

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

Can anyone help me please ? Why I am getting WA at Test 15 for Problem B ???

http://codeforces.net/contest/659/submission/17059710

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

Is AlphaGo not a single coder?

The coding style of the submissions by this account are different. For examples, solutions on C and F used:

#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif

while others don't.

And solutions on E and F used:

#include <bits/stdc++.h>

while others don't.

We can find that the coding styles of different codes are not similar.

On the other hand, AlphaGo used only 3 seconds to submit B after C. Should this kind of accounts be banned?

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

    OK this account is fake, but there is no proof so he can't be banned.

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

      If it doesn't get banned, this may create a precedent for others to cheat.

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

        Looks like PPFishIsADoge is not a single coder too.

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

          Yeah, I looked upon his submissons a moment ago and the coding style is different.

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

    Also there seem to be 2 very distinct templates being used.

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

Can someone tell me why I am getting TLE in my solution for B , I am trying to find bug around 2 hours : 17055144 ?

Thanks in advance.

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

First time to solve A-B-C-D-E during the contest time and guess what!! my rate decreased :(

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

Please let us open the problemset now

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

This is my first round to get an AC problem, nice problems (y)

btw this is also my first comment in CF xD

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

Can someone tell me what is wrong with my B solution? 17044686

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

    You need to check that a[i].size() == 2 before asking values, otherwise your

    if (a[i][0].score == a[i][1].score)

    will result in undefined behaviour in C++.

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

Before and After system test

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

thanks dude! 17057269

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

I had a problem with the 53 test case of the B problem. My output is correct, and the author of the problem didn't estipulate any order of the names of the selected member of the team...

I got wrong answer, and the checker message was "wrong answer Jury solution is better than the participant [region=143]" ... I just don't understand the reason that i've received WA...

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

    Before checking [1] == [2] you must ensure that there is at least 3 participant, otherwise equality checking result would be undefined

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

Can anyone explain this solution to E. for me? 17042676 by AlphaGo

I think I get that the array fa represents the "root" of each node's connected component. What are tot and TOT?

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

    tot: vetexes count TOT: edges count if TOT==tot, there is a circle

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

      Thank you! Do you know what purpose this line serves? tot[u] = TOT[u] = 0

      Edit: I just tried running the submission, exactly copied, but with that line removed. It still passed all tests. So it looks like that line is unnecessary.

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

As the tutorial said, we can make a boolean array in problem c; but i failed to do it at c++, because array size of 1e9 was too great, can anyone tell me how to achieve that, thank you

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

    Using sets. Learn STL as soon as possible. Because it's very useful and easy.

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

    The editorial also specified to maintain a boolean array of max 2*10**5 and from the input numbers mark only those that are less then 2*10**5.

    → Reply