Блог пользователя Lewin

Автор Lewin, 6 лет назад, По-английски

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

 
 
 
 
  • Проголосовать: нравится
  • +567
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +132 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +60 Проголосовать: не нравится

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.

»
6 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

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...

»
6 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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.

»
6 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

Finally, Div.1 come!

»
6 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

eagrly waiting for div 2 intresting problems.. :)

»
6 лет назад, # |
  Проголосовать: нравится +67 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

My first Div1 :D

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится -48 Проголосовать: не нравится

Izi problem, izi life

»
6 лет назад, # |
  Проголосовать: нравится -37 Проголосовать: не нравится

i didn't participate in tc for almost 5 month

»
6 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

good round but bad time :(

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +610 Проголосовать: не нравится

Just a pic about my CF contest style:

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

I think this contest have At least one Geometric problem

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

gl & hf!

»
6 лет назад, # |
  Проголосовать: нравится -53 Проголосовать: не нравится

I belong to the first...

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
    main(){
      itoa(2, col, 2);
      if(strcmp(col, "10") == 0) mark ++;
      else mark --;
      printf("%d", mark);
    }
    
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +12 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +160 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится +78 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -21 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope I become Expert in this round

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Izi problem, izi life

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Scoring? . . .

»
6 лет назад, # |
  Проголосовать: нравится -29 Проголосовать: не нравится

beijing-----》00:30,shi fen dan teng!!(Very egg pain!!)

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

1

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Codeforces is temporary unavailable ... :(

»
6 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

will this be an unrated round ?

»
6 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Ненавижу аниме

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +180 Проголосовать: не нравится

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 :(

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится -25 Проголосовать: не нравится

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.

»
6 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

Feeling like back in Permutation and Combination classes :(

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 ;(

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Div1A felt harder than Div1B :(

»
6 лет назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

Nice problems, looking forward to your next round ;)

»
6 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Lots of fun Math in this contest!

»
6 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I wish I read the announcement...

»
6 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +7 Проголосовать: не нравится
»
6 лет назад, # |
Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      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!

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

didn't like at all. Mostly math problems. is it mathforces or what?

»
6 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Sorry, can't see your code yet

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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).

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Спасибо авторам за хорошо проведенное время!

»
6 лет назад, # |
  Проголосовать: нравится +71 Проголосовать: не нравится

Someone really likes combinatorics.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

only 1 unrated in top 10 of div2 :o

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.(

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You could use a generator?

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

      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...(

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 :(

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          ohhh!! Hell sorry I didn't know about that :( :(

          1 mistake cost me 1 question I will remember this forever now.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    you initialized the j variables in the second loop differently

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    it's that line

    ios_base::sync_with_stdio(false);
    
»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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) :)

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.com/contest/553/submission/11739706

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you prove this?

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится +13 Проголосовать: не нравится

          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.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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)

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Div1 C or Div2 C ??

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Div 2 problem C was awesome !

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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 .

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

      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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Looking forward to seeing editorial for it.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

      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!

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +54 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          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 :)

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +16 Проголосовать: не нравится

        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 :)

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    no pun intended

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

Extremely fast system testing phase!

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For the less mathematically inclined (like myself) :-

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    can you explain??

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.)

»
6 лет назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

Ouch, resubmission penalty with dynamic scoring really hurts.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    you react as if pain was inflicted by physical touch !

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

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

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Я разочарован, не мог зайти на codeforces перед раундом, соответственно не зарегистрировался и не участвовал

»
6 лет назад, # |
  Проголосовать: нравится -35 Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +79 Проголосовать: не нравится

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 :)

»
6 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

del

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я не увидел обращения к -1-ому элементу, но переполнение... Могу предположить лишь то, что умножение двух int'ов по сути выполняется по модулю INT_MAX. Тогда все становится на свои места. Но это лишь предположение.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    а где там переполняется.

    int * long long == long long

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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 =(

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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).

»
6 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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!

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It was very difficult to hack in this contest

»
6 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

When do we get ratings?

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

is this round unrated? UPD-> rated :)

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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?

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
                Проголосовать: нравится +11 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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). :/

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Yes, the solution for both the cases was same.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -9 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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)."

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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?

»
6 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 :)

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Where are the rating points gone ?!

»
6 лет назад, # |
  Проголосовать: нравится -32 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can I ask about the 10 minutes that you added to the contest duration . did you took that in consideration while rating after contest or not ?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Very cool problemset, thank you :).

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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