NALP's blog

By NALP, 12 years ago, translation, In English

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

  • Vote: I like it
  • +57
  • Vote: I do not like it

| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ……~~

»
12 years ago, # |
  Vote: I like it -8 Vote: I do not like it

In problem E complexity should be O(n) + O(m*log(n)*20) = O(n + m*log(n)). Isn't it?

  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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)."

    • »
      »
      »
      12 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Why do you think that m grows faster than n in this case?

»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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!

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

pro E: nx20 ??why??thanks...

  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    because 2^20 > 1000000 so 20 bits is enough to represent every number

»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Really, we would really appreciate if someone could give a detailed explanation on the solution of E using segment trees. Thank you.

»
12 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I think The time is O(n+m) for 242D — Dispute

»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I solved 242E — XOR on Segment with naive algorithm without using any data structer

look at my code it solved the problem exactly on time limit and got accepted

  • »
    »
    12 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    lol :D :D how did that code pass tests ?

    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      4000ms!!!

      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, one more 1ms and my code will get Time limit exeeded

        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it -13 Vote: I do not like it

can anyone please point out what is wrong with my code?here is my code http://codeforces.me/submissions/vis10326#

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Clean your code first. Put some spaces and indentations would be enough

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am getting wrong answer on test 10 in problem C My code: http://codeforces.me/contest/242/submission/14186492 anyone please help

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same problem, In fact I am also getting the same answer as yours for test case 10 :/

»
6 years ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

E : good problem

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So much week testcases of problem E. Many of accepted solutions have more than 10^5 * 10^5 complexity.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

lazy segment tree solution of E Xor On Segmentcode

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody explain E ? Thanks.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    If you are still curious about this problem — the idea is as follows. Maintain a segment tree for each bit and a lazy tree for each bit (containing info on whether ith bit is set in each of the numbers). For each update query, flip the bits in the current range and invert the child's lazy bit values, but only if the ith bit is set in the number that we xor our range with, otherwise skip to the next one. The same is applied in the sum query.

    It is the standard lazy segment tree implementation with a little twist (multiple trees). Here's a link to a tutorial and my submission for further clarification:

    https://codeforces.me/contest/242/submission/103977271

    https://www.geeksforgeeks.org/lazy-propagation-in-segment-tree/

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can't we solve problem E with lazy-segment tree? thank you in advance..

  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes all we have to do is to construct 20 lazy segment tree for every bit.

    my solution: 216845895