zscoder's blog

Codeforces Round #369 (Div. 2)
By zscoder, history, 8 years ago, In English

Important Update: Our friends have noticed that the upcoming round collides with their contest and also weekend is full of many another contests, so the round is now moved to Monday, 29 August 2016 15:05 MSK. We are sorry for the inconvenience caused and hope that you'll understand us.

Hi everyone!

Codeforces Round #369 (Div. 2) will take place on 27 August 2016 at 16:05 MSK. As usual, Div.1 participants can join out of competition.

I would like to thank danilka.pro for helping me with the preparation of the round, MikeMirzayanov for the amazing Codeforces and Polygon platforms and also Phyto for testing the problems.

I am the author of all the problems, and danilka.pro also helped making one of the problems harder. This is my first round on Codeforces! Hope everyone will enjoy the problems and find them interesting. It is advisable to read all the problems ;)

In this round, you will help ZS the Coder and Chris the Baboon while they are on an adventure in Udayland. Can you help them solve their problems? :)

Good luck, have fun, and wish everyone many Accepted Solutions. :)

UPD : Also thanks to IlyaLos and HellKitsune for testing the problems too.

UPD 2 : There will be 5 problems and the scoring is standard : 500-1000-1500-2000-2500.

UPD 3 : Editorial

UPD 4 :

Congratulations to the winners :

Div. 1 winners :

  1. matthew99

  2. uwi

  3. Egor

  4. Um_nik

  5. kmjp

Div. 2 Winners :

  1. zhabo

  2. ysy_ioi_pengbei

  3. YangJunzhao

  4. lych_cys

  5. Zharaskhan

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

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

Timing although nice collides with Codechef lunchtime (•_•)

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

    The time has been changed to not collide with the lunchtime round.

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

      Now it's 3pm in timezone of most participants. Is it possible to launch round as usual?

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

        You can't say "most participant". The usual staring time isn't good for some countries too. There just cannot be a starting time which is good for everyone.

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

          That's because the Earth is a sphere. However, I think the time before Russia changed the time zone will be better than now.

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

        And still >7k participants. It seems there are people who like this time.

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

Since it's impossible for everyone to have a positive rating change, I wish high rating for everyone who deserves it and has been working hard.

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

Good to see zscoder start writing regular rounds now. I wonder what interesting problems he has in stock.

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

I wish not to see "unrated user" in top_10

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

Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).

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

Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).

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

Time not collide with contest lunchtime... Please don't play with my feelings.

UPD : Nevermind, Thanks for update...

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

Could you please postpone the contest a little bit? Something like 19:00 MSK would be great for everyone, because some of us are still working at 15:05 MSK.

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

    And another part of us are not able to participate in evening. It is like rating updates — even if everyone have solved all problems, it is impossible to increase everyone's rating. For someone it will be bad, for another it will be good

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

    19:35 MSK in my local time is 00:35,it's difficult to please everyone ：）

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

    It is a great time for East Asia time zone though, it's roughly 21:05 over here. You can't imagine how thankful I am to see and participate a round ending before the clock hits 12.

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

      Things are not always same.. ... I will be thankful if the contest starts after 22:00.... We all have some job to do :)

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

        More or less I think we can agree that starting before 00:35(the usual time) is a great idea. =D

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

Is the contest delayed for 3 days or is this a bug/mistake ?

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

    I think it's a feature.

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

    Reading the announcement before posting a comment would be a great idea.

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

    There is a bold Important Update which means you should read it and it's important

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

    This post was made right after the time was switched. It probably done while/right after the author made the post. I believe at the time of posting it there was no update.

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

Will problems be in russian language?

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

    I think if a contest is in russian, they will say it in announcement ... and why should it be ?! author of contest is not from russia.. and a lot of people don't know russian !

    UPD : I am so sorry about what I said... I didn't mean something bad ... It's just because I don't know English well...

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

      The problems are always translated in russian or english by the coordonator,you can read them in both languages.

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

contest time change .....:(

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

The first thing that I saw here was arithmetic-progression tag :/

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

Where is contest tomorrow?!

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

Thanks a lot zscoder i was just wondering how i would be able to give 3 contests with time colloiding with each other in a single day + i have an annual day also tomorrow of cse society and as last contest cost me too much -ve rating and i want to become expert again so can't afford to miss a regular round....

U solved my problem and also of many i think...so thank u so much zscoder:)

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

Thanks, Monday is better!!

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

Hopefully not a stupid question. What contests are there overlapping?

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

Oh now I won't be able to participate anymore :( sadlife

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

"wish everyone many Accepted Solutions", that's a joke right !?

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

why change the contest to 8.29？？？？？？excuse?

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

    This is because of the many contests that are being held in this weekend (one of which clashes with the original time) so this is to allow everyone to have a chance to participate in all of them instead of being forced to choose between the clashing contests.

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

your problems in educational round are always among the most interesting problems I've ever met. Hope your round will be interesting too! 710E - Generate a String 691E - Xor-sequences 665E - Beautiful Subarrays 678D - Iterated Linear Function

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

Please try to give a constant time for next rounds...

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

this guy has 2 Bronze medal in IMO
his results
so...

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

    So, we should wait for lots of math problems :P

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

Why this round delay?

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

1.29 August 2016 15:05 MSK.
2.27 August 2016 at 16:05 MSK.
3. Aug/29/2016 18:05UTC+6.
Which is perfect time??????

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

Perfect timing of a contest...:-) thanks for shifting the contest.

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

List of Contest, if someone need (^_^)

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

Awful time. It's a middle of working day in Europe!

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

Where is our Gleb? :P

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

Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).

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

Great , I'm so happy , Monday I can participate !!

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

كل تاخيره و فيها خيره :D

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

Chinese people will be glad to participate this round. It's on 20:05! The earrrrly time means we can almost see the rating changes!

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

I love arithmetic-progression :D

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

can U please put the contest 2 hour later? i and 37 of my friends are in class in this time and we really want to participate in this contest! thanks!

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

    well, he can't satisfy all the pepole :p

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

      Why people use this argument? Is it possible to check the distribution of participants among countries and answer that question once and for all?

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

        Fine, go ask 40,000 users about their preferred time :3

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

          Is it the only way that comes to your mind?

          People specify the region in their's profile. For example, you are from Lattakia in Syria. Lattakia has the time UTC+02:00 which is the same as in Moscow (I didn't know that before :) ).

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

            But Moscow is UTC+3

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

              Yes, but current time is still the same — that is what I found interesting.

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

Keeping the previous problems in mind which are provided by the problemesetter zscoder in various educational round , i hope that today's round is going to be fantastic, wish you all positive rating change :)

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

Again 7k+ contestants :) i hope there won't be long queue!

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

    Probably many registered for the previous date and won't be able to attend the contest.

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

Contest time is so bad, I hope change it to the usual Codeforces rounds time :(
(there is electricity outages in Syria in this time :p)

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

pray for being specialist .!

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

Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).

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

7.5k regitered users, hope there won't be a large queue..

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

    > 8k XD

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

      8.3k till now, the queue will be sooooo large, I hope the servers won't break :\

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

could you delay the contest till i finish my ice cream

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

First round exceeds 8k

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

How many people feeling lazy for contest?

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

More than 1000 unrated users :/

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

WOW!! 8000+ contestant already registered.

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

8385 registration !!! Is it the highest ever ? WOW... way to go CF.. Love this platform.

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

Very cool problems. (I liked problem C and D more)

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

    I can't solve D, but my mind is same!

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

    can u please explain how to solve C and D

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

      c dp[n][m][k], where n-the number? we want to paint, m-color,k-how pretty ! dp[i][j][x]=min(dp[i-1][j][x],dp[i-1][1..m!=j][x-1) if color[j]!=0; else dp[i][j][x]=min(dp[i-1][1..m!=j][x-1);

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

      D:

      Let ans = 1 Count number of cycles and store in what cycle is a vertex. If a vertex doesn't belong to any cycle then reversing the edge won't matter so that contributes ans = ans*2 to the answer

      Now if there is a cycle that contains k different vertex, then you have to reverse any of its edge so possibilities are 2**k — 2 (1 for no reversal and 1 for all reversal) So ans = ans * (2**k — 2)

      Do this for every vertex that is not part of any cycle and for every cycle

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

        Isn't it possible that when you flip edges not in a cycle you end up with another cycle?

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

          No it isn't. It is a functional graph (just one edge from each vertex) So if you suppose have a edge u->v and if you reverse it to v->u then any path going through v will just stop at u and won't move any further.

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

          No it isn't. It is a functional graph (just one edge from each vertex) So if you suppose have a edge u->v and if you reverse it to v->u then any path going through v will just stop at u and won't move any further.

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

      Here is my dp solution: 20251359.

      I think, it's hard to explain :)

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

    Could you explain it to me?

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

      If my solution is correct answer is Product((2^cycle_len — 2)) * 2^unused.
      unused = vericles outside cycle.
      cycle_len = length of cycle.

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

        i tried that and got wrong on 9

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

          Strange, mine passed pretests. Maybe you have bugs?

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

            cycles = strongly connected components?

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

              No, just simple cycles like 1->2->3->4->1.

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

                that`s what i did wrong

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

        What is Product? And if we have many cycles?

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

          There is at most 1 cycle in the graph. I just realized it post contest -_-

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

            No, e.g.

            4
2 1 4 3

            There may be many but they are disjoint.

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

    Please explain how to solve those two problems

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

    Problem C :

    DP[i][j][k] = minimum cost to color first 'i' trees such that the color of the ith tree is 'j' and beauty is k .

    transitions are easy to think .

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

    how did you solved D, i tried finding all strongly connected components and then and then using formula (2^k1-2)*(2^k2-2)*....*(2^kx-2) where x is the number of strongly connected components, ki — size of the k-th component and if a component has size 1 i multiply it with 2

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

      I came up with the same idea but got that you have to consider the opposite edges and it makes that all the vertices are in the same scc :(

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

      Can someone confirm your solution or prove its correctness? my solution was something similar.

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

let's wait and see how many div2 B solutions will fail at test n = 1

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

How to solve E ?

Wilsons theorem ?

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

    Div1E:

    (B - A) / B = (2N - 1)(2N - 2)...(2N - K + 1) / 2N(K - 1)

    The denominator (B) is a power of 2, so for it you just need to count how many 2s you need to remove both from A and B (using modular inverse!). For (B-A), you can compute it straightforwardly in a loop but early break if you get 0.

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

      how did you come up with that ?

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

        It is quite straightforward. First one goes to any place, the second one can go to 2N - 1 places to avoid collision, third one has 2N - 2 free places, etc.

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

          I meant how did you derive the formula ?

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

            Consider the amount of days and the chances of any two of the people in the set doesn't have the same birthday. Do some maths and you will end up with this formula.

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

      I had the same idea but i didn't know how to find the numerator ?! how ?

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

      Wait... but (2^N-1 % MOD)(2^N-2 % MOD)...(2^N-K+1 % MOD) doesn't have the same amount of 2s as the values that are not under %MOD right....?

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

      why the formula is , but not , or why do we say that order here matters?

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

    I get hit by pretest 4 so I probably missed out some exceptions in my last few minutes, but I strongly believe that my approach is correct.

    For B, the value is (2^n)^k (before modulo 1e6+3, of course), it is not hard to prove, since there are (2^n) days and k people in the set, so this is the total case.

    Denote A' as B-A, this value is (2^n)! / (2^n-k)! as we consider that the days are not clashing with each other.

    To calculate A', you can just use a for loop from (2^n-k+1) to (2^n) to get the value, note that since MOD = 1e6+3, when you hit something that is divisible by MOD, just return 0.

    The only part I failed is to make A' co-prime with B by counting the 2's in the for loop, but note that I am using values that are under modulo MOD so the amount of 2's are not exactly correct.

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

    The combinatoric(probabilistic) problem wasn't too hard.

    Answer is

    The real problem i think is compute this value modulo mod.

    Notice than when k >  = mod the term that involves factorials is equal to 0, so answer isn't that hard in that case, but remains the problem of reduce the fraction. The only prime factor of the denominator is 2, so you need to find the biggest p such that 2p divides the numerator. Then multiply both num and den for the multiplicative inverse of this number and voila...

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

Hats off to zscoder for such an awesome problemset, especially problem D :)

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

    can you explain your solution?

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

      For each component of the graph, because it has x vertices and x edges, there exists exactly one cycle. In this cycle, by switching edges, the only way you can end up with another cycle is if you don't switch any edges, or you switch all of them. So if the cycle has y vertices, you have (2^y — 2) valid sets of edge switches. And it's not hard to find the cycle length with a simple dfs.

      You can also notice that for every other edge it doesn't matter if you switch it or not, so for a component of size x with a cycle length of y, the answer is (2^y — 2) * 2^(x — y). All that's left is to multiply the answers for every component of the graph.

      Hope I helped.

      Edit:

      Submission: http://mirror.codeforces.com/contest/711/submission/20253554

      Complexity is O(n)

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

        Wow! It was one of those problems where the difficult part is that you have to make important observations and the rest is easy.

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

    How to solve D? My solution used strongly connected component. Got WA in testcase 4 -__-

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

    Could you explain yours? I tried to find the cycles with some special properties of the problem within the designated time but can't find the solution :(

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

I solved A , B in 16 minutes and didn't solve C. It seems like it is very easy as a lot of people solved it. But how did you handle something like that ? (3 3 3)

(0 0 0)

(1 200 200)

(1 1 1)

(1 200 200)

With my approach it was so hard to be handled because after the putting the colors that will give me the minimum cost I start to change the current beauty to be beauty + 1 or beauty -1 in every step until I reach set == k.

But this case will require from me to change the beauty by 2.

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

    dont really know what you mean by "set" , but it can be solved by dynamic programming .

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

      I thought about solving it with DP , but the problem was that I need to save which colors I have used so Far which cannot be saved as it will be 2 ^ (colors)

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

        You can use each color multiple times.

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

        For an index i, you only need to know what color was on i-1 index. So you could do dp with (n, no of segments, lastcolor) as states. You can choose any of noofcolors for index i if it is not colored.

        So complexity: O(n*segments*color*color)

        I just hope it don't give tle if there are no prunings done :|

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

        Thank you very much , I understood something wrongly :)

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

        You only need to store the color of the last element to know if you increase the number of groups or not.

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

Couldn't submit D because the servers were slow during the last 60 seconds ;_;

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

*Reads Problem E

*Notices a way to calculate large factorial is needed

*Ready to rant for requiring knowledge about an algorithm that I probably won't need it again.

*Notices that since MOD is only 1e6+3 so things could be simplified at the last minutes

*QWERTYUIOPLKJHGFDSAZXCVBNM obviously didn't coded quick enough and fail

Keep on observing till the last moment guys...

This is a pretty decent problem set anyways, I'm lovin it. =]

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

What was pretest 7 at D?

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

I tried to hack this 20246021 twice, as it uses int but he gives the correct output and no overflow happened!!

could anyone explain why that happened?!

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

    Your hack is wrong, I guess. Operations on 32 bit integers normally wrap around. Can you share your hack with us?

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

      the 1st hack the 2nd hack

      what do you mean by "Operations on 32 bit integers normally wrap around", could you explain that?

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

        Take a look at this. Normally the result of addition, subtraction and multiplication on ints will still be correct modulo 232. And if the final solution is less than 231, the calculated value will be correct.

        The problem with the second code is that the compiler is able to deduce that the loop will result in undefined behavior, so the compiler can basically do whatever it wants. In the first code, the compiler cannot deduce anything (because of user input) and no weird "optimizations" will occur. The machine code generated will simply use the ADD x86 instruction (or perhaps the MUL instruction), which on x86 produce the correct result modulo 232.

        I warned everyone not to expect such crazy undefined behavior (for example when hacking solutions) but I got booed off

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

      10

      0 536870913 536870913 536870913 536870913 536870913 536870913 536870913 536870913 1

      536870913 1 536870913 536870913 536870913 536870913 536870913 536870913 1 536870913

      536870913 536870913 1 536870913 536870913 536870913 536870913 1 536870913 536870913

      536870913 536870913 536870913 1 536870913 536870913 1 536870913 536870913 536870913

      536870913 536870913 536870913 536870913 1 1 536870913 536870913 536870913 536870913

      536870913 536870913 536870913 536870913 1 1 536870913 536870913 536870913 536870913

      536870913 536870913 536870913 1 536870913 536870913 1 536870913 536870913 536870913

      536870913 536870913 1 536870913 536870913 536870913 536870913 1 536870913 536870913

      536870913 1 536870913 536870913 536870913 536870913 536870913 536870913 1 536870913

      1 536870913 536870913 536870913 536870913 536870913 536870913 536870913 536870913 1

      This is the case I found.

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

        Would it be possible to get test case #117 for this problem? My solution for some reason did not pass it :(submission/20233549

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

I figured out the solution for problem D. Unluckily couldn't complete the code on time.

It is easy using DFS to find the number of edges that form the circle, let's name it cEdge.

Notice that if we choose the sets that contain the circle edges, after flipping, the circle remains.

So the answer = Number_of_all_subset — Number_of_subset_doesn't_contain_all_circle_edge = Pow(2,n) — 2*Pow(2, n — cEdge).

It this solution were right, I would be a little bit sad. Cause this is the first time I was this close to problem D.

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

    You're correct, but note that you can have multiple weakly connected components and thus multiple circles:


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

    It's right, but you need to do this not once, but for every connected component of the graph, and multiply these answers.

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

Please help me with the second question (Div. 2) and tell me what I did wrong? http://ideone.com/6HDQwQ

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

    your solution gives -1 in : 1 0

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

    Check:

    3

    3 3 3

    3 0 3

    3 3 3

    answer is 3, you are printing -1

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

Wasted a lot of time on B and C, I think I could have solved D if I was a little faster :(

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

Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).

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

Almost everyone has implemented a O(n^4) dp for problem C,I just hope it doesn't pass else it would be very unfair..how could 10^8 iterations pass...there are many problems on codeforces where a similar complexity has given TLE.

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

    It's a Div2C for a reason man.

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

      I can show a variety of Div-2C problems where such a complexity has given a TLE, MAN!!!

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

        Calm down. I mean it is not meant to be extremely challenging.

        Sorry if you feel that you are offended by my previous comment.

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

        Send me problems where there is no high constant factor, and 10^8 fails on CF servers.

        (No sarcasm intended). 10^8 just always pass.

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

    TLE: 2 seconds. Also codeforces servers are pretty fast + almost no constant factor.

    The only thing i worry is all operations are on long long int though

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

    usually you can pass 10^8 iterations! you can even 10^8 * 5 of them! but I think there is a O(n^3) dp!

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

      There is indeed an O(nmk) solution.

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

      Yes, the inner loop iterates on colors. When you want to break the previous group and start the new one, you need to compute the two minimum costs over all possible colors of the previous group. And then iterate again on possible colors of new group and use one of the two minimum costs.

      That is, you make two consequent loops instead of two nested.

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

        ...and I didn't have the balls to do the extra work, and I still failed regardless of the optimization.

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

    Didn't actually try O(n^4). I thought it might blow up. So I tried for MORE THAN AN HOUR to bring the complexity down to O(n^3). (Using subtle techniques. Thus difficult to debug.) Consequently, I didn't have time for Problem D and E.

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

Can anyone explain C ?

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

    Use a dp array

    dp[tree][color][set_count]

    Just handle the transfer between states carefully and you are set. (Note that the constraints are VERY small)

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

      Can it run in O(1e8) ? I used 4 for loop. Hope it'll pass

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

        Yes, it's fast for cf

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

          normally what's the limit?

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

            It's about 1e9/s. Usually TL won't be that tight since there are constant factors so consider 1e8/s.

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

        I remember, when i can't hack solution with 1e9 operations!

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

          That is true — "1e9" takes here around 1s (anyway it depends on complexity of operations)

          Some simple iteration + summing would do that, anyway I doubt 1e9 load/store operation would be that successful.

          Anyway 1e8 shall be OK with much complex operation (especially considering it might be considerably reduced by a constant)

          Have nice day ^_^

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

            Thanks, you too!

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

            How can we know in general the number of iterations we can do ? For instance 1GHz means how many iterations ? Thanks :)

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

              Do you know asymptotic(o())? So the number of iterations is the max possible asimptotic! As example, if n=1000 and o(n^2) then number of iterations near 1000000

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

                If you mean time complexity yes I know. I was just asking how can we know in general how many iterations we could do.

                Because here I had the solution for C in O(nkm^2) but I thought that I could do only 10^6 operations so I didn't even try to submit it

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

                  Here you can make above 2e9 primitive operations!

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

                  Thanks.

                  So what is a primitive operation ?

                  For instance addition, comparison,.. are worth how many primitive operations ?

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

                  =,+=,-=,*=,&,|,^,-,+,*,<<,>>,all comparison! I think it's all

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

                  Thanks !

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

                  You're welcome!

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

http://mirror.codeforces.com/contest/711/submission/20254708 Some one please tell me why this timed out ?

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

    Good day to you,

    it became "stuck" in your "do-while" cycle

    Try following input

    5
2 3 1 1 4

    Good Luck ~ Have nice day

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

Rant: Hate it when forgot to uncomment a line that i commented out during debugging

But atleast it shows up in pretests xD and i could fix it :D

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

C was the first DP problem that I've solved during the contest thank you zscoder

self-confident level is rising.

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

Finally, I am going to be blue! :D

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

Problem B was so tricky

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

Pain is solving 4 problems and then getting "WA on 105" _/_

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

Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).

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

Can someone tell why did I get WA on 105.
http://mirror.codeforces.com/contest/711/submission/20244876
Its not clear from the test case what's wrong.

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

    Not sure if that's the reason.

    But here you call answer by reference, but you don't save it in the memo table in the first if condition. I think this should cause TLE and not WA though.

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

      Yups I saw that. But WA isn't the outcome of it.

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

        It looks like your submission is being re-judged ? It's re-running test 1 again.

        Edit : It is accepted. I guess that makes you x100 happier now. Congrats!

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

    Rejudged. Congrats! Ratings will be adjusted tonight.

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

Can someone tell me what's wrong with my code? 20239552

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

    You are doing a[x][y]=(r[(x+1)%n]-r[x]); what if 0 is in last row. r[x + 1] = 0 in that case.

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

    vector< long int> r(n),c(n);should be vector< long long int> r(n),c(n);

    long int d1=0,d2=0,s=0;should belong long int d1=0,d2=0,s=0;

    Those sums can reach 500*10^9=5*10^11 which overflows 32-bit integer. UPD:a[x][y]=(r[(x+1)%n]-r[x]);t=a[x][y]also causes overflow.

    Change it to t=(r[(x+1)%n]-r[x]);

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

Yes!!!! Specialist finally...next target :- Expert

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

O(n*k*m^2) in C! Really? 10^8? I didn't believe that it will pass all the tests and wrote something strange... Now I don't understand how my code passed pretests. Anyway, problems were very nice. Thank you

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

    10^8 with simple operations can pass with only 1s
    they gave you 2 seconds
    anyway, if they want you to solve it in o(n^3) complexity then they would give 500 for n and just 1 second

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

      I didn't know this before. It is usual for me, that test system can't pass more than 10^7 operations, so it was a good lesson :-)

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

I like the problem c,my dp is weak.i didn't solve it in contest,the problem c help me improve my mind,and the time is really really nice, thanks a lot

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

Hi.

This is about Problem B. I'm stuck at the test 93, and the test data is:

3

1 15 5

11 7 3

9 0 13

The correct answer is 1. However I think the answer should be -1.

Could anybody explain this for me?

Thx.

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

    Nope.

    Sum across second diagonal = 21

    Sum in last row = 23

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

      Wow...Sorry...I submit the wrong file after the contest...

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

    The correct answer is -1. As can be seen in 20259409

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

      Wow...Sorry...I submit the wrong file after the contest...

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

Problem C I though n*k*m^2 couldn't pass so I didn't do the solution. New lesson of analyzing bigO notation

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

I have a tendency of writing recursive solutions for DP problems. Will that be cause any problem in near future? Here is my accepted solution for DIV 2C (Complexity O(NKM2)). Can anyone help how to modify the same recursive solution so that complexity is reduced to O(NKM).

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

    I have been told that it is always better to have an iterative code because it is easier to make sure you don't compute the same thing twice and you can have stack overflow with a recursive function. But I am no expert if someone knows it better ...

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

      Good day to you!

      I think it is (in MOST cases) up to you [what fits you better].

      The advantages of "iterative" method are, that is is faster (by a constant — not that much but it is SOMETHING).

      The "stack problem" is usually on, only if it is "1D" Dynamic Programming with N greater than 10^5 — anyway it can be prevented by executing DP a few times (you can execute the recursion with 10^5,2*10^5,3*10^5...etc in a loop, so there won't be more than 10^5 depth {or you can do this with custom depth — it doesn't cost any asymptotic complexity :) })

      The same thing will never be computed twice (in any of the methods), anyway a "thing" might be asked more than once in recursive form (anyway as it is computed it ends in O(1) )

      I (personally) prefer recursive method over iterative [it is easier for me to see the solution] — but as I said, it is personal matter.

      An advantage of recursive DP is, that it is more easy to do a DP, in which the whole "state-space" doesn't fit into array, but you will use only "part" of it [with assist of "map"]. Also it is more easier, whenever the parents are somehow "variable" — not fixed :)

      So the asymptotic complexity of both methods is same, and most of the things can be (somehow) converted to other method to make it working — so unless you are (for a reason) hunting every "ms", then it is only matter of personal preferences!

      Good Luck & Have Nice Day :)

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

nice

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

Is there a bug in the contest ?!
Rating changes are removed !! zscoder MikeMirzayanov

UPD : The bug is fixed now.

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

    My rating changes are returned. :) You can try to refresh the pages.

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

did the round become unrated ?! or is it just a bug ?

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

11 days till the next contest !:/

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

    Great, now at least my exams will be over :D

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

    and it collides with icpc first phase in south america :(

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

it's really frustrating that next contest is 10 days away.

→ Reply