witua's blog

By witua, 7 years ago, translation, ,

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:

• +351

 » 7 years ago, # |   +144 I hope problem statement to be short & easy to understand like your Post :D
•  » » 7 years ago, # ^ |   +6 like last contest :D
•  » » 7 years ago, # ^ |   0 AND were made hacking easy
•  » » » 7 years ago, # ^ |   -11 are you hacked?
•  » » » » 7 years ago, # ^ |   0 No :D because submited questions are hacking in two or three minute
•  » » » » » 7 years ago, # ^ |   -15 you're talking so much bit***..
 » 7 years ago, # | ← Rev. 3 →   +83 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 :D2- you forgot to thank MikeMirzayanov for creating Codeforces system :D3- sorry, but I really love kidding :)
•  » » 7 years ago, # ^ |   +9 4 . score distribution .
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +3 5 . Congratulations to the winners
•  » » » » 7 years ago, # ^ |   -13 are you loser
 » 7 years ago, # |   +8 What a short post! Great!!
 » 7 years ago, # |   +11 one of the most attractive post i have ever readshort and precise :)
 » 7 years ago, # |   +6 finally! i've been waiting for a Codeforces contest for more than a week now!!
•  » » 7 years ago, # ^ |   +2 yeah.. me 2:)
 » 7 years ago, # |   +10 Who bets that there will be problems with lucky numbers? :))
•  » » 7 years ago, # ^ |   +1 I bet there will be with permutations
•  » » » 7 years ago, # ^ |   0 I bet there will be Little Elephant
 » 7 years ago, # |   -6 hope the problem statements will be more short...
•  » » 7 years ago, # ^ |   +51 So short, like yesterday? :)
 » 7 years ago, # | ← Rev. 2 →   +45 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.
•  » » 7 years ago, # ^ |   -11 I really need to know it before the contest. It's a matter of strategy, at least for me.
 » 7 years ago, # |   +8 There is a little sadness in the post.
 » 7 years ago, # |   -13 Score distribution wont be published ?
•  » » 7 years ago, # ^ |   0 It's published)
 » 7 years ago, # |   +25 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 !!
•  » » 7 years ago, # ^ |   +23 :( submitted and got AC http://codeforces.com/contest/288/submission/3464296
 » 7 years ago, # |   +7 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
•  » » 7 years ago, # ^ |   +9 No, elements 1,1 are allowed as well. It's a cycle from 1 to 1 of length 1 (non-zero).
•  » » » 7 years ago, # ^ |   +4 If 1,1 is allowed, whats the meaning of constrain 3? It can be removed then.
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +7 Without the 3rd contrain, p_1 = k+1 would be possible (when k < n, of course).
•  » » » 7 years ago, # ^ |   +16 that should've been explained explicitly.
•  » » » » 7 years ago, # ^ |   0 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.
•  » » » » » 7 years ago, # ^ |   0 But 1 to 1 is a cycle of length 1.
•  » » » » » » 7 years ago, # ^ |   +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.
•  » » 7 years ago, # ^ |   +3 First elements also can be 1 1
•  » » 7 years ago, # ^ |   +3 1,1 is a valid configuration :)
 » 7 years ago, # |   +17 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.
•  » » 7 years ago, # ^ |   +1 Was the solution of that person accepted? BTW same happened with me two time before no submission or hacks in last 2-3 minutes
•  » » » 7 years ago, # ^ |   0 no, it ended up getting TLE which I knew :P
 » 7 years ago, # | ← Rev. 3 →   +8 Couldnt submit problem E in last 16 secs :(
•  » » 7 years ago, # ^ | ← Rev. 4 →   0 sorry, deleted.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +1 couldnt submit the problem in last minutes due to server issues. please look into this .
 » 7 years ago, # |   +17 I could not submit problem D in the last minute because of server errors. How unfortunate!
•  » » 7 years ago, # ^ |   +27 I also couldn't submit D, and now I got accepted T_T
•  » » 7 years ago, # ^ |   0 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.
•  » » » 7 years ago, # ^ |   0 They are talking about div1D not div2D :D
 » 7 years ago, # |   +5 What's the solution to div1 C/div2 E?
•  » » 7 years ago, # ^ |   +5 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 :DSo, 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
•  » » » 7 years ago, # ^ |   0 Thanks for the reply. Any proof about why the answer is always N*(N+1)?
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 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
 » 7 years ago, # | ← Rev. 2 →   +8 In my opinion, that would be good idea to swap(B div2 , C div2) :)
 » 7 years ago, # |   +14 this time I couldn't make any hack. Browser is Google Chrome 23.0.1271.64 Isn't there any other trouble like me?
•  » » 7 years ago, # ^ |   +7 Any installed plugins/addons? What?
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 May be the reason I couldn't is ABP(Ad Block Plus). Can it be ?
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +13 Please open the developer tools console (Ctrl+Shift+J) and try to repeat. Any errors?
•  » » » » » 7 years ago, # ^ |   +5 oh,there's an error -"Uncaught Error: QUOTA_EXCEEDED_ERR: DOM Exception 22 "
•  » » 7 years ago, # ^ |   0 Chrome 26.0.1410.43 — all works perfectly.
 » 7 years ago, # |   -11 When will the ratings be updated?
 » 7 years ago, # |   +1 a participant hacked 10 people in min 5 :O
 » 7 years ago, # |   +15 Excellent Problems!
 » 7 years ago, # |   +16 This is my first Codeforces Round & I really had fun :)! Thanks for giving us such a good round~(miao~~~)!
 » 7 years ago, # |   +5 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
 » 7 years ago, # |   +9 The contest was very good and the problems were excellent and hackable!!! Thanks! :)
 » 7 years ago, # |   +24 In solutions for problem D expression (n*(n-1)/2)^2 overflows long long. Technically it is undefined behaviour, but those solutions passed.
•  » » 7 years ago, # ^ |   +5 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.
•  » » 7 years ago, # ^ |   +3 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.
•  » » » 7 years ago, # ^ |   +16 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).
•  » » » » 7 years ago, # ^ |   +6 Interesting! I didn't know about this.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +13 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 exceedR <= [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 ;)
 » 7 years ago, # | ← Rev. 2 →   -17 Look at this : 3462424 (IN contest submission) and 3464490just change from i++ to ++i and reduce clause while(remA.size()) to while(remA.size()|remB.size())TLE -> Accept T___TMoreover, I Accept at 2000 ms :)
•  » » 7 years ago, # ^ |   0 So, I know this and can explain, but on PHP.
 » 7 years ago, # |   +7 "GNU C++ vs MS C++", bullshit and old ambiguity! 3464322 3464569
•  » » 7 years ago, # ^ |   +1 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
 » 7 years ago, # |   +11 Great contest, great problems! Here's a discussion of the math in (B): http://www.codeforces.ru/blog/entry/7225
 » 7 years ago, # |   +3 faster rating update.... :)
 » 7 years ago, # |   +12 Great contest
•  » » 7 years ago, # ^ |   +1 I think so.
•  » » 7 years ago, # ^ |   -32 do you think so? this is bullshit
•  » » 7 years ago, # ^ |   0 I THINK SO
 » 7 years ago, # | ← Rev. 2 →   +10 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..
•  » » 7 years ago, # ^ |   +11 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.
 » 7 years ago, # |   +40
•  » » 7 years ago, # ^ |   +116 This rating is quite difficult to keep.
 » 7 years ago, # |   0 A nice way to get updated for all contests https://www.hackerrank.com/calendar
•  » » 7 years ago, # ^ |   +3 this is great contest
»
7 years ago, # |
-15

HI

 » 7 years ago, # |   +14 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) -_-...).
•  » » 7 years ago, # ^ |   +1 Excellent explanation. Here is a link to wiki for those who interested: http://en.wikipedia.org/wiki/Cayley%27s_formulaAnd (n-k)^{n-k} for remaining houses is because its irrelevant what kind of mapping do you choose as long as it is surjective.
 » 7 years ago, # |   0 How to solve problem B of div2?
•  » » 7 years ago, # ^ |   +4 (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.
 » 7 years ago, # |   -8 I love this contest!
 » 7 years ago, # |   +6 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.
•  » » 7 years ago, # ^ |   0 because of this false thinking I didn't even tried to code the naive approach so ...
 » 7 years ago, # | ← Rev. 2 →   +1 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.
•  » » 7 years ago, # ^ |   0 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.
•  » » 7 years ago, # ^ |   0 No , it only means he can reach house number 1.
•  » » 7 years ago, # ^ |   0 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?
•  » » » 7 years ago, # ^ |   +1 It means that there must be a path. I understood it wrongly too.
 » 7 years ago, # |   +5 Can someone explain the E of div 1? thx
 » 7 years ago, # |   0 Can someone explain solution of Problem E.div2 PLS?
•  » » 7 years ago, # ^ |   +8 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
 » 7 years ago, # |   +35 Editorial please..................