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:

Div2:

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

like last contest :D

AND were made hacking easy

are you hacked?

No :D because submited questions are hacking in two or three minute

you're talking so much bit***..

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

4 . score distribution .

5 . Congratulations to the winners

are you loser

What a short post! Great!!

one of the most attractive post i have ever read

short and precise :)

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

yeah.. me 2:)

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

I bet there will be with permutations

I bet there will be Little Elephant

hope the problem statements will be more short...

So short, like yesterday? :)

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.

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

There is a little sadness in the post.

Score distribution wont be published ?

It's published)

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

:( submitted and got AC http://codeforces.com/contest/288/submission/3464296

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

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

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

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

that should've been explained explicitly.

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.

But 1 to 1 is a cycle of length 1.

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.

First elements also can be

`1 1`

1,1 is a valid configuration :)

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.

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

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

Couldnt submit problem E in last 16 secs :(

sorry, deleted.

couldnt submit the problem in last minutes due to server issues. please look into this .

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

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

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.

They are talking about div1D not div2D :D

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

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

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

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= 2^{k}- 1 is {n,n- 1, ..., 1, 0}.For

n≠ 2^{k}- 1:Find maximum

r= 2^{k}such thatr≤n- 1 and construct the sequencev= {r- 1,r- 2, ..., 1, 0,r- 1,r- 2, ...} of lengthn(there will be only one zero in it).For each

ifromrton: rememberv[0] and putiintov[0]. Writei-ras a sum of powers of two in ascending order. Then each elementaof this sum means that you should put the remembered elementaelements right behind the last touched element.Example for

n= 14:Let’s see, for example, how’s transition from

i= 13 toi= 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

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

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

Any installed plugins/addons? What?

May be the reason I couldn't is ABP(Ad Block Plus). Can it be ?

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.

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

oh,there's an error -

"Uncaught Error: QUOTA_EXCEEDED_ERR: DOM Exception 22 "

Chrome 26.0.1410.43 — all works perfectly.

When will the ratings be updated?

a participant hacked 10 people in min 5 :O

Excellent Problems!

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

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

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

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

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.

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 2

^{64}.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).

Interesting! I didn't know about this.

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

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

So, I know this and can explain, but on PHP.

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

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

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

faster rating update.... :)

Great contest

I think so.

do you think so? this is bullshit

I THINK SO

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

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.

This rating is quite difficult to keep.

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

this is great contest

## HI

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

Excellent explanation. Here is a link to wiki for those who interested: http://en.wikipedia.org/wiki/Cayley%27s_formula

And (n-k)^{n-k} for remaining houses is because its irrelevant what kind of mapping do you choose as long as it is surjective.

How to solve problem B of div2?

(The matrix-like scheme is irrelevant; Consider we have

N=n*mnumbers in a array v[0..N-1] as input).First of all, please notice that when you add or subtract the value

dfrom a valuev[i], its remainder bydis 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 tov[i], there is a solution if and only if the value of(v[i] mod d)is the same for alli.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

vand sum|v[i]-v[N/2]|/dfor alli.I love this contest!

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.

because of this false thinking I didn't even tried to code the naive approach so ...

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

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

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?

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

Can someone explain the E of div 1? thx

Can someone explain solution of Problem E.div2 PLS?

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 0Editorial please..................