smahdavi4's blog

Codeforces Round #428 (Div. 2). Announcement
By smahdavi4, 7 years ago, In English

Hi everybody!

On Saturday, August 12, 2017, at 14:35 UTC Codeforces Round #428 will be held. As usual, Div.1 participants can join out of competition.

The problems are prepared by me(Sadegh Mahdavi) and NikaraBika(Majid GarooC). Great thanks to Arpa(AmirReza PoorAkhavan) and Livace(Alexey Ilyukhov) for testing the round, KAN(Nikolay Kalinin) for helping us preparing the round and MikeMirzayanov(Mike Mirzayanov) for the Codeforces and Polygon systems.

There will be 5 problems and 2 hours to solve. The scoring will be published later.

The main characters of this round are chosen from the game of thrones series :D

UPD : The scoring is : 500 — 1000 — 1500 — 2000 — 2500

UPD: The judges solutions for problem B incorrectly handled some case, so we are going to rejudge some of the hacks. The pretests are not affected, so the contest is going to be rated.

UPD : The round is finished. Congratulations to winners:

Div 2:

1.mama_budra

2.fatego

3.regmsif

4.Lyra

5.Illyasviel

Div 1:

1.dotorya

2.kmjp

3.I_love_Tanya_Romanova

4.Benq

5.Claris

UPD Editorial

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

Comments Comments (335)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it +75 Vote: I do not like it

There aren't going to be spoilers in the statements right?

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

    Nope. Many parts of the problems are written by ourselves and are not real :)

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

I guess problems will have lot of hacks. HBO, inspiration...

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

    Star India appears to have leaked the episode online through its own website.

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

:D

I'll be very disappointed though, if nobody dies, or if there are no dragons/mad kings/queens causing explosions.

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

I think this is very fast announcement of the year (because it published ~60 hours before contest) thank you very much. Hope editorial is fast as announcement.

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

Why isn't the announcement on the homepage ?

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

tank you Arpa. anybody know how the pdf will be published????

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

So I've been off Codeforces for a couple of months and then I see this Game of Thrones themed round. I couldn't get a bigger motivation to come back. Thank you for this. :)

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

When one of your friend didnt watch the show.

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

    When you're just doing the contest*

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

Why can't GRRM use twitter?, he killed all 140 characters. I'm struggling to think of a suitable pun for why he can't write problem statements.

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

OMG!!! This is going to be my favorite round perhaps ever! :)

I guess problems would be like; given seven kingdoms, three dragons (and their mother), one mad queen, a man who still knows nothing, how would you assign these kingdoms optimally?, haha I forgot the WHITEWALKERS!

Hope it will be as exciting and fun to watch as the show :)

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

I hope no one will die in problem statements like it's popular in Game of Thrones))

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

Problem statements be like : If Gendry started rowing in season 3 and Varys travelled from Dorne to Meereen in one episode, then where dafuq is Gendry?

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

I know nothing . But I am gonna participate .

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

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

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

Interesting round :)

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

Am I the only one in the world who hasn't watched this series yet??? :\

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

I won't be able to focus on the problems, I will be thinking what's going to happen instead.

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

Leave one Problem unsolved, and the programmers are never safe.

GOT_FAN

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

WoW GoT...excited for the problem statements.

"WHEN YOU PLAY THE GAME OF THRONES, YOU WIN OR YOU DIE."

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

Snapdragon has beaten tourist in GCJ World Finals. He's the new king of seven kingdoms.

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

i know nothing jonsnow;(

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

is it rated ?

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

--novice_dev-- you are not eligible for this contest

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

Game of Thrones + Codeforces = Game of tourist

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

I am new to programming and want to step into world of competitive programming. Is this a right platform for me to start competing ? What kind of questions will be there in this ?? SHould i participate in it ??

Please let me know! Thanks.

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

    It's really good. Codeforces is the only practice website I'm active on and there are lots of problems for you to solve for different skill levels. I recommend going to the problem set tab and clicking on solved to see the most solved problems and starting with those. You can see the types of questions they usually have by looking at previous contests, like this one.

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

I hope that I'll perform better than Lanisters' army in last battle.

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

Hope there will be Emilia Clarke's nude pictures in statements

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

Is there any PDF for translation statements to Persian ?

smahdavi4 NikaraBika

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

    Unfortunately, it isn't possible to publish the persian statements, we are sorry to persian users.

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

hacked solution like killed by white walkers, once you hacked and you find out the mistake so you can make others same by trying same hack. :D

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

Since this contest has a lot of GoT hype, I'm sharing this with whoever hasn't seen it.

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

I hope that this round will be successful. Good luck for everyone!

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

I Think I am the only one who haven't watched this movie.. !! :D

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

Scoring distribution

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

Registered users: Cro-Marmot, 172340, Cro-Marmot, 172340, 1040865060, ...

Hmm, that's suspicious...

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

About to start, Good luck everyone! I wish you all High rating!

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

Problem A says "Your task is to find the minimum number of days Arya needs to give Bran k candies before the end of the n-th day." But on querying, the problem actually is minimum number of days Arya has to take candies from the God to give k candies to Bran. The problem statement is wrong IMO.

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

    what the test case 7 ?

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

      Test-1
      2 3 1 2

      She can save and give 3 candies to Bran on the 2nd day and hence the number of days Arya gave candies to Bran is 1 not 2

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

Two unclear problem statements? Great contest. :D

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

This was one of the worst codeforces rounds ever.

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

    Saying this because you couldn't solve a tricky problem won't change anything

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

Pretests 7 in B and 5 in C;

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

    Solutions for problem B of even reds failed in pretest 7.

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

      I thought the same thing until I saw this "We call two seats neighbor, if they are in the same row and in seats {1, 2}, {3, 4}, {4, 5}, {5, 6} or {7, 8}" Did you notice this?

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

      Just used float instead of double and got AC -_-. What the hell happened in C?

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

    yeah i failed 5 c because i wasn't calculating the probability of choosing the path i was just printing sum(root->leafs) / number of leafs

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

    A bit more productive version: "But I will find you and I will solve you"

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

That pretest 7 in B killed me

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

I think the judge solution maybe wrong for B. I did a hack using following test case:

4 13

2 2 2 2 2 2 2 2 2 2 2 2 4

(4 rows, 12 groups with 2 soldiers each + 1 group with 4)

The judge solution gives "NO" for this case, but there is a solution:

[1][1] [5][5][.][13] [9][9]

[2][2] [6][6][.][13] [10][10]

[3][3] [7][7][.][13] [11][11]

[4][4] [8][8][.][13] [12][12]

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

    Use formatting

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

    Yes, I made a similar hack:

    3 10 2 2 2 2 2 2 2 2 2 3

    And system sayd me the answer is NO. Should be YES.

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

      My program finds the solution in this case :)

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

    Really? It's terrible.

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

    The answer "NO" is correct.

    We use 8 "2 - placed" seats for groups of 2.

    4 groups of 2 soldiers and 1 group of 4 soldiers remain.

    This group with 4 soldiers will use one 4 - placed seat.
    Now there are 3 "4 - placed" seats and 4 pairs of solders.
    You cannot place them without breaking the rule.

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

      Then how about this:

      [1][1] [7][7][ ][10] [2][2]
      [3][3] [8][8][ ][10] [4][4]
      [5][5] [9][9][ ][10] [6][6]

      hopefullly the author had taken this situation into account.
      So I'll fail the system test, defanitely :-(

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

    Now it looks like even Um_nik will fail (submission 29384447)

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

    i think i had a very simple sol before:

    Solution

    is it correct??

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

    I hacked 4 users with this test, but I didn't understand why?

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

Problem B _/_

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

Hack for B:

1 4 1 1 2 2

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

Hack Cases for A and B ?

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

Hacks for B?

I didn't hack anyone but this test broke my first pretests-passing submission:

4 10

2 2 2 3 3 3 3 3 3 3

Answer should be no I believe.

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

Ideas for E please, TIA.

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

    What I did was finding the maximal component where each vertex has degree equal to or more than i (1<=i<n) but I get WA on test 5

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

    Find the maximum clique in the graph. Suppose it has t nodes, the result is .

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

I used greedy in B, take seats in the middle segment first. Hope it pass

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

For E , is it correct that optimal answer is always a Clique?

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

    We might have the same idea. Run under timelimit, hope that it converge. :)

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

    I was thinking in lagrange multipliers, what do you mean by clique? is a pentagon ABCDE with a triangle ACE a counterexample?

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

      for pentagon answer is while for triangle answer is so clique works better.

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

        I understand that bigger clique is better than smaller, but can you explain why clique is always the best ?

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

          this is just a guess , i have no proof.

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

    Yes. Consider solution that distributes xi liquid to vertex vi. Suppose there is no edge between vi and vj. If we fix t = xi + xj and change xi, then answer is linear function of xi (because only summand that is could be not linear of xi is aij·xi·(t - xi) = aij·xi·xj, which is zero). So in one of optimal solutions either xi = 0, either xj = 0. Now fix any optimal solution with maximum numbers of zeroes. In this solution any vertices with non-zero numbers are connected. So, answer should be a clique.

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

    I proved it with following way:

    Lemma. There is an optimal way to give numbers to each vertex as this way: only some vertex v and it's neighbors can have positive values, and every other vertex has 0 value.

    Proof: Suppose that you have some optimal way to give values to vertices. For each vertex, calculate sum of values written in neighbor vertices. Find a vertex which has maximum value, and let this vertex v. Suppose we have vertex w != v, which is not a neighbor of v, and has positive value written. Then, we can just add value of w to v, and make value of w 0. This will make better result for problem. It means that all vertices except v and it's neighbors should have 0 value to have optimal solution.

    If we use above lemma, we can show that answer only depends on maximum clique by induction.

    Theorem: the answer for some graph that maximum clique is K is equal to answer for perfect graph with K vertices.

    Proof: 1) K = 1 -> Easy to show. 2) If above theorem holds for some K, it should hold for K+1 also.

    By lemma, we can take some vertex v and it's neighbors, and erase all other vertices from the graph. In this modified graph, suppose we can get rid of vertex v and think it later. (It's correct. We can find which value to write in vertex v, only depending on answer on graph without v) Then left graph should have just K-clique. So this graph is equal to perfect graph with K vertices by induction. By adding vertex v again, it becomes perfect graph with K+1 vertices.

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

In problem B, the answer for 3 10 2 2 2 2 2 2 2 2 2 3 should be YES, but judge outputs NO. Am I wrong thinking the answer is YES, or the judge is incorrect, and we will have to face another unrated contest?

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

    :p

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

    How would you organize it so that it's yes? I can't think of a way.

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

      We put 6 2s in the 6 2 seats, and 3 2s in the 4 seats, leaving 1 seat open in all 3 4 seats, and we can put the 10th 3 in 3 pieces to the leftover 1 seats.

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

      1 1 | 2 2 . 10 | 3 3

      4 4 | 5 5 . 10 | 6 6

      7 7 | 8 8 . 10 | 9 9

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

      The answer is definitely YES
      1 1 2 2 . 10 3 3
      4 4 5 5 . 10 6 6
      7 7 8 8 . 10 9 9

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

      This way

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

    You are wrong. We have 6 2-placed zones and 3 4-placed, 6 two-using groups sending to 6 2-placed, so we have only 3 4-placed zones and 2 2 2 3, we can't put groups on them, cause different groups can't seat with each other (sorry for my poor endlish :D)

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

    It's yes, ofc

    My solution passed pretests and it gives YES

    UPD: 29391756 passed systests =)

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

      Mine passed with outputing NO, but I tried to hack someone with this case, and it went unsuccessful, because judge outputs NO too.

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

    yes the answer should be YES

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

Ideas for D?

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

Now that the contest is over, can anyone share how they passed test case 5 in problem C? :'(

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

    you need to calculate sum( probability of reaching the leaf * depth[leaf]), instead of sum( of paths to leafs) / number of paths

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

    I fixed it by calculating for each destination the probability to reach there * their length. For each node the probability to reach its children would be the probability to reach itself divided by the number of children (with node 1 being probability of 1). The expected length is then the sum over all of the destinations.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it 
    Expectation(node){
   E = 0.0;
   d = 1.0/number_of_children
   for each v in node.children:
      E+= (d)*(1+Expectation(v));
   return E
}
    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Getting to different ends in the tree have different probabilities.

    Consider the input

    5
1 2
1 3
3 4
3 5

    Getting to 2 have probability = 0.5 whereas getting to 4 and 5 have probability = 0.25 each

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

It's not a bad round but the language could have been better. Tbh who the fuck wrote the statements, There were typos everywhere and caused me to even misunderstood Problem A.

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

In Prob B 2 7 2 2 2 2 2 2 2 Should be "YES"

1 1 2 2 0 3 4 4 5 5 6 6 0 3 7 7

but STD output "NO" ????????

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

We need to find summation of 1.kC1 + 2*kC2 + 3*kC3 + .... k*kCk for D right ?

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

    I did that and some inclusion exclusion but have WA4, in any case that sum is k*2k-1

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

    Yes, then apply Pinex not to count twice some sets {6} in the example 2,3,6.

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

    yeah. kCa = kC(k-a), so you can rewrite it as (k/2)*kC0 + (k/2)*kC1 + ... (k/2)*kCk = (k/2)*(kC0 + kC1 + kC2 + .. kCk) = k*(2^(k-1))

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

    I used Mobius inversion Formula (I knew it was totient) and Inclusion Exclusion for g=1.

    BTW The summation is equivalent to k * 2 ^ (k-1)

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

      I don't know that and had to derive a formula in last few mins and i couldn't.

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

    I derived it in this way -> Binomial expansion is,

    Derivating on both sides with respect to x,

    Substituting x = 1 on both sides,

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

      Or you could reverse the series S and add it to itself. You get 2*S = n*(sigma(nCi))

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

    Can you please tell me how to get this formula?

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

WA in A,B,C. solution for C: sum over depths of leaves/ number of leafs. Cant wait to see which mistakes I made.

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

    For begin I'm too did as you did. Then I solved so: when you went to vertex in DFS you should know probability visits to this vertex, children's probability such: (parent_probability)/(count_children). If vertex is leaf then ans += depth*probability_vertex.

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

    Sum of depths of leaves divided by the number of leafs is wrong. You have to take into account the probability of reaching every leaf (you have assumed the probability of each branch from the root node to be equal, which is not the case, as there is a branching factor at every node, not just the root). The line "In each such city, the horse goes with equal probabilities and it stops when there are no such cities" mentions this.

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

      Thank you sir! I didnt even realise you need to care about that.

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

fuck u -> precision coz it fucked up my rating.

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

In problem B, why is this white line here? I thought the seats 4 and 5 are not neighbours... :/

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

    So {1, 2} and {7, 8} are not neighbours as well... :/

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

    even I thought that.

    As it is just a div2 B it has to be under estimated :P

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

How to solve C ? Also , any idea on what could be the 4th pretest ?

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

    2 2 1

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

      answer is 1 ,right ?

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

        ofc, you just need to make directed graph, not non-directed as I did. After doing this, I've got WA on 5th test...

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

Problem B: add this test case in system tests please: 1 4 2 1 2 2

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

    Most times they add all successful hack cases to system tests.

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

    This is YES/NO problem, and there can be so many different test cases! I think it is not late to make sure, that system test contains at least 150 TCs.

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

    And anyways, probably 90% of solutions will fail on test cases, which the judge failed too during the contest, so there will be at most 100-200 solves I think.

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

    the answer is "YES".

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

The contest was quite nice (really liked the D). B was really annoying, tho as long as the problem is correct, I'd rather blame myself. All of this being said, the statement problem with problem C was extremely annoying and I've spend precious minutes trying to implement a root changing algorithm instead of writing the straight-forward one root solution. I almost ran out of time to write D because of this, so please, at least ignore the submissions before the announcement.

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

    What was your idea for a root changing algorithm?

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

I hacked a person who submitted this code for A, my hack case was n=100, k=10000 and a_i=1 for all 1<=i<=100. His while loop should have continued pass i=100 and have very undefined behavior, yet somehow it gave the correct answer. How?

#include <bits/stdc++.h>
using namespace std;

int main() {
	//code
	int n,k,i,temp;
	cin >> n >> k;
	int arr[n];
	for (i=0;i<n;i++)
	cin >> arr[i];
	int num = k;
	i=0;
	temp = 0;
	while(num>0)
	{
	    num = num &mdash; min(8,arr[i]+temp);
	    temp = temp &mdash;  min(8,arr[i]+temp);
	    temp+= arr[i];
	    i++;
	}
	if (i>n)
	cout << -1;
	else
	cout << i;
	return 0;
}
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Just because it's undefined does not imply it's wrong. I guess he was just very lucky!

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

    statement says a_i>=1 , you should have gotten invalid input for a_i = 0

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

for problem C i rooted the tree then had a function solve (i, d, prob) , i is index of current node, d is its distance from the root (the root is node 1), prob is the probability of reaching node i, prob starts by 1 and on each recursive call for solve the node i passes to its child the third parameter as prob multiplied by number of children of node i, when we reach a leaf node we add to the answer the distance of the leaf node from the root divided by prob, but WA at test 10, any ideas ?

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

    Most probably overflow.Your prob parameter may reach upto 2^2500 if you analyse.The trick was to prune the tree after prob parameter is sufficiently large.

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

The statement of problem B never specifies that the seats {3,4,5,6} are neighbor. "We call two seats neighbor, if they are in the same row and in seats {1, 2}, {3, 4}, {4, 5}, {5, 6} or {7, 8}.". This round should be unrated......

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

    3 and 6 are not neighbors

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

    3 is not a neighbor to 6. Only the pairs specified are neighbors. You can have different soldiers in seats 3 and 5, for example.

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

B was really annoying. Although pretests was not affected,but hack was. After Unsuccessful hacking I spent a lot of time on it. It should be UNRATED

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

    I support your opinion. Time is invaluable in Codeforces Rounds. This contest should be UNRATED!

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

    If your solution was successfully hacked by incorrect hack, you could have also spent time on it, trying to find a bug in a correct solution.

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

    KAN

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

    Also, I tried to hack with a correct hack, but I got unsuccessful. If I had succesful, I could have hacked more people with it, ending with more points.

    On the other hand, even with a failed B, I'll end up with positive delta in rating, so I'll be happy if the contest stays rated, but I also think it shouldn't.

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

    How you are affected by this issue as I see you never tried to hack any solution nor your solution got hacked

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

      I do. The hack ID is 341785. It was unsuccessful during the contest. And it was Ignored after the contest.

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

    You are right pantw:)

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

I think i should have a good sleep .

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

"The judges solutions for problem B incorrectly handled some case, so we are going to rejudge some of the hacks. The pretests are not affected, so the contest is going to be rated." AND WHAT ABOUT THE TIME WE WASTED IN FINDING THE BUG? CANT BELIEVE YOU GUYS

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

    Pretests were correct, be quiet, turn off caps-lock and put the gun in your hand to table, no need to kill testers.

    But this is good reason to make contest unrated: http://codeforces.me/blog/entry/53773?#comment-378155

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

      first go and learn to spell properly..there is a huge difference b/w "quite & quiet" kiddo

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

        It's not grammar mistake, I just mixed two letters, anyway,

        if my English is bad, so I can't write anything?

        → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it
      be quiet, turn off caps-lock and put the gun in your hand to table

      take your well-deserved upvote, sir

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

Why are the system tests taking so long?

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

I don't know if it is kinda template or not but this two codes are same:

http://codeforces.me/contest/839/submission/29409014

http://codeforces.me/contest/839/submission/29406327

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

    Their solutions to A also has a more or less line-by-line correspondence.

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

Oohoo, minimum number of days must be minimum number of index problem A, I think many contestant lost time on problem A !!!! LOL

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

Are there tests that cause a stack overflow in Java for C? Cause I resubmitted with iterative DFS just to make sure...

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

    Yeah my solution just crashed on the max case. Guess it's failing system tests.

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

Can you share some information about the hacks that helped to identify the bugs???

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

    10 3 2 2 2 2 2 2 2 2 2 3

    Answer is YES, judge outputs NO. I tried to hack with it, and got unsuccesful.

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

I cannot Understand the problem in my C problem code.... can anyone help? i simply did a DFS on the undirected graph and found the distances of leaves... take their mean. What am i doing Wrong for Pretest 5?

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

    5

    1 2

    1 3

    2 4

    2 5

    Remember, there is a different probability that the horse ends up at cities 4 and 5 than the probability that he ends up at 3.

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

      Thanks a lot... i didn't consider the probability of going to one branch.

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

Wikipedia reference was added to problem C statement without an announcement !

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

    In fact, there were lots of edits without announcement!

    As an example, at the start of the contest, I opened all problems, and my B problem said: "The second line contains n integers", I thought they should have been just k integers, so I refreshed and it suddenly said: "The second line contains k integers".

    Also I remember that happening one more time, but don't exactly remember where.

    EDIT: Now I remember, exactly in problem C, haha, it said: "What is the of their journey?", yes... unbelievable.

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

      codeforces should choose problem setters well or at least test problems many times by different persons

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

Another shitty contest, when you don't know whether to rate or unrate. All of that caused by trying to be too smart on B task...

I understand such initiatives on harder tasks, but why B? It is supposed to be a little more difficult than A. Why trying to make it so tricky?

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

    Agree ,really bad case-bash problem.

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

How about using the pretest results for B and ignoring all hacking results? It seems like some red-rated contestants also made mistakes on B.

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

    But it's unfair for the participants who solved it with the totally correct solution.

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

KAN what dafuq are you doing now?

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

    Maybe working together with the setters, and testers to figure out what will they do. They need time for that.

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

hack for B

2 8 1 1 2 2 2 2 2 2 "YES"

2 7 1 2 2 2 2 2 2 "YES"

2 8 1 2 2 2 2 2 2 2 "NO"

is it right?

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

    I think Claris got it right. You could actually use his solution to test.

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

      for case: 2 7 2 2 2 2 2 2 2 I got "YES" from his solution, but I think the answer will be "NO"…

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

        for the case : 2 7 2 2 2 2 2 2 2 I have tested some "Accepted" solutions, but I got "YES" from them. Something wrong for standard solution?

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

          it is yes. [1][1] [2][2][][3] [4][4] [5][5] [6][6][][3] [7][7]

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

            sorry that I am wrong… and thanks a lot.

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

I used Hightail today for the first time. It worked nicely. Thanks to the maker(s).

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

    Could you explain more about it???

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

      It's an application that helps you to check sample cases for your program. Please go through this blog about Hightail for details.

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

finally the testing started

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

This contest must be unrated, I know someone can say that, I'm just thinking about myself, but I was thinking about problem B more than one hour, and why???sorry for poor English

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

    For me it is totally irrelevant will it be rated or not. But your reason for unrated is wrong, you were thinking about B and didn't solve it, so what ? It is solvable and it will have many accepted. Estimation is wrong, but not so tragic as it happened on some previous rounds.

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

      That isn't but this is.

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

        What time is wasted ? Pretests were correct, so good solution will pass it. If you missed hack, you can think what is wrong with your code, but why would you think about it when you do not have ability to change code ?

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

          I pointed to my comment not to it's parent. I could have had more successful hacks, if I used the test case more times, but as I saw unsuccessful I didn't try. I tried to find the mistake in my test case (I didn't waste my time, because like 5 minutes were left) and I couldn't, but I didn't hack more anyways.

          However as I pointed out here I don't have problems, just try to make everyone see every aspects of the issue.

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

    If round 421 ended unrated,I don't see why will this round be different.Please don't apply double standards KAN

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

      That problem was (probably) unsolvable, and no one solved the problem during the contest. This one is different, now the judge was incorrect, but many people got it AC on system test. I also think it would be more fair to make it unrated, but if they make it rated, it won't be double standards.

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

Even though the system test began, my hack still shows unsuccessful, when it should be successful.

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

There are around 50 people affected by the issue in problem B. We will calculate ratings for all participants now, and after that (most likely tomorrow) will make it unrated for those affected who has negative rating change.

I'm sorry for the issue.

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

    So will the hacking data be in the system test?

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

    "negative raging change" I had a positive raging change after this contest :)

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

    I think it's the optimal solution, to make this as fair as possible for everyone, but this is still a problem. I don't know how many people were affected by it (I was), but it makes the positive rating change slightly smaller.

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

    when you publish ratings ?

    KAN

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

    This issue effected on me too, or I'm not rigth, KAN can you explain me what happened! UPD:Thanx

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

they ignored all my hacks, and what does it mean??

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

    it means all the users were correct on your given test case.. you should be grateful to the organiser as they did not give you negative points for this lol

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

      No just 2 or 3 of them were correct, other were incorrect, don't unswer if you don't know the unswer of question!!!

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

wow cool problemset (no)

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

wow! 1800 pretest passed for B and just 300 accepts !!!

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

I am worried with tests for the problem D. Is 29406336 supposed to pass?

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

    Why should it not pass?

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

      Calculation of the (1*C(n,1)+2*C(n,2)+...n*C(n,n)) requires O(n) time

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

        But sum of frequencies is N, right?

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

        A number from input adds to fcnt[i] only when i is divisor of the number

        So the complexity of your code is O(n*(MAX DIVISOR OF NUMBER)) So it fits well in tle. MAX DIVISORS OF NUMBER ~= O(NUM^(1/3)) (240 for 10**6)

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

          Wow, absolutely. I haven't thought about that.

          Thanks

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

Contest should be unrated as incorrectly handled some test-case for problem B. :|

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

When only 332 can solve a problem of category B in div 2 (including the div 1 players) and the author as well as the people related to this contest also make a mistake in writing the solution and testing, should the contest be considered even good?

Why shouldn't it be unrated? it looks harsh that we had a contest after a week and it turned out to be like this. But when a problem was being made, didn't it feel that this was being somewhat awkward? Problem C was easy (it was normal expected value problem) and problem B was really tough. even div 1 solvers would have had hard time solving it. so does it seem like a div2 contest? it would been better if it was div1 + div2. it would been fairer.

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

    A contest isn't rated when it's good, it is when it's fair. They handled the issue with the unfairness, so I see no reason to make it unrated.

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

Could smb explain me pretest 43 for problem B?

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

    11|22 3|44 55|66 3|77 The numbers mean the groups.

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

    11 22*3 44 55 66*3 77

    you can choose seat like something like up * is for empty seat

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

    7 Groups can be seated as follows: Group 1 at {1,2} at row 1 Group 2 at {5,6} at row 1 Group 3 at {7,8} at row 1 Group 4 at {1,2} at row 2 Group 5 at {5,6} at row 2 Group 6 at {7,8} at row 2 Group 7 Person 1 at {4} at row 1 Person 2 at {4} at row 2

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

If I understand correctly, my answer "NO" for problem B is correct, isn't it?

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

    11 22.3 44

    55 66.3 77 (dot is for seat left) so your ans is wrong

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

    AB CDEF GH 11 22 6 33 44 55 6 77 Hence answer will be YES

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

    11|22 3|44 55|66 3|77 The numbers mean the groups.

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

      Thanks, It was really interesting problem

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

        That problem was anything but interesting...

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

I downvoted this round. B problem was way too hard for standard B level.

I finally found clean solution for B after contest:

http://codeforces.me/contest/839/submission/29411599

P.S. It looks like CodeForces became harder. So you have to run in order to stay at the same place (run=amount of training, place=rating). And if you want to grow you have to run twice as fast. It's so demotivating!

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

    That's pretty biased, you can't say Codeforces became harder just because one hard contest, and even if you could everyone has had the same promblem set, so as long as you did better than the other people with lower rating than you, you will stay in the same rating.

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

      Then let's make all Div2 rounds where all problems starting from B will be as hard as Div1 E and A problem will be as trivial as possible. In this case, a few reds would be distinguished from each other based on number of solved problems (one solved 2, other 3 etc). Others will be rated only based how fast they could read the statement of trivial problem A and how fast they could type a text for trivial solution for A.

      Of course, that would be extreme case but I hope you've got the idea.

      I'm not enjoying write text for trivial solution for A problem as fast as possible as it will be the only way to distinguish yourself unless you are super strong.

      If problems don't have huge gap in difficulty, then most participants have more options than just compete in submitting trivial solution for A as fast as possible.

      P.S. I couldn't solve B problem for last few rounds in a row. That's never happen with me since 2015.

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

        I'm not gonna argue todays contest was harder than usual, that's definitely each person's perspective and it's hard to deny that B was definitely much harder than expected. But still, everyone has the same problemset and the difficulty of other problems weren't incredibly much harder. And most importantly rating isn't decided by one contest, everyone does better in some contests than others but as long as you keep practicing in participating your rating will hopefully rise independently of the problemset.

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

          Unless you are at the level to consistently solve C problem (which is quite high level), you compete with fast typing of solution for problem A.

          I.e. before you fill the huge gap between sometimes solving C and always solving C, you compete in fast typing solution for trivial problem A.

          As I said I couldn't solve B problem for last few rounds in a row. That's never happen with me since 2015! And I didn't make pause in my training. So CodeForces indeed became harder.

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

            The other people are learning faster than you and can solve B, or maybe they can finish faster than you while solving the same problems, then why wouldn't they rank higher than you?

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

              I don't think you understood what I tried to explain.

              So let's make all problems in all rounds as hard as Div1 E. Sure results of a few people could be distinguished from each other. Do you see problem in this model?

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

                But that's a logical fallacy, in reality you are always at least able to solve one problem, and people who are worse than you should solve the same or less problems. I know it's harsh to lose rating just because sone people typed the trivial problem faster, but if they solved the problem faster it is obl fair that it happens.

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

                  Look at AtCoder. They have much better difficulty distribution than CodeForces. In fact, you don't compete there by typing solution fast because the gap between difficulty isn't high, so that a lot of participants are distinguished by number of problems they solved.

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

                  All time I like codeforces because of unusual problemsets. If you want to solve easier problems there are many places. It is not easy to create interesting problems and keep their difficulty level. If one time problem B more harder than expected, other time it can be easier. Even my rating was fall, It was interesting problem. Thanks for contest.

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

                  That argument still is really bad, because if there are easier problems the same will happen, instead in atcoder you have to type 3 and not 1 trivila problem. And distinguishing participants by problems solved in itself is a bad measure because with 5 problems there is at most 25 different possibilities, definitely worse ranking system.

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

                  I think you don't get his argument at all. He is not talking about having 3 trivial problem, but instead have a gradual increase in difficulty. For instance, this codeforces round failed to do that as B was a little too difficult, in fact when I solve B, I thought that it wasn't suppose to be a B and should be like a C instead.(which is evident by looking at the number of AC of B and C)

                  distinguishing participants by problems solved in itself is a bad measure because with 5 problems there is at most 25 different possibilities

                  He is not asking to only distinguish participant by problem solved, he is just mentioning the problem that for those people with lower rating, most people will only have 1 problem solved (as the difficulty level increase too quickly), and this will make it into a contest where your standing depends more on your typing speed than actual problem solving skills.

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

                  Thank you! That's exactly what I'm trying to explain!

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

                  To be fair I did misrepresent the last argument and I'm sorry for that, but the initial rant was about this:

                  P.S. It looks like CodeForces became harder. So you have to run in order to stay at the same place (run=amount of training, place=rating). And if you want to grow you have to run twice as fast. It's so demotivating!

                  So while I agree that it can be true that the difficulty grows too fast, it is the same for everyone so as long as you learn at the same speed than the others your rating will eventually improve.

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

    And what your going to do, every one is trying his best, if you will not do this, you will newer be better.sorry for English

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

Test case #33 in problem B:

2 5

8 2 2 2 2

Why the answer is YES?

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

n = 1 can strike you hard sometimes :(

Problem C :(

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

Stop complaining about hardness of problem B. Nobody has guaranteed that problem B should be easier than C or D or whatever. The issue has affected only those who made an unsuccessful hack and these people can complain. But if you can't solve problem it doesn't mean that round was garbage and should be unrated.

And I want to thank authors for beautiful problem E.

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

What are the main topics/tags of problem D?

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

Can anyone help me solve the problem B?

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

In div2 B 1 4 2 2 2 2 Why te query answer is no ?

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

    The middle four seats are all connected.

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

      The problem statement doesn't have anything that says that !

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

        It says it pretty clearly and even gives a diagram. Honestly, I almost made the same mistake.

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

          he said "We call two seats neighbor, if they are in the same row and in seats {1, 2}, {3, 4}, {4, 5}, {5, 6} or {7, 8}."

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

            Exactly, so 3 is a neighbor of 4. 4 is a neighbor of 5. 5 is a neighbor of 6. Those 4 seats are all next to each other.

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

              so 2 is neighbor of 3 ?

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

                No 2 is not a neighbor of 3. I said the middle four seats are all next to each other. If one group takes seats 3 and 4 and another group takes 5 and 6, then seats 4 and 5 will violate the rule.

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

                  every row has 8 seats he didn't that the middle 4 are connected he said that the two seats are neighbors if they are in seats {1,2} , etc those pairs don't have {4,5} so 4 and 5 aren't neighbors .

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

                  They do have {4,5}. You even said it.

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

                  I didn't say anything :D

                  okay the contest has ended there is no reason for complaining about it thank you for trying to make me understand the problem though .

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

                  you know what I saw it now .

                  I think I was blind :D

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

Can anyone explain their problem B solution?

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

    We will keep three counters cnt4, cnt2, cnt1 storing the following information:

    Number of empty blocks of 4 seats (initialized to N); Number of empty blocks of 2 seats (initialized to 2 * N); Number of empty blocks of 1 seat (initialized to 0).

    At the start, we will greedily fill all the blocks of 4 we can. For each team t[i], the number of blocks of 4 we can fill up is min(cnt4, ). If we still have blocks of 4 remaining after we run through all teams, we note that we can break up a block of 4 into a block of 2 and a block of 1. So we do cnt2 += cnt4; cnt1 += cnt4; cnt4 = 0.

    After that, we will greedily fill all the blocks of 2 we can. For each team t[i], the number of blocks of 2 we can fill up is min(cnt2, ). If we still have blocks of 2 remaining after we run through all teams, we note that we can use a block of 2 as a block of 1. So we do cnt1 += cnt2; cnt2 = 0.

    After that, we just fill up all the remaining blocks of 1. For each team t[i], the number of blocks of 1 we can fill up is min(cnt1, t[i]). After we run through all teams, if at least one team still has at least one player remaining, the answer is NO; otherwise, the answer is YES.

    Implementation: http://codeforces.me/contest/839/submission/29414448

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

      Can you please give a formal proof why is partitioning the above way optimal?

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

Can anyone tell why CF-Predictor predictions are wrong today?

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

so why didn't the author say that the 4 middle seats are connected ? anyone who read the statement will say that (1,2) , (3,4) , (5,6) , (7,8) are the pairs

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

    You're right. The statement of B was very unclear and they edited it without announcement.

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

WA in Problem B, test case 7 gives me nightmares...

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

I find a test case for problem B:

2 7

2 4 2 2 2 2 2

The answer is "NO", isn't it?

And some of the shortest solutions can be hacked by this test case...

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

    The answer is yes -> http://codeforces.me/blog/entry/53773?#comment-378264

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

      You are not rigth, answer is "No", look, at first we will give for 3 first groups place to first row -> 11_2222_33 <- and after this we need to give places to other 4 groups, but we can not do this because our test case become " 1 4 -> 2 2 2 2", we can give for the first and last groups seats in places {1,2} and {7,8}, but we have two more groups, we can not give them seats, because seats 4 and 5 are neer to each other, and what did we get, anwser is "NO", sorry for grammatical mistakes :D

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

        You are right, sorry for my mistake I confused this testcase with this one : 2 7 2 2 2 2 2 2 2

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

in problem D why the output of the second sample is 39 ? any explain please !

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

    for size
    1: (2+3+4+6) (1,2,3,4)
    2: (2+2+2+3) ({1,3},{1,4},{3,4},{2,4}
    3: (2) ({1,3,4})
    so we have (2+3+4+6) + (2+2+2+3)*2 + 2*3 = 39

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

[ignore,fixed] Again 1727 :)

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

Hope it to be rejudged instead of unrated...(+149 last night)

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

    yeah... making a round unrated after the rating update is the worst idea!

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

[ignore, fixed]

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

Why unrated? Can someone tell me why?

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

Even after recalculation my hack still is unsuccessful, despite the fact it is correct. KAN could you please look into it? The hack's ID is 341839.

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

You copied my (and also E869120's) problem XD...
Actually Problem C is the easiest version of Problem D on square869120contest #4 in Atcoder.

→ Reply