Lewin's blog

Codeforces Round #309
By Lewin, 10 years ago, In English

Hello Codeforces!

I invite all of you to participate in regular Codeforces round #309 that will take place on 24 June, 19:30 MSK.

Some of you may know me as lg5293 on Topcoder (you can see some of my past problems here), but this is my first time ever writing a Codeforces round. I've designed all the problems myself and I hope you enjoy them.

I want to thank ctunoku for helping me come up with stories for the problems, Zlobober for his immense help with preparation for this round, winger for testing the problems, Delinur for translating statements, and of course MikeMirzayanov for the superb Codeforces and Polygon systems.

I hope to see you all at the round. Good luck and have fun! :)

UPD: Scoring will be dynamic. Problems will be arranged by what I think is increasing difficulty.

UPD: Editorial is here. Congratulations to the top 5:

Div 1:

  1. ecnerwala

  2. scott_wu

  3. enot110

  4. KADR

  5. yeputons

Div2:

  1. Elsa_Elsa

  2. Chenyao

  3. cdkrot

  4. Shayan

  5. M_H_M

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

Comments Comments (224)
| Write comment?
»
10 years ago, # |
  Vote: I like it +132 Vote: I do not like it

I know you as a guy who writes huge answers explaining people who don't get the solutions :D . Huge editorials incoming

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

    Thanks :) I'll try to live up to your expectations.

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

A month without div1 and 2 separated contest!

Last div1 and 2 contest was held on May/26/2015 Codeforces Round 305 (Div. 1) Codeforces Round 305 (Div. 2)... I wish we can enjoy your problem set.

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

    Month without div1 and div2 separated contest — and now we'll have 2 such contests in 3 days :)

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

      Really... I agree with you. I have been waiting this contests... good luck all of participants....

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

Nice, your problems are usually interesting. Too bad the round is at such a bad time for us in the Americas. I'd really wish there would be more rounds on weekends or just more variety in the contest times to benefit all time zones...

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

This might be a weird question, but for the last round you wrote for topcoder, div 2 1000 points, is there a proof of the pattern, or must one simply notice it? Thanks.

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

    misof describes it in this comment. The key idea to note is to count the same thing, but in a different way.

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

i hope less no of unrated people in div2 since there is a div1 contest this time

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

Finally, Div.1 come!

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

eagrly waiting for div 2 intresting problems.. :)

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

Look at your TopCoder problems, I see a lot of maths, geometry, but few graph. Will this contest have almost maths and geometry?

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

    I'm hoping for some data structures ... :P

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

      Would be great if problems are of different types, imho :)

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

    i study math olympiad. and i do programming for fun. i hope this contest have many math problems.

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

    Let's hope not...

    I want data structures, sqrt-decomposition, trees, graph theory in general, etc..

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

Please make the problem statements clear and concise . I particularly don't like problems which are hard to understand . :D .

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

My first Div1 :D

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

i didn't participate in tc for almost 5 month

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

The first semester and the final exam just ended today...! I'm so happy to take CF at home, not dorm.

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

good round but bad time :(

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

I wish good luck to all students in the final exams successfully submit.:)

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

    Yes, luck may help some of us :) Thnx)

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

Just a pic about my CF contest style:

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

Hope that contest will not as hard as contests of allllekssssa and PrinceOfPersia.

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

the blog post doesn't say anything about hacks :D

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

I think this contest have At least one Geometric problem

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

I belong to the first...

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it 
    main(){
  itoa(2, col, 2);
  if(strcmp(col, "10") == 0) mark ++;
  else mark --;
  printf("%d", mark);
}
    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    I don't know Russian but I guess this is the joke about binary system, isn't it? please translate for us

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

      There is 10 types of humans in the world. Those who understand binary code and those who doesn't

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

        So my guess was correct :D

        how about this one:

        There are 10 types of humans in the world: those who know binary system , those who doesn't and those who didn't expect this joke to be about ternary system

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

          There are 10 types of people in the world: those who understand hexadecimal, and F the rest.

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

    To people who click minus for this picture, you are very stupid! Yes, I'm waiting for minuses for this comment too...

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

Hope I become Expert in this round

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

yeah~The contest FINALLY comes,I have been wait for so long ....

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

I liked the problems of your topcoder SRM 652. I hoped it would be rated.

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

Izi problem, izi life

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

Scoring? . . .

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

    Dynamic ):

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

      what does this mean ?

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

        It means that the maximum scoring for a problem will depend on the total number of participants who send an AC solution i.e. the more people who solve a problem, the less that problem will value.

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

beijing-----》00:30，shi fen dan teng！！（Very egg pain！！）

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

Since last job change, my rating was down down down. Hope this round would add some points. 00:30 for chinese player is too later in night.

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

Codeforces is temporary unavailable ... :(

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

There was a lot of "website was not available" stuff... did anyone else experience this?

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

I couldn't open any problem for the first 5 min... :\

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

    You will get extra 10 mins

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

      but people have already submitted before i was able to open a question

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

will this be an unrated round ?

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

Why do you block recent actions page, the most useful page here, during the rounds?

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

Guys, sorry about failure on start. The reason is quite funny. Because of huge number of participants I blocked some pages to reduce system load. I don't know why, but this time I've blocked user profile page. But our internal monitorings have rule like

   if failed url http://127.0.0.1:8088/profile/tourist
       and content == "Grandmaster"
       with timeout 10 seconds for 4 times within 5 cycles
           then restart

So monitoring systems decided that Codeforces servers were down and restarted them just before the round. And they were restarting Codeforces serveres again and again... until I unblocked user profile page.

Sorry participants, sorry Lewin :(

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

    It's alright! Thanks so much for your work and contributions!

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

    IMHO, Codeforces should consider the option to limit the number of participants to reduce system load (like TopCoder).

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

    So this means if tourist is no longer red, Codeforces servers will lock down in shock?

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

      Exactly. And not only Codeforces servers but me too.

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

      or when tourist decided to change his handle to something else...?

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

        No, because now codeforces redirects links with old usernames to their actual profiles.

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

REALLY? So many math problem in div 1 and 2. I honestly think that this round is pretty bad as almost all problems are only rely on math which are hard imo. I am not good at math and i feel very desperate. I hope next time will have a normal programming contest instead of math contest.

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

    You should be aware of that possibility by looking at the previous writer's TopCoder problems.

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

Feeling like back in Permutation and Combination classes :(

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

The clarification in problem B changes completely its meaning. I submit a solution to this problem for the wrong meaning, of course, getting WA. Changing it to the new problem required a lot of more code, so i'll pass ;(

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

    No it doesn't, the problem statement is perfectly clear:

    You start out with a bunch of cycles. Then you shift each cycle until it has its largest element first (it doesn't state that you are allowed to alter the cycles meaning so you can only shift). Then you sort the cycles with respect to each cycles first element (this can't be taken as sorting the elements in each cycle since the elements doesn't have a first element to sort by). This way we get a unique representation of each permutation.

    There is no other way to read it.

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

Div1A felt harder than Div1B :(

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

    All you had to do was scan a number and print 25*n+1. Easiest problem I have ever solved.

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

Nice problems, looking forward to your next round ;)

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

Lots of fun Math in this contest!

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

And not a single hack was given today.... :P

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

I wish I read the announcement...

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

why is problemset still blocked ? i am waiting to submit a code from 2 hours and still cant submit

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

Lightoj 1226

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

Today's Div1A/Div2C is same as this problem of LightOJ !! As LightOJ requires login, you could see it here !!

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

    I'm sorry for the collision. Hopefully you found the other problems enjoyable.

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

      The other problems blown upon our head. That means the domain of those problems were Out of Range of most of us!! However, Thanks a lot!

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

Before resubmitting one should read the whole input restriction again. In Div1 A/Div2 C, I check that no of ball should be less than 1000 but forget to read that sum of them will be less than <= 1000 lost many points due to that.

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

I wish the contest could be extended by 2 more minutes....drat! I finally coded C and time up!

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

UPD. Nevermind, I got my mistake.

can someone kindly tell me what is wrong with my code?

I am basically doing search over number of possible splits of set of indexes. Number of ways to split n-element set on k subsets is Cn - 1n - k. Thus, of all possible splittings is . (F[n] in my code.)

So, I am simply doing search on my code according to the following rule. Suppose we are at position i(1 based). If F[n - i] >  = k, then we need to merge this element with the next one (i + 1). Subtract k from F[n-i] and check if we have to merge current element i with the i + 2. When we face with the element j with which we do not have to merge current i element, we simply write {j-1, j-2, ..., i} to output array and move to position j.

For some reason, this fails. Code seems to be fine. I think the problem is in my idea. Could someone kindly tell me why what I am doing is wrong?

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

    Sorry, can't see your code yet

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

    All subsets must have size 1 or 2. This is because the smallest element in a subset must point to the largest, because the largest must be listed first in the cycle. Which also means that the smallest element must be listed last in the cycle (so it points to the first).

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

Someone really likes combinatorics.

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

only 1 unrated in top 10 of div2 :o

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

Couldn't make a challenge on time cause my test with a size of 1mb was suggested to be too large. It was really a big surprise.(

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

    You could use a generator?

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

      There were like 20 seconds before the end. I couldn't quickly understand what's the appropriate format. I've never used generators button before, so...(

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

It was fun solving the problems. A different contest from rest ones.

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

Look at this and tell me what is the difference between these two submissions???

http://codeforces.net/contest/554/submission/11741175

http://codeforces.net/contest/554/submission/11746517

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

    It does not allow to view others solution so early so be patient :P

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

      Thanks but both are exactly same except in one solution I have added ios_base::sync_with_stdio and in other one I have removed it. The one with ios_base get wrong answer on pretest one and I wasted exactly one hour to find solution for B (div2) and resubmitted again and it got accepted :( :( I need exactly 20 second to submit C :(

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

        ios_base::sync_with_stdio(false); turns of synchronisation between cin and scanf, which means you cannot use both at the same time anymore.

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

    you initialized the j variables in the second loop differently

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

how do you solve "**Kyoya and Colored Balls**" pls share ur ideas

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

    dynamic programming + combinatorics.dp[i][j] numbers of ways to fit in the first i all the balls from 1-j(all means all c[1],c[2]...c[j])so that at the i-th position I put the last ball of color j.So from that I can say that the last ball of j-1 color can be between 1 and i-1(to respect the condition from problem text)and also I have some space left after coming from dp[x][j-1](x<i),where i can put my c[j]-1 balls(because the last ball of color j is already on ith pos,so the others need to be somewhere in the left spaces). Hope you understood,I let you calculate the final formula :) The main ideea is that you need to place the last ball of some color j on ith position,so you come from a dp[x][j-1](x<j) :)

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

    Just do combinatorics, first place all balls of color 1, this can be done in one way. Then place all colors of color 2, one of them must be behind all of color 1 balls so it can be placed in one way. The rest of them has to be put between all of the previously put balls which is a standard combinatorics problem (becomes choose(placed_balls, new_balls + placed_balls - 1)). The order of the already placed balls doesn't matter so you just multiply together all of these values.

    See this submission:

    http://codeforces.net/contest/553/submission/11739706

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

      can you explain why this is not working for pretest 2: we have balls 1 2 3 4.

      According to formula we take 1 first.

      for next color C(1 + 1, 1) = 2

      for next color C(1 + 2 + 2, 2) = 20

      for next color C(1 + 2 + 3 + 3, 3) = 84

      1 * 2 * 20 * 84 = 3360 and not 1680 as it should be

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

Answer for C is 2^(number_of_components — 1) if answer exists and 0 otherwise.

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

    Can you prove this?

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

      Well any connected component has an unique way of being filled with missing edges. So take two components and a vertex from each one. You have two options, to either make it love or hate, from then on the components are connected and filling the other edges is unique again. So to merge two components you have 2 options, hence the 2^(components-1) to merge them all.

      I don't have a formal proof of it being unique, but it is pretty easy to see it if you work it out on paper

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

        How did you check that answer exists? Because I think that my check is harder than expected.

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

          To check if answer exists assume any two nodes joined by love edge need to be colored with same color and any two edges joined with hate edge need to be colored differently. If you are able to get a valid 2-coloring(doable by a single dfs much like we do for checking bipartiteness of graph) then that particular component is ok.

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

        Oooohhhh.... I didn't think this way. Thanks

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

        let's assume that edge 0 means love and 1 means hate (opposite of input)

        now assignment to the edges of complete graph is valid if and only if you can assign to each node value 0 or 1 such that for every edge its value is equal to the XOR of its two nodes

        so our problem now changes to assigning values to the nodes instead of edges

        for each competent there's exactly zero or two ways to assigns values to the nodes (if you find one assignment then by flipping the values of all nodes of this competent you get the other valid assignment)

        if there's a component with zero ways to assign values to its nodes then final answer is zero otherwise the answer if 2^(number of components) (because we are multiplying the ways of all components)

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

    Div1 C or Div2 C ??

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

What was the idea for problem Love triangles.I was only able to deduce the relations that must hold for a successful match but finding ways seemed to be a distant dream.Anyone?

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

Div 2 problem C was awesome !

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

    How to solve it? I did'n even understand the 2nd example answer, how do we get it?

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

      You have to use multinomial theorem.Take out 1 sample of each colour and then arrange the rest in front of it.Start from color 1 and move behind and multiply the ways you can get it .

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

      http://ideone.com/3FLh1G But I didn't submit it.

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

      my approach is close to DP, suppose we already placed the colored balls 1 ..k-1, then

      we must place one k-colored ball at the end of the sequence and we place the remaining

      k-colored ball among the the 1..k-1 colored ball already placed , which is a classical

      problem of combinatorics

      then we iterate allover the colors and that gives the result

      sorry for my poor english

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

      First all the balls of colors from 1 to i should be put before the last ball of ith color. So let's say that dp[i] gives the no of ways of arranging balls till ith color. Balls of colors from 1 to i-1 are arranged in dp[i-1] ways. There are s[i-1] = (c[1]+c[2]+ .. c[i-1]) balls arranged till now. Also put a ball of ith color at the end. Now there are s[i-1]+1 gaps between the balls that must be filled with c[i]-1 balls. No of ways of doing this tmp = (n+r-1)C(r-1) where r = gaps = s[i-1]+1 and n = balls = c[i-1]-1. Now dp[i] = dp[i-1]*tmp. Answer is dp[k]. Here is the 11741519

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

Was the score of the problem B changed ? Cause I saw a sudden drop in my scores for problem B ? I think something is wrong here

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

After this contest, it reminds me of an amazing word — aftermath!

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

    I didn't find any only-math problem in div 2. they all could be solved non-matematically as well.

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

      In div2, C(div1 A),D(div1 B),E(div1 C) can be solved by maths... C(div1 A) is Combination number. D(div1 B) is Fibonacci number. E(div1 C) is counting the number of bipartite graph. I have solved only these three problems... Therefore I think it is a maths round!

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

        Combinatorics and DP go hand in hand, so I guess that's not entirely mathematical imo.

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

          At first, I have not noticed that the sum of c[i] is not more than 1000... So I think the sum may be as large as one million... I gave up DP and choose factorial numbers to calculate the combination numbers.

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

        OH NOES FIBONACCI NUMBER SO ADVANCED AND COMPLICATED MATH!!

        AND HOW IT IS POSSIBLE TO DERIVE THAT VERY HARD FORMULA THAT NUMBER OF THOSE GRAPHS WAS 2|connected components| - 1!?!?

        SCREW YOU LEWIN FOR THAT AWFUL PROBLEMSET, WE WANT PROGAMMING NOT SOME DIFFERENTIAL EQUATIONS!

        P.S. Sorry if that seems to rude, but that's funny :P. However at least you don't complain that this contest was very bad, because there were only math problem xD (like some guys are sometimes claiming about various contests). Frankly saying, whole competitive programming is math for me :P.

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

          Exactly. There was no difficult formula or some required prior mathematical knowledge to solve a problem. It was all based on observations that you don't need to prove. Really don't understand why people complain that it was too mathy, it was just logical solutions based on observations, just because it's not some by-the-book algorithm doesn't mean it's not programming :)

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

        As I already said once before — try Ad Infinitum contests at HackerRank and you'll realize that given contest is far from math :) Unless you are calling every single programming problem "math", because programming itself is math.

        If somebody says that binomial coefficients, number of n-digit 0-1 strings or fibonacci numbers is advanced math — I have bad news for that person.

        Swistakk said smart things in his message above :)

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

          Hackerrank is a good place to train myself. However, it cost too much time for a Chinese to open the website.

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

    no pun intended

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

    But math is what you love most (:3」∠)

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

Extremely fast system testing phase!

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

For the less mathematically inclined (like myself) :-

Div-2 C / Div-1 A was solvable using DP as well.

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

    can you explain??

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

      My method involved (hint): What must be the color of the last ball in the lineup?

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

      We can go for a DP solution, if we consider the colors in the decreasing order. State --> (colorToUseNext, bank).

      After using the color for the first time (remember we are going backwards), we can add rest of the balls with the same color to our ball-bank (balls of which can be used anytime now).

      Alternatively, we can use a ball from the ball-bank as well.

      The overall idea is to construct the sequence in the reverse order, and filling the current position with either a ball from the "bank", or using a color for the first time (and adding rest of the colors to the bank, to be used later.)

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

Ouch, resubmission penalty with dynamic scoring really hurts.

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

    you react as if pain was inflicted by physical touch !

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

    Yes... For 250's problem, resubmission = 50 penalty = 50 minutes penalty...

    As for 3000's problem, resubmission = 50 penalty = 4 minutes 10 seconds penalty...

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

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

    Math is cool, Math is great, Math is really tricky thing.

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

i think problem D's time-limit has been set by a cruel person :| he just ruined my contest

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

    What is the complexity of your solution? Mine runs in 170ms

    Edit: My complexity is O( (n+m) log n )

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

    There is a solution, which passes comfortably (probably can be optimized to O(n + m)).

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

In life we learn from our mistakes and in this contest i learned that "Every city will have at least one road adjacent to it." does not means the graph is connected :)

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

Ahhhh... 0,5 of wrong submission away from being on Petr's blog third time in a row! I need to do better in Friday contest :P

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

How to solve div.1 E? I think, I know the solution in case of acyclic graph, but adding some hacks for cycles makes this solution TL =(

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

    I tried something like this:

    Let dp[v][r] be a best expectation if we are in vertex v and have r units of time remaining. There is a straightforward way to compute it in O(mt2) by some easy formulas and to speed it up we need to observe that in those formulas there are some convolutions. That means that we can use multiplying polynomials to compute them. However there is a really big problem with, we can't use just one FFT, because we are adding coefficients one by one and we have to be able to update result of multiplication. That can be done and is a really nice (but not that easy) exercise which I will leave up to you (this adds logarithmic factor to complexity).

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

I loved this contest! A lot of problems to think. No theoric problems =). These are the best competitive problems!

I really enjoy the contest, but i have 40 minutes to code problem D from i found the solution and I didn't solve. I need train to code faster the problems =/.

Thanks lewin!

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

It was very difficult to hack in this contest

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

When do we get ratings?

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

is this round unrated? UPD-> rated :)

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

    UPD -> unrated!! New rating is removed!

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

      I say, "I'm violet!" Codeforces says, "Shut up, you are blue forever"
      UPD. I'm violet now :)

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

        Blue-Zoned ? No CF isn't a bitch rated again PS i had same story xD :D

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

Isn't the statement for B wrong considering the intended solution? for example (3 1 2) is decomposed into the cycle (3 2 1) that reorders to (3 1 2) so it is good.

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

    Why does it reorder to (3 1 2)? I think it stays (3 2 1)

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

      some people like me thought that we should sort elements of each cycle in decreasing order in order to make first element is the biggest, but until the last moment I knew that we should make shift to the sequence of the cycle to make the first element is the biggest element

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

        Actually I was one of those people and I thought the whole cycle is sorted in decreasing order, but still arrived to the same solution. Isn't the solution in both cases the same, or was I just lucky?

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

          since I assumed that we should sort elements of each cycle in decreasing order I assumed that for example 3 1 2 5 4 is not one of the permutations that we should count because (3 1 2) is not sorted in decreasing order

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

            But {3 1 2 5 4} indeed shouldn't be counted.

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

              it turned out that I still don't understand the problem

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

          If you sorted the whole cycle, you would count 3 2 1 5 4 for example, which you shouldn't.

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

            No, you wouldn't. It changes: 3 2 1 5 4 -> (3 1)(2)(5 4) -> 3 1 2 5 4

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

              Yep, indeed, the solution for both seems to be identical so the "confusing" statement ain't an excuse :P

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

              Point taken. I guess this problem was easier if you were more familiar with cycle notation; I made a similar mistake during the round (I understood the statement correctly though). :/

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

          Yes, the solution for both the cases was same.

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

    reordering of (3 2 1) is (3 2 1) itself.

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

    You cannot reorder cycle in that way, because links between elements of permutation are directed.

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

      Maybe it's just unusual wording, but aren't "reorder the elements within cycle" and "cyclically shift the elements in cycle" different things?

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

        Hmm, from that point of view they look different for me, agree with you.

        However, there was a clarification about that (around 54 minute of the contest): "In order to get standard cyclic representation, you should write elements of each cycle in order of cycle starting from the largest element of the cycle (not just in decreasing order)."

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

        Sorry for the confusion. I will remember this wording in the future. Also, another thing that I could have done was to make the standard cyclic representation in the statement not be in decreasing order.

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

    If (3,1,2) is not considered a valid permutation, then problem statement is wrong. It only asks to reorder elements in a cycle such that largest should be at the beginning, so (3,1,2) upon reordering will stay the same. The clarification was not clear to me.If it meant that you have to sort the cycle in decreasing order , then of course (3,1,2) is invalid as it reorders to (3,2,1) which is different.

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

Thanks to the organizers of this round, problems was very interesting. I hope you will invite us to your new Codeforces rounds in future :)

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

Really glad to see top5 in Div2 without a single newly registered user :)

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

What's wrong? I became div1 and then rating changes are undone and am div2 again.

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

For some reason my rating increased by 77 and then went back down a few minutes ago to what it was before the contest. Is the contest unrated?

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

    Same here, my rating changed and then came back. What happened?

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

    Yay it went up again! :D

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

      Yes it did. However, I gained 38 rating points in the previous rating update. This time I gained one less rating point, although my rank went up by one :P

      It seems like they caught one cheater :)

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

Had become Candidate Master for the first time. I thought it would last for at least 1 contest. :P I should have saved the screenshot.

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

    You can save it now :P All rating changes have been rolled back. (for sometime I guess)

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

For me solving div2 D (div1 B) was completely random. Observing the complex problem statement I've implemented precalc which filters valid permutations out of all the permutations (with std::next_permutation) and then I've noticed the Fibonacci sequence :)

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

Where are the rating points gone ?!

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

Div 1- Ques B

In Testcase 5, the result for (10,57) is 2 1 3 4 5 6 7 8 10 9

When I generated the sequence using my cod, the following is the output. Where is it wrong?

(10,1) -> 1 2 3 4 5 6 7 8 9 10

(10,2) -> 1 2 3 4 5 6 7 8 10 9

(10,3) -> 1 2 3 4 5 6 7 9 8 10

(10,4) -> 1 2 3 4 5 6 7 10 9 8

(10,5) -> 1 2 3 4 5 6 8 7 9 10

(10,6) -> 1 2 3 4 5 6 8 7 10 9

(10,7) -> 1 2 3 4 5 6 9 8 7 10

(10,8) -> 1 2 3 4 5 6 10 9 8 7

(10,9) -> 1 2 3 4 5 7 6 8 9 10

(10,10) -> 1 2 3 4 5 7 6 8 10 9

(10,11) -> 1 2 3 4 5 7 6 9 8 10

(10,12) -> 1 2 3 4 5 7 6 10 9 8

(10,13) -> 1 2 3 4 5 8 7 6 9 10

(10,14) -> 1 2 3 4 5 8 7 6 10 9

(10,15) -> 1 2 3 4 5 9 8 7 6 10

(10,16) -> 1 2 3 4 5 10 9 8 7 6

(10,17) -> 1 2 3 4 6 5 7 8 9 10

(10,18) -> 1 2 3 4 6 5 7 8 10 9

(10,19) -> 1 2 3 4 6 5 7 9 8 10

(10,20) -> 1 2 3 4 6 5 7 10 9 8

(10,21) -> 1 2 3 4 6 5 8 7 9 10

(10,22) -> 1 2 3 4 6 5 8 7 10 9

(10,23) -> 1 2 3 4 6 5 9 8 7 10

(10,24) -> 1 2 3 4 6 5 10 9 8 7

(10,25) -> 1 2 3 4 7 6 5 8 9 10

(10,26) -> 1 2 3 4 7 6 5 8 10 9

(10,27) -> 1 2 3 4 7 6 5 9 8 10

(10,28) -> 1 2 3 4 7 6 5 10 9 8

(10,29) -> 1 2 3 4 8 7 6 5 9 10

(10,30) -> 1 2 3 4 8 7 6 5 10 9

(10,31) -> 1 2 3 4 9 8 7 6 5 10

(10,32) -> 1 2 3 4 10 9 8 7 6 5

(10,33) -> 1 2 3 5 4 6 7 8 9 10

(10,34) -> 1 2 3 5 4 6 7 8 10 9

(10,35) -> 1 2 3 5 4 6 7 9 8 10

(10,36) -> 1 2 3 5 4 6 7 10 9 8

(10,37) -> 1 2 3 5 4 6 8 7 9 10

(10,38) -> 1 2 3 5 4 6 8 7 10 9

(10,39) -> 1 2 3 5 4 6 9 8 7 10

(10,40) -> 1 2 3 5 4 6 10 9 8 7

(10,41) -> 1 2 3 5 4 7 6 8 9 10

(10,42) -> 1 2 3 5 4 7 6 8 10 9

(10,43) -> 1 2 3 5 4 7 6 9 8 10

(10,44) -> 1 2 3 5 4 7 6 10 9 8

(10,45) -> 1 2 3 5 4 8 7 6 9 10

(10,46) -> 1 2 3 5 4 8 7 6 10 9

(10,47) -> 1 2 3 5 4 9 8 7 6 10

(10,48) -> 1 2 3 5 4 10 9 8 7 6

(10,49) -> 1 2 3 6 5 4 7 8 9 10

(10,50) -> 1 2 3 6 5 4 7 8 10 9

(10,51) -> 1 2 3 6 5 4 7 9 8 10

(10,52) -> 1 2 3 6 5 4 7 10 9 8

(10,53) -> 1 2 3 6 5 4 8 7 9 10

(10,54) -> 1 2 3 6 5 4 8 7 10 9

(10,55) -> 1 2 3 6 5 4 9 8 7 10

(10,56) -> 1 2 3 6 5 4 10 9 8 7

(10,57) -> 1 2 3 7 6 5 4 8 9 10

(10,58) -> 1 2 3 7 6 5 4 8 10 9

(10,59) -> 1 2 3 7 6 5 4 9 8 10

(10,60) -> 1 2 3 7 6 5 4 10 9 8

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

    (10,4) -> 1 2 3 4 5 6 7 10 9 8 is not valid

    The cyclic sequence will be (1)(2)(3)(4)(5)(6)(7)(9)(10 8)

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

      ok got it , thanks.

      I read the ques wrongly.

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

Rating update (1699) :O ... i would have gotten this point if i would have entered the contest without 8 minutes temporary unavailable :'(

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

Either I am stupid or div 2 D is actually hard to understand. I still don't understand what the question wants me to do.

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

Very cool problemset, thank you :).

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

The problem set was awesome, loved to solve it :)

→ Reply