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

NALP's blog

By NALP, 6 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  

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

»
6 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?

  • »
    »
    6 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)."

    • »
      »
      »
      6 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?

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

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

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

  • »
    »
    6 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

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

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

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

»
6 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

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

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

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

      4000ms!!!

      • »
        »
        »
        »
        6 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

        • »
          »
          »
          »
          »
          6 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.

          • »
            »
            »
            »
            »
            »
            15 months ago, # ^ |
              Vote: I like it -8 Vote: I do not like it

            can you please explain the logic of this optimisation

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

            How can i solve Problem E using segment tree with lazy? i don't understand the logic of lazy.

            i see one source code where use tree[20][maxn],lazy[20][maxn] such as 2d array. i don't understand why we use this 2d array

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

Won't sqrt-decomposition work for E?

»
5 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

»
4 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.com/submissions/vis10326#

  • »
    »
    4 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

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

i have cleaned that too but it's giving runtime error what can be the reason for that?i have cleaned that too

»
3 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.com/contest/242/submission/14186492 anyone please help