witua's blog

Codeforces Round #177
By witua, 12 years ago, translation, In English

Greetings!

Codeforces Round #177 takes place tomorrow at 19:30 by Moscow. I hope you all will take part and enjoy the problems.

Gerald, as usually, helps in preparings, Delinur translates all the problems for you. Thanks to them.

Good Luck!

Points distribution is standard:

Div1: 500 1000 1500 2000 2500

Div2: 500 1000 1500 2000 2500

Here are today's winners:

Div1:

  1. wjmsbmr

  2. peter50216

  3. rng_58

  4. XilinX

  5. RAD

  6. RomaWhite

  7. eduardische

Div2:

  1. alimiaomiao

  2. yutaka1999

  3. Alex.lap

  4. zlqiszlq

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

Comments Comments (95)
| Write comment?
»
12 years ago, # |
  Vote: I like it +144 Vote: I do not like it

I hope problem statement to be short & easy to understand like your Post :D

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

1- if you want, you can make your announcement shorter by removing unnecessary lines "Greetings!" and "Good Luck!" then your announcement will become only 2 lines long :D

2- you forgot to thank MikeMirzayanov for creating Codeforces system :D

3- sorry, but I really love kidding :)

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

What a short post! Great!!

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

one of the most attractive post i have ever read

short and precise :)

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

finally! i've been waiting for a Codeforces contest for more than a week now!!

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

Who bets that there will be problems with lucky numbers? :))

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

    I bet there will be with permutations

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

hope the problem statements will be more short...

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

Pro tip: you can find out the score distribution when the contest begins by opening any problem and looking at the possible scores table. All 3000 => dynamic, not => standard. Unless for some reason you really need to know the score distribution before the contest.

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

    I really need to know it before the contest. It's a matter of strategy, at least for me.

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

There is a little sadness in the post.

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

Score distribution wont be published ?

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

Although nice problems, I am really unhappy from the contest: 1- Spent 30 minutes misunderstanding B, because of problem writer mixed usage of "can" with "must". 2- Could not submit problem C in last minute of contest because of server errors !!

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

in problem B(div 1) in first testcase why answer is 54? first two elements definitely will be 2,1 and ans=1*3^(5-2)=27

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

    No, elements 1,1 are allowed as well. It's a cycle from 1 to 1 of length 1 (non-zero).

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

      If 1,1 is allowed, whats the meaning of constrain 3? It can be removed then.

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

        Without the 3rd contrain, p_1 = k+1 would be possible (when k < n, of course).

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

      that should've been explained explicitly.

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

        It's clear from the first sample. Had 1,1 not been allowed, the first 2 houses would have to be 2,1 so the answer would be 27 instead of 54.

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

          But 1 to 1 is a cycle of length 1.

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

            Yes, I agree. And that is another reason why there was no need to explain explicitly.

            It's just that common sense differs from graph theory here :D since "walking to the same house you're at" means "not moving at all" IRL.

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

    First elements also can be 1 1

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

    1,1 is a valid configuration :)

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

The website didn't respond in the last moments, I was 2-3 seconds short of hacking someone's solution, if only you people could give some extra time if there is a fault on your behalf, it would be great. Thanks anyway, the contest was very nice.

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

    Was the solution of that person accepted? BTW same happened with me two time before no submission or hacks in last 2-3 minutes

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

      no, it ended up getting TLE which I knew :P

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

Couldnt submit problem E in last 16 secs :(

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

I could not submit problem D in the last minute because of server errors. How unfortunate!

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

    I also couldn't submit D, and now I got accepted T_T

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

    Same with my D. I first submitted a solution considering all possibilities with complexity O(k*k^k). When 2 mins were left, I realised that I could precalculate the values for k and then when I tried to submit in the last seconds, the servers did spoilers for me.

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

      They are talking about div1D not div2D :D

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

What's the solution to div1 C/div2 E?

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

    I coded a bruteforce and observed a possible greedy algorithm, hehe... not without sweating blood, though.

    The first thing to notice is: the answer is always N(N+1) for a permutation of numbers 0..(N-1). Too bad that's not enough to solve the problem :D

    So, try printing all possible permutations with answer N(N+1). Not good... although there is a nice pattern for even N, odd N is a problem.

    If the permutation itself doesn't tell you anything, try something else... like the permutation xor-d with its indices! (I mean i^p[i] instead of just p[i]). Hmm... the lexicographically smallest permutation, xored with indices, gives a non-decreasing sequence of powers of 2 -1.

    So what could be a good approach? Greedy, for example — we go from N-1 to 0, and maintain the largest allowed power of 2, and the numbers already used in the permutation. When trying to find i-th number, try xor-ing i with our largest power of 2 -1 and decreasing the power of 2, until the number which it gives is one that we could put in the permutation.

    Miraculously, this works! :D

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

      Thanks for the reply. Any proof about why the answer is always N*(N+1)?

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

    Everything that I say here is just what I observed during the contest, and I don’t know how to prove it (yet). Also, the pattern that I noted certainly isn’t the only one.

    The maximum beauty is n(n + 1).

    A possible answer for n = 2k - 1 is {n, n - 1, ..., 1, 0}.

    For n ≠ 2k - 1:

    Find maximum r = 2k such that r ≤ n - 1 and construct the sequence v = {r - 1, r - 2, ..., 1, 0, r - 1, r - 2, ...} of length n (there will be only one zero in it).

    For each i from r to n: remember v[0] and put i into v[0]. Write i - r as a sum of powers of two in ascending order. Then each element a of this sum means that you should put the remembered element a elements right behind the last touched element.

    Example for n = 14:

    (initial) 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 
(i = 8)   8 6 5 4 3 2 1 0 7 6 5 4 3 2 1 
(i = 9)   9 8 5 4 3 2 1 0 7 6 5 4 3 2 1 
(i = 10)  10 8 9 4 3 2 1 0 7 6 5 4 3 2 1 
(i = 11)  11 10 9 8 3 2 1 0 7 6 5 4 3 2 1 
(i = 12)  12 10 9 8 11 2 1 0 7 6 5 4 3 2 1 
(i = 13)  13 12 9 8 11 10 1 0 7 6 5 4 3 2 1 
(i = 14)  14 12 13 8 11 10 9 0 7 6 5 4 3 2 1

    Let’s see, for example, how’s transition from i = 13 to i = 14 done: i - r = 6 = 2 + 4, so 0th element is moved 2 positions to the right and 2nd element is moved 4 positions to the right.

    My implementation: 3464172

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

In my opinion, that would be good idea to swap(B div2 , C div2) :)

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

this time I couldn't make any hack. Browser is Google Chrome 23.0.1271.64 Isn't there any other trouble like me?

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

    Any installed plugins/addons? What?

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

      I've installed some general addons(like smooth gestures),and yak_ex's some plugins about codeforces, but I've had no trouble ever.

      Also, now I disabled all plugins,but the problem(the menu showing submitted times and states didn't appear) is not resolved.

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

        Please open the developer tools console (Ctrl+Shift+J) and try to repeat. Any errors?

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

          oh,there's an error -

          "Uncaught Error: QUOTA_EXCEEDED_ERR: DOM Exception 22 "

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

When will the ratings be updated?

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

a participant hacked 10 people in min 5 :O

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

Excellent Problems!

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

This is my first Codeforces Round & I really had fun :)! Thanks for giving us such a good round~(miao~~~)!

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

In Problem C (Div. 1), you didn't write the usual warning about 64-bit numbers ("Please do not use the %lld specificator..."), although the beauty can be larger than 2^31

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

The contest was very good and the problems were excellent and hackable!!! Thanks! :)

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

In solutions for problem D expression (n*(n-1)/2)^2 overflows long long. Technically it is undefined behaviour, but those solutions passed.

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

    I believe that the actual count (which is less than what you specified) could never overflow it. I used unsigned long long just in case though.

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

    This value fits in unsigned long long and technically unsigned long long and long long are not different. Anyway it's like calculating answer modulo 264.

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

      Not always true — while unsigned long long overflow is safe, signed long long overflow leads to undefined behaviour which means that compiler optimizations can use it in weird ways (and they do sometimes, but not in this simple case).

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

        Interesting! I didn't know about this.

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

    Let's estimate the number of paths containing the centroid (precisely, one of the centroids) of the tree (that's the vertex for which the subgraphs after deleting this vertex don't have more than n/2 vertices). Let's mark our centroid by v.

    For each vertex w there are >= n/2 directed paths which start in w and contain v (that's because the size of the subtree containing w is less or equal n/2). It means that there are >= n*n/2 = (n^2)/2 directed paths containing the centroid, which gives us >= (n^2)/4 undirected paths, so >= n^2(n^2-1)/16 pairs of these paths.

    You have to subtract this number from your expression. It means that the result does not exceed

    R <= [n*(n-1)/2]^2 — n^2(n^2-1)/16 <= n^2(n^2-1)/4 — n^2(n^2-1)/16 = 3n^2(n^2-1)/16 < 2^63 for n<=80000.

    It means the results fit in signed long long and these solutions must have passed :/

    Edit: However, it would be funny if the behaviour of handling signed overflows was undefined ;)

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

Look at this : 3462424 (IN contest submission) and 3464490

just change from i++ to ++i and reduce clause while(remA.size()) to while(remA.size()|remB.size())

TLE -> Accept T___T

Moreover, I Accept at 2000 ms :)

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

"GNU C++ vs MS C++", bullshit and old ambiguity! 3464322 3464569

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

    That is very confusing!

    there are some codes TLE with MS C++ and AC with GNU++. however, there are also some codes TLE with GNU c++ and AC with MS C++ .

    so it's not easy to tell which compiler is better

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

Great contest, great problems! Here's a discussion of the math in (B): http://www.codeforces.ru/blog/entry/7225

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

faster rating update.... :)

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

Great contest

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

In my view, prob C of div.2 was very tricky because it had many corner cases and this might be the reason why it yielded the maximum number of hacks.. But I escaped lucky and got +120 rating points..

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

    I'am sorry to make mistake on this when I summited it at 7 minute.But I soon found that lots of people got hackings.So I realized it and put it right within 2 minutes,luckily.

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

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

    This rating is quite difficult to keep.

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

A nice way to get updated for all contests https://www.hackerrank.com/calendar

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

HI

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

Fun fact: Answer to B is always k^{k-1} * (n-k)^{n-k}. Why k^{k-1}? Let's ignore edge outgoing from 1. Graph on vertices 1, ..., k has to be any spanning tree of K_n, with root at 1. Number of such trees is k^{k-2} — it is known beatiful Cayley's theorem. Now we can fix any edge outgoing from vertex 1 and we get k^{k-1} good graphs. So bad that I didn't notice this during the contest, even though I thought about Cayley's theorem (and also I have read k<=max(8, n) (which is not of much sense) instead of k<=min(8, n) -_-...).

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

How to solve problem B of div2?

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

    (The matrix-like scheme is irrelevant; Consider we have N=n*m numbers in a array v[0..N-1] as input).

    First of all, please notice that when you add or subtract the value d from a value v[i], its remainder by d is not changed (i.e., (v[i] +/- d) mod d = v[i] mod d ).

    Since you can't change the value of (v[i] mod d) by applying any number of moves to v[i], there is a solution if and only if the value of (v[i] mod d) is the same for all i.

    So, if there isn't a solution, print "-1". Otherwise, the problem is kinda classical: you'll change all the elements to the median of the values given in the input. So, sort v and sum |v[i]-v[N/2]|/d for all i.

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

I love this contest!

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

Regarding Problem B of Division 2, it was surprising to see that even the brute force solutions passed system tests. The brute force approach would involve trying every number from 1 to 10^4 as the final value of each element of the matrix, finding the required number of moves for each of them, and then choosing the minimum out of them.

As per the constraints, this approach has O(10000*100*100) = O(10^8) operations in the worst case, which, in my opinion, should have exceeded the time limit. After couple of wasted hacking attempts and the system testing, it appears that this isn't the case.

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

In problem B (Div 1) in the first statement: When the penguin starts walking from any house indexed from 1 to k, inclusive, he can walk to house number 1. Does he can walk to house number 1 mean he must get back to the house number 1? Edit: Sorry for my mistake.

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

    It actually means that if he starts from any house numbered 1 to k, inclusive, then there will be a path from the house he started to house number 1. He must not get back to the house he started walking from but there must be a path from any house with index 1 to k to house 1.

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

    No , it only means he can reach house number 1.

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

    I still don't get it. What does "Can" mean here? There must be a path from every house between 1 and k inclusive to the first house? Or there "can" be such a path?

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

      It means that there must be a path. I understood it wrongly too.

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

Can someone explain the E of div 1? thx

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

Can someone explain solution of Problem E.div2 PLS?

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

    for each array index such i you should calculate the number a that a + i = ( 2 ^ k )-1 and this number hasn't been used yet in the permutation C++ code:3461375 There is a simple way for the implementation, calculate powers of 2 and check it for the array index elements, from n to 0

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

Editorial please..................

→ Reply