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
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
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
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://mirror.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 = 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:
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
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?
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 "
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 264.
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 :)
"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.
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*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.
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.
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.
Doeshe 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 numbera
thata + 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..................