### KhaustovPavel's blog

By KhaustovPavel, 6 years ago, translation, ,

Hi, everyone!

Regular Codeforces round #242 for participants from the second division will take place on 25 April, 11:00 MSK. Participants from the first division are able to participate out of the competition.

The contest is prepared by programmers from Tomsk Polytechnic University: Pavel Khaustov (KhaustovPavel), Olesya Golub (Taube), Nickolay Kuzivanov (bnick), Dmitry Savvinov (dsavvinov), Alexey Vetrov (noxwell).

Special thanks to Vladimir Chalyshev (cmd) and Alexey Dergunov (dalex) for their impact.

Also, thanks to Codeforces team and, especially, to Gerald Agapov (Gerald) and Maria Belova (Delinur).

Points distribution: 500-1000-1500-2500-3000

Good luck!

• +109

 » 6 years ago, # |   0 Why are there so many contests at 3 AM US time. :(
•  » » 6 years ago, # ^ |   0 In china,we usually play it at 23:00!Sometime,we can't help falling asleep at that time.
 » 6 years ago, # | ← Rev. 3 →   +3 I think most of the contestants aren't comfortable with the time of the contest start , it's been like this with coder-strike tooPlease reconsider this in the next contests .And many thanks to the authors
•  » » 6 years ago, # ^ |   +37 I am sorry to hear that you feel uncomfortable with the time.However, I like the time very much :) It is 15:00 in Hong Kong (UTC+8), but I will be at school as it is Friday... The usual time of contest will be at 23:00 in Hong Kong and I can't help falling asleep at that time.I hope that the time could be modified so as to cater most people's need.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 I'm glad to hear that =) , I hope so too
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Same in Taiwan (UTC+8)!
•  » » » 6 years ago, # ^ |   0 I can't agree more. The same in BeiJing.
•  » » » » 6 years ago, # ^ |   0 The same in Chengdu！
•  » » » 6 years ago, # ^ |   0 Same in Vietnam :) (UTC+7)
•  » » » 6 years ago, # ^ |   0 Same in Beijing.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 In Romania the contest starts at 10AM, but I have school then. Hope that the old hour(6PM in Romania) will be used more in the future :D
 » 6 years ago, # |   -11 Div1 users won't be rated? Only div2 users will be rated with a separated ranking?
•  » » 6 years ago, # ^ |   +3 as usual, div1 wont be rated
 » 6 years ago, # |   +6 Am I the only guy who read KhaustovPavel as Khaustov Patel? :PPS: Khaustov Patel is a typical Indian name.
•  » » 6 years ago, # ^ |   +21 yes.
•  » » 6 years ago, # ^ |   +3 Patel is common Indian name and not Khaustov. https://www.google.com/search?q=Khaustov+PatelAnd his name does not contain Patel! I don't see many people making this mistake :)
 » 6 years ago, # | ← Rev. 3 →   +2 This time is ok, if it's not friday. Friday is Jummah day(a special day for the muslims). And in Bangladesh, the time when contest will be started, is the jumma time. :( So going to miss this contest... :'( *** If anyone wants to know about Jummah, can check it here
 » 6 years ago, # |   0 lot of competitions lately have been at 1 am here which has been uncomfortable. Can anything be done with the time to make it work for most of contestants
 » 6 years ago, # | ← Rev. 3 →   +27 I'm sorry to to hear that many people feel uncomfortable with the time.However, it's obvious that the time can't make all contestants happy and some people participate the contest at midnight.The usual time will be at 23:30 in Beijing.When the contest ends,it will be at 1:30am.And I think it's more uncomfortable for Japanese and other east Asian countries' contestants. But there are still many east Asian countries' contestants to participate the contest. I think the reason is that we love coding and enjoy the contests. But I have to say the usual time of the contest is better for most contestants. Hope we can understand author and understand each other.
 » 6 years ago, # | ← Rev. 2 →   +14 I am happy with this time. It will be 3 AM EST here in FL, US but it is a good time to write code relaxed, lol. The usual time is complicated (11:30 AM EST) for me because either I am working and I can't focus very well or I am at home where my daughter doesn't stop playing with me while I am solving the problems. As always, enjoy the contest, GL & HF!!!
•  » » 6 years ago, # ^ | ← Rev. 2 →   +20 Same point of view here. I prefer midnight contests to daytime contests, too. Fortunately, regular Codeforces time favors me well (11.30pm). Typical coders don't go to bed early, right? :P
•  » » » 6 years ago, # ^ |   +6 Yes. At the end, coders don't go to sleep early. I would like to participate in more contests after midnight.
 » 6 years ago, # |   +5 I prefer 3 AM to 11:30 AM because I'm more likely to be awake at the former time ;)
 » 6 years ago, # |   +8 Our mid-term exam is about to finish today morning, so just be able to take part in... Sorry to hear that it' s an uncomfortable time for others. (Start at China Standard Time 15:00)
 » 6 years ago, # |   +11 Unfortunately cannot participate in the contest cause its jummah time .
 » 6 years ago, # |   +1 30 mins to start the contest .... It will be a good contest as always . wish you luck all :)
 » 6 years ago, # |   0 How did you solve Div 2 C?
•  » » 6 years ago, # ^ |   0 I received time limit on pretest 12.
•  » » » 6 years ago, # ^ |   0 What did you try? Bruteforce will fail obviously.
•  » » 6 years ago, # ^ |   +3 q[i]=p[i]^(i%1)^(i%2)^...^(i%n) Q = q[1]^q[2]^...^q[n] = (p[1]^...^p[n]) ^ (^ for i=1..n for k=1..n (i%k)) = (p[1]^...^p[n]) ^ (^ for k=1..n for i=1..n (i%k)). Let P=p[1]^...^p[n]. So, Q = P ^ (^ for k=1..n for i=1..n (i%k)). Now we have to calculate these xors for all k: (^ for i=1..n (i%k)). ^ for i=1..n (i%k) = 0^1^2^...^(k-1) ^ 0^1^2^...^(k-1) ^ ... ^ 0^1^2^...^(k-1) [(n/k) times] ^ 0^1^2...^(n%k) = ((n/k)%2)*(0^1^2^...^(k-1)) ^ (0^1^2...^(n%k)). We can pre-calculate all xor sums like (0^1^2^...^(k-1)). The rest is obvious.
•  » » » 6 years ago, # ^ |   +31 Also there is a formula for prefix xors 0 ^ 1 ^ .... ^ k: int xorUpToK(int k) { switch (k % 4) { case 0: return k; case 1: return 1; case 2: return k + 1; case 3: return 0; } } 
•  » » » » 6 years ago, # ^ |   0 can you explain this formula?
•  » » » » » 6 years ago, # ^ |   +1 This is a nice formula for long values of k . To prove it you takeF(3) = 0 ^ 1 ^ 2 ^ 3 = 0because in binary 0000 ^ 0001 ^ 0010 ^ 0011 = 0000and operating BIT for BITF( 7 ) = F( 3 ) ^ 0100 ^ 0101 ^0110 ^ 0111 = 0000F( 7 ) = F( 3 ) ^ (01)00 ^ (01)01 ^(01)10 ^ (01)11 = 0000We can note that () repeats four times , and four is even then (x)^(x)^(x)^(x) = 0 is ever zeroBut in this problem is not necesarry because we can precalculate al values <= 10^6A problem that you really need this formula.Link to problemPSDATA: you need know nim numbers before solve Industrial Nim.
•  » » » » » » 6 years ago, # ^ |   0 Awesome, thanks! I know this problem just needed a simple precomputation, but it's still nice to understand this formula.
•  » » » » » 6 years ago, # ^ |   +1 I think that most coders have checked this postBut without this, you can also do a precomputation :D
•  » » » 6 years ago, # ^ |   0 could you please format your comment to make it more readable. thanks!
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   0 This is related to problem C of div.2 #242Here is the formatted explanation of Totktonada approach..I checked solution codes of many people but everywhere they were using two things as n/i and n%i and I kept asking why are they using these.. Then I read many explanations for the approach, some helping people wrote long explanations but what helped me really understand is Totktonada's comment below is the same comment made clear and easy to read q[i]=p[i]^(i%1)^(i%2)^...^(i%n) Q = q[1]^q[2]^...^q[n] = (p[1]^...^p[n]) ^ (^ for i=1..n for k=1..n (i%k))= (p[1]^...^p[n]) ^ (^ for k=1..n for i=1..n (i%k)). Let P=p[1]^...^p[n]. So, Q = P ^ (^ for k=1..n for i=1..n (i%k)). Now we have to calculate these xorsfor all k: (^ for i=1..n (i%k)). ^ for i=1..n (i%k) = 0^1^2^...^(k-1) ^ 0^1^2^...^(k-1) ^ ... ^ 0^1^2^...^(k-1) [(n/k) times] ^ 0^1^2...^(n%k) = ((n/k)%2)*(0^1^2^...^(k-1)) ^ (0^1^2...^(n%k)). We can pre-calculate all xor sums like (0^1^2^...^(k-1)).using a precalculated array X[1..n] with X[i] as 1^2^..^ifor( int i = 1 ; i <= N ; ++i ) F[ i ] = F[ i-1 ] ^ i; The rest is obviousApart from above explanation you must also read comment1 by Boxer and comment2 by dalex
•  » » 6 years ago, # ^ |   0 We know that xor is asociative then we can reagrup de expression as p1 xor p2 .... xor p3 * E where E is a new expression and again reagruping :E = (1 mod 1 xor 2 mod2 ... n mod1 ) xor (1 mod 2 xor 2 mod 2 ... n mod2 ) ....Then we can get F = 1 mod i xor 2 mod i xor .... n mod i efficiently
•  » » » 6 years ago, # ^ |   0 Exactly, but what after that? I understood that part, but I could not form a relation afterwards.
•  » » » » 6 years ago, # ^ |   +11 We can getF = 1 mod i xor 2 mod i xor .... n mod i if we take every package of size i then we have F = [ 1 mod i xor 2 mod i xor .... i mod i ]xor [ (i + 1) mod i xor (i+2) mod i .. (2*i) mod i ] ...thenF = [ 1 mod i xor 2 mod i xor .... i mod i ] xor [ 1 mod i xor 2 mod i xor .... i mod i ]......Finally [ ] repeats q = n/i and if q is even there [ ] = 0 else [] = [ 1 mod i xor 2 mod i xor .... i mod i ] and we can consider r = n%i too.for solve G = [ 1 mod i xor 2 mod i xor .... i mod i ] we can see that is equal toG = [ 1 xor 2 xor .... i ]And everthing depends only of G we can precalcalculate with a array.My SolutionSorry for my bad english.
•  » » 6 years ago, # ^ | ← Rev. 3 →   +4 I have formed an matrix on a paper of n x n rows represent n and cols mod i - 0 1 1 1 1 ... 1 - 0 0 2 2 2 ... 2 - 0 1 0 3 3 ... 3 - 0 0 1 0 4 ... 4 as you can see, every column is a cycle of length i, and you can cancel (n/i)/2 cycles, because x ^ x = 0, obviously you will not always have cycles that pairs, so you need the xor of the parts that can't be paired, lets call it rest[i] finally with a for i do ans ^= p[i] ^ rest[i]my submission 6467752
 » 6 years ago, # |   -12 A contest with no successful hacking attempt!
•  » » 6 years ago, # ^ |   0 may be there was hack in E. :p
•  » » 6 years ago, # ^ |   +4
 » 6 years ago, # |   +3 Am I the only person who are confused with problem E's sample case?
 » 6 years ago, # |   0 Can anyone tell me why my solution gave WA ? I did precomputation of XORs and my complexity is also good. 6468572
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 can you at least explain a bit your idea? and ull was not necessary
•  » » 6 years ago, # ^ |   0 You had the right idea of precalculating xors, but what you're doing on each iteration is not right. Try this simple test: 4 0 0 0 0 The answer should be 2.
•  » » » 6 years ago, # ^ |   0 Yeah . Silly mistake on my part , I took mod as simply the difference and it failed on indices like 4%2 and 4%4. .
 » 6 years ago, # |   +3 what was the idea of D?
•  » » 6 years ago, # ^ |   +6 Bruteforce and TernarySearch , my friend.
•  » » » 6 years ago, # ^ |   +3 Integer ternary search OoYou crazy person...P.S. I thought, we can't avoid using set in this problem. Such a surprise.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +3 Actually the solution passes in time! >.>
•  » » » 6 years ago, # ^ |   +9 This solution is wrong. Ternary search doesn't work here.
•  » » » » 6 years ago, # ^ |   +3 6469423Well, but his solution is AC.
•  » » » » » 6 years ago, # ^ |   0 And how do you think what does it mean? :)
•  » » » » » » 6 years ago, # ^ |   -6 Weak tests, round should be unrated :Ъ
•  » » » » » » » 6 years ago, # ^ |   0 Not really, I believe his solution is correct.His ternary search function is a function of the absolute difference between both times, which is clearly a bitonic function in this problem.
•  » » » » 6 years ago, # ^ |   0 Hey man i think that you are wrong , Ternary search works because my function f is crecient then g = abs( f — t ) is like a parabola then i need to calculate the minimum.
•  » » » » » 6 years ago, # ^ |   +9 You fix left, right and top borders of the track and then find the bottom border by binary search. Let's see what bottom borders we can create.What happens if all odd rows are decreasing (a[i][j] > a[i][j+1]) and all even rows are increasing (a[i][j] < a[i][j+1])?If we consider the times needed to go through the parts of track built at these rows, they will be like {d*tUp, d*tDown, d*tUp, d*tDown, ...} where d is the width of the track and tUp and tDown are numbers from the input. It's not a crescent sequence, is it? Of course we also have increasing left and right parts, but they cannot affect so much as the bottom part affects the function (e.g. if the width is very large).
•  » » » » » » 6 years ago, # ^ |   0 Oh nice counterExample , maybe in random cases my solution works well:)
•  » » » » » » 6 years ago, # ^ |   +1 I thought this during the contest, so I went for the O(N^4) solution :(Still, in the editorial (http://codeforces.com/blog/entry/11944) the author says his solution is O(N^3 * logN).As far as I've seen, people have used n-ary search to do this, but there are a lot of cases where that would fail, cause you can't guarantee that it's increasing or decreasing at any point.Take dalex' example with odd decreasing/even increasing rows, you can actually have any random configuration of rows that are all increasing or decreasing and this would make any n-ary search solution fail, as far as I can understand.So, any ideas of how to achieve the O(N^3 * log N) solution with any other method? (Or is there something that I'm missing and a n-ary search actually works?)
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 champero detected !! :P, Nice problem.
 » 6 years ago, # |   +3 Any editorial?
•  » » 6 years ago, # ^ |   +3 here it is.
 » 6 years ago, # |   0 Could anyone help figure out what the wrong is in my two solution of Problem C? 6466959 and 6468449
 » 6 years ago, # |   0 In Problem C, upper limit of 'p' was 2 x 10**9. However, solutions that took 'p' as int passed.
•  » » 6 years ago, # ^ |   +1 the upper limit of int is 2147483647, which is more than 2e9. so ofcourse it will pass!
 » 6 years ago, # |   +4 I am wondering if this algorithm is correct or not. http://codeforces.com/contest/424/submission/6470517 He enums all the point on the top-left , and use trinary-search twice to find the point on the bottom-right. In my view , this solution is incorrect. Just can not find a data challenge this code ? Thanks
 » 6 years ago, # |   0 Could anyone share your idea of problem D? I was confused with the problem for more than one hour, sticking to the O(n^4) algorithm and cannot find a way to optimize it....
 » 6 years ago, # |   +3 Hello.Can anyone tell me why submission 6465131 gets Compilation Error on Codeforces, as it compiled perfectly on my local machine ( Linux GCC 4.8.2, though I doubt there are any great differences between this and 4.7) ? Link: http://codeforces.com/contest/424/submission/6465131Thanks.
•  » » 6 years ago, # ^ |   +11 Compiler thinks that distance is STL function to count distance between two iterators, but not yours. You haven't Compilation Error on your local machine because your local machine uses C++11 mode. If you want to use C++11 on Codeforces, you should choose "GNU C++0x 4" as language.
•  » » » 6 years ago, # ^ |   +3 Ok, thanks for your help.
 » 6 years ago, # |   0 why is 3 1 4 6 not a solution to sample of D?
•  » » 6 years ago, # ^ |   0 Read the statement carefully. The side of rectangle must be at least 3.
 » 6 years ago, # |   0 Problem D was very misleading... During the contest, some people got Accepted with a O(n^4) algorithm, while most people thought that the required complexity was O(n^3) :P