Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### NALP's blog

By NALP, 11 years 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(li) and R = max(ri) and print index of segment [L, R], or  - 1 if there is no such segment in the set. The time is O(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 105. 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 bi. Let's describe an algorithm. It takes any counter i such that bi = ai 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 bi = ai else we must press the button.

2. Why doesn't algorithm press some button multiple times? Because it presses button number i only if bi = ai, and after this pressing the value bi 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 bi = ai like this: every time we change value of the counter numbered i we check equation bi = ai 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 a1, a2, ..., an as a table which has size n × 20, and bi, j is jth bit in ai. 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 bi, 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 number xi has ones.

These operations may be easy implemented with binary trees. The time is O(m·log(n)·20). Tutorial of Codeforces Round 149 (Div. 2) 149, Comments (37)
| Write comment?
 » Excuse me ~ Can you write a solution in English ?~^。^ I'm very impressed with your E problem and want to learn it for a lot.But I can not read Russian. So ……~~
•  » » goto this link:http://codeforces.com/blog/entry/5837
•  » » » Thanks a lot ~ ^_^
 » In problem E complexity should be O(n) + O(m*log(n)*20) = O(n + m*log(n)). Isn't it?
•  » » No, that is not how you calculate the sum of terms in Big-O-Notation. The correct way in this case is to take the fastest growing term, which is O(m*log(n)*20). You can read more about the Big-O-Notation for example in Wikipedia: http://en.wikipedia.org/wiki/Big_O_notation , which will tell you the following: "If a function f(n) can be written as a finite sum of other functions, then the fastest growing one determines the order of f(n)."
•  » » » 11 years ago, # ^ | ← Rev. 2 →   Why do you think that m grows faster than n in this case?
 » Codeforces editorials rarely give detailed explanation of the harder problems, especially when the problem is just about using an advanced data structure. The editorial just says "This can be done using interval trees.". Can someone please explain how to use segment trees in Problem E in more detail? Your explanation will be useful for all those who are just starting to learn segment trees, thanks!
•  » » check my code. 2559296if you dont understand any of my code, please let me know.. :)
•  » » » thanks for sharing your codei understand the build function and a bit of the query and update function. can you explain what is the lazy array used for?
•  » » » » From looking at the code I think it is "Lazy Propagation". Search that up
•  » » I recommend that you first solve https://www.codechef.com/problems/FLIPCOIN to learn about lazy propagation with Segment tress and then solve E problem.My solution http://codeforces.com/contest/242/submission/17871914
 » pro E: nx20 ??why??thanks...
•  » » because 2^20 > 1000000 so 20 bits is enough to represent every number
 » Really, we would really appreciate if someone could give a detailed explanation on the solution of E using segment trees. Thank you.
 » I think The time is O(n+m) for 242D — Dispute
 » I solved 242E — XOR on Segment with naive algorithm without using any data structerlook at my code it solved the problem exactly on time limit and got accepted
•  » » 11 years ago, # ^ | ← Rev. 2 →   lol :D :D how did that code pass tests ?
•  » » » 4000ms!!!
•  » » » » Yes, one more 1ms and my code will get Time limit exeeded
•  » » » » » This naive solution may be a little bit optimised.Instead of using count — just check that tmp is far from overflow.Compare solutions 3064707 and 3064734.
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   I_love_Tanya_Romanova, Can we solve it using fenwick tree. If no, why not ? I read some blog that we can do range update + range query using fenwick tree, but could not solve this problem using this concept. Note that I'm clear with the segtree lazy propag. solution idea.
 » I solved this problem using segment tree I am getting WA on the 15 th test case can anyone help me finding bug in my code here is the link https://ideone.com/0OuZRq
•  » » I am also getting WA on test 15
 » can anyone please point out what is wrong with my code?here is my code http://codeforces.com/submissions/vis10326#
•  » » Clean your code first. Put some spaces and indentations would be enough
 » The same code...i m not as lucky as the latter.