Codeforces Round #242 (Div. 2)

11 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;
	}
}

→ Reply

caioaao

11 years ago, # ^ |

can you explain this formula?

→ Reply

11 years ago, # ^ |

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.

→ Reply

caioaao

11 years ago, # ^ |

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

→ Reply

pachon

11 years ago, # ^ |

I think that most coders have checked this post

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

→ Reply

DieAnderen

11 years ago, # ^ |

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

→ Reply

11 years ago, # ^ |

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

→ Reply

xennygrimmato

11 years ago, # ^ |

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

→ Reply

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

11 years ago, # ^ |

+11

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.

→ Reply

pachon

11 years ago, # ^ |

← Rev. 3 →

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

→ Reply

Kianoosh

11 years ago, # |

-12

A contest with no successful hacking attempt!

→ Reply

ivplay

11 years ago, # ^ |

may be there was hack in E. :p

→ Reply

fyflwc779

11 years ago, # ^ |

→ Reply

TangSiLoveDingYing

11 years ago, # |

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

→ Reply

kavishrox

11 years ago, # |

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

→ Reply

pachon

11 years ago, # ^ |

← Rev. 3 →

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

→ Reply

HellKitsune

11 years ago, # ^ |

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.

→ Reply

kavishrox

11 years ago, # ^ |

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

→ Reply

ivplay

11 years ago, # |

what was the idea of D?

→ Reply

11 years ago, # ^ |

Bruteforce and TernarySearch , my friend.

→ Reply

6467987 6468437 6468850 6467987

11 years ago, # ^ |

Integer ternary search Oo

You crazy person...

P.S. I thought, we can't avoid using set in this problem. Such a surprise.

→ Reply

mc_mosa

11 years ago, # ^ |

← Rev. 2 →

Actually the $\text{[math]}$ solution passes in time! >.>

→ Reply

11 years ago, # ^ |

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

→ Reply

11 years ago, # ^ |

6469423

Well, but his solution is AC.

→ Reply

11 years ago, # ^ |

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

→ Reply

11 years ago, # ^ |

-6

Weak tests, round should be unrated :Ъ

→ Reply

mc_mosa

11 years ago, # ^ |

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.

→ Reply

11 years ago, # ^ |

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.

→ Reply

11 years ago, # ^ |

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

→ Reply

11 years ago, # ^ |

Oh nice counterExample , maybe in random cases my solution works well:)

→ Reply

alv-r-

11 years ago, # ^ |

I thought this during the contest, so I went for the O(N^4) solution :(

Still, in the editorial (http://codeforces.me/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?)

→ Reply

choke

11 years ago, # ^ |

← Rev. 2 →

champero detected !! :P, Nice problem.

→ Reply

afrizal

11 years ago, # |

Any editorial?

→ Reply

JuanMata

11 years ago, # ^ |

here it is.

→ Reply

Lazzaro

11 years ago, # |

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

→ Reply

xennygrimmato

11 years ago, # |

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

→ Reply

JuanMata

11 years ago, # ^ |

the upper limit of int is 2147483647, which is more than 2e9. so ofcourse it will pass!

→ Reply

OpalDshawn

11 years ago, # |

I am wondering if this algorithm is correct or not. http://codeforces.me/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

→ Reply

DarkZero

11 years ago, # |

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

→ Reply

cristb

11 years ago, # |

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.me/contest/424/submission/6465131

Thanks.

→ Reply