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!

Why are there so many contests at 3 AM US time. :(

In china,we usually play it at 23:00!Sometime,we can't help falling asleep at that time.

I think most of the contestants aren't comfortable with the time of the contest start , it's been like this with coder-strike too

Please reconsider this in the next contests .

And many thanks to the authors

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.

I'm glad to hear that =) , I hope so too

Same in Taiwan (UTC+8)!

I can't agree more. The same in BeiJing.

The same in Chengdu！

Same in Vietnam :) (UTC+7)

Same in Beijing.

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

Div1 users won't be rated? Only div2 users will be rated with a separated ranking?

as usual, div1 wont be rated

Am I the only guy who read KhaustovPavel as Khaustov Patel? :P

PS: Khaustov Patel is a typical Indian name.

yes.

Patel is common Indian name and not Khaustov. https://www.google.com/search?q=Khaustov+Patel

And his name does not contain Patel! I don't see many people making this mistake :)

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

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

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.

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

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

Yes. At the end, coders don't go to sleep early. I would like to participate in more contests after midnight.

I prefer 3 AM to 11:30 AM because I'm more likely to be awake at the former time ;)

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)

Unfortunately cannot participate in the contest cause its jummah time .

30 mins to start the contest .... It will be a good contest as always . wish you luck all :)

How did you solve Div 2 C?

I received time limit on pretest 12.

What did you try? Bruteforce will fail obviously.

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.

Also there is a formula for prefix xors

`0 ^ 1 ^ .... ^ k`

:can you explain this formula?

This is a nice formula for long values of k . To prove it you take

F(3) = 0 ^ 1 ^ 2 ^ 3 = 0

because in binary

0000 ^ 0001 ^ 0010 ^ 0011 = 0000

and operating BIT for BIT

F( 7 ) = F( 3 ) ^ 0100 ^ 0101 ^0110 ^ 0111 = 0000

F( 7 ) = F( 3 ) ^ (01)00 ^ (01)01 ^(01)10 ^ (01)11 = 0000

We can note that () repeats four times , and four is even then (x)^(x)^(x)^(x) = 0 is ever zero

But in this problem is not necesarry because we can precalculate al values <= 10^6

A problem that you really need this formula.

Link to problem

PSDATA: you need know nim numbers before solve Industrial Nim.

Awesome, thanks! I know this problem just needed a simple precomputation, but it's still nice to understand this formula.

I think that most coders have checked this post

But without this, you can also do a precomputation :D

could you please format your comment to make it more readable. thanks!

This is related to problem C of div.2 #242

Here 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 readq[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)).

using a precalculated array X[1..n] with X[i] as 1^2^..^i

for( int i = 1 ; i <= N ; ++i ) F[ i ] = F[ i-1 ] ^ i; The rest is obvious

Apart from above explanation you must also read comment1 by Boxer and comment2 by dalex

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

Exactly, but what after that? I understood that part, but I could not form a relation afterwards.

We can get

F = 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 ] ...

then

F = [ 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 to

G = [ 1 xor 2 xor .... i ]

And everthing depends only of G we can precalcalculate with a array.

My Solution

Sorry for my bad english.

I have formed an matrix on a paper of n x n rows represent n and cols mod i

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

A contest with no successful hacking attempt!

may be there was hack in E. :p

http://codeforces.ru/contest/424/submission/6467778

Am I the only person who are confused with problem E's sample case?

Can anyone tell me why my solution gave WA ? I did precomputation of XORs and my complexity is also good. 6468572

can you at least explain a bit your idea? and ull was not necessary

You had the right idea of precalculating xors, but what you're doing on each iteration is not right. Try this simple test:

The answer should be 2.

Yeah . Silly mistake on my part , I took mod as simply the difference and it failed on indices like 4%2 and 4%4. .

what was the idea of D?

Bruteforce and TernarySearch , my friend.

Integer ternary search Oo

You crazy person...

P.S. I thought, we can't avoid using

`set`

in this problem. Such a surprise.Actually the solution passes in time! >.>

6467987 6468437 6468850 6467987

This solution is wrong. Ternary search doesn't work here.

6469423

Well, but his solution is AC.

And how do you think what does it mean? :)

Weak tests, round should be unrated :Ъ

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.

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.

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).Oh nice counterExample , maybe in random cases my solution works well:)

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

champero detected !! :P, Nice problem.

Any editorial?

here it is.

Could anyone help figure out what the wrong is in my two solution of Problem C? 6466959 and 6468449

In Problem C, upper limit of 'p' was 2 x 10**9. However, solutions that took 'p' as int passed.

the upper limit of

`int`

is`2147483647`

, which is more than`2e9`

. so ofcourse it will pass!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

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

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/6465131

Thanks.

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.Ok, thanks for your help.

why is

`3 1 4 6`

not a solution to sample of D?Read the statement carefully. The side of rectangle must be at least 3.

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