Solution of Codeforces Round 149 Div 2

Link: http://codeforces.com/blog/entry/5837

Codeforces Round #149 (Div. 2) Tutorial

By NALP, 3 days ago, translation, , 

242A - Heads or Tails

This problem was very easy, we should only use two cycles with i and with j (a ≤ i ≤ x, b ≤ j ≤ y), iterate all possible outcomes of the game and print such in that i > j. The time is O(x·y).

242B - Big Segment

At first, we must note that the answer is always unique, because if segment i covers segment j, that segment j can't cover segment i. It possible if and only if there are coincide segments in the set, but it's not permissible by the statement. Let's pay attention the answer covers the most left point of all segments and the most right point of all points too. Now then we should found L = min(l_i) and R = max(r_i) and print index of segment [L, R], or  - 1 if there is no such segment in the set. The time isO(n).

242C - King's Path

The most important thing for accepted solution is that it is guaranteed that the total length of all given segments doesn't exceed 10⁵. We should use this feature, let's number allowed cells and found shortest path by BFS. It's easiest to use associative array such as map in C++ for numbering. The time is O(n·log(n)).

242D - Dispute

Denote current value of counter number i as b_i. Let's describe an algorithm. It takes any counter i such that b_i = a_i and presses its button. The algorithm finishes if there is no such i.

Let's proof correctness of the algorithm:

1. Why does Valera win the game? Because there is no such counter which has b_i = a_i else we must press the button.
2. Why doesn't algorithm press some button multiple times? Because it presses button number i only if b_i = a_i, and after this pressing the value b_i is increased and the equation will be true never.
3. Why is the algorithm fast? Because of paragraph 2 it does no more n pressings which produces no more n + 2·m increases of the counters. We should use queue for fast seaching counters which has b_i = a_i like this: every time we change value of the counter numbered i we check equation b_i = a_i and if it's true then we push value i to the queue. It's easy to understand that all indexes i will be in queue no more one time.

Also these paragraphs proof that the answer always exists. You must print  - 1 never. The time is O(n + m).

242E - XOR on Segment

Let's write numbers a₁, a₂, ..., a_n as a table which has size n × 20, and b_i, j is jth bit in a_i. Then sum of numbers on segment [l, r] equals . The last notation helps us to process queries.

For fast implementation we should use 20 binary trees like cartesian trees or range trees. Every tree matchs one of bits (and matchs one of the columns of the table b_i, j).

1. calculation of sum is equal to counting 1-s from l-th to r-th.
2. operation "xor" equals reversing all bits from l-th to r-th (i.e. 0 changes to 1, 1 changes to 0).

The first operation executes for all bit numbers, the second executes only for bits in which input numberx_i has ones.

These operations may be easy implemented with binary trees. The time is O(m·log(n)·20).