BERNARD's blog

By BERNARD, 3 years ago, In English

Hello, I have a problem and some variations on it that I would like to share. At the moment, I don't know solutions to all the problems, so any ideas/solutions are welcomed in the comments.

Problem 0: You are given an array $$$A$$$ of $$$n$$$ integers, and $$$q$$$ queries of the form "$$$l$$$ $$$r$$$ $$$x$$$" and each number in $$$A[l...r]$$$ appear either once or twice. For each query you have to print the number of elements $$$A_j$$$ $$$(l \le j \le r)$$$ such that $$$A_j \lt x$$$, and the number $$$A_j$$$ appears exactly once in $$$A[l...r]$$$.

Problem 1: The same as Problem 0, but without the restriction that each number in $$$A[l...r]$$$ appear either once or twice.

Problem 2: The same as Problem 1, but with the following change in the queries: "an odd number of times" instead of "exactly once".

Problem 3: The same as Problem 0, but we have updates of the form "$$$i$$$": swap $$$A_i$$$ and $$$A_{i + 1}$$$.

Problem 3.5: The same as Problem 0, but we have updates of the form "$$$i$$$ $$$j$$$": swap $$$A_i$$$ and $$$A_j$$$.

Problem 4: The same as Problem 1, but we have updates that change single elements (e.g. $$$A_i := x$$$, $$$A_i := A_i + x$$$, or some combination of updates like these).

Problem 5: The same as Problem 2, but we have updates that change single elements.

Problem 6: The same as Problem 1, but we have updates that change the elements of ranges (e.g. $$$A_i := A_i + x$$$ for $$$(l \le i \le r)$$$, $$$A_i := min(A_i, x)$$$ for $$$(l \le i \le r)$$$, or some combination of updates like these).

Problem 7: The same as Problem 2, but we have updates that change the elements of ranges.

Time limit: ~4s

Memory limit: 256MB~512MB.

$$$(1 \le n, q \le 500 \space 000, 1 \le A_i \le 10^9)$$$

I'm not sure how hard/easy these problems are. I'll update the blog with founded solutions in the future.

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

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

Some of those problems could be solved offline. For every index you can save all queries for which r = index. Then you can maintain +1 for every i such that there isn't any j for which a[i] = a[j] and i, j <= index, and -1 otherwise. And then you can just query sum of all range [l, index] for every l from queries with r = index. You can update segment tree when moving to index + 1 in logN, so complexity will be O(NlogN).

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

I think some problems can be solved with "merge sort tree", maybe updates with only one element with merge sort tree with set or map, but TL is tight

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

An idea for the first three problems:

  1. Group the queries according to the values of x.
  2. Run Mo's Algorithm for each group of queries.
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem 0 and its descendants, do the numbers appear at most twice in the entire array or is it only guaranteed that they will appear at most twice in all the queried segments?

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

    In the queried segments. Does it matter other than if you want do some preprocessing on the array before the queries?

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

I think, that TLs for this problems are too tight, seems like only O(log n)/query solutions will fit (although even some O(log n) solutions will not be able to pass TL for n=500000). But your problems are really interesting :)

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

    Thank you! I don't really think 3s is that tight for even $$$Nlog^2N$$$ solutions, is it? I was a lot of times able to squeeze in solutions that does around 2e8 operations when TL was just 1s, so I think 3s shouldn't be that bad. Should I increase the TL to 4s? or maybe change 5e5 to 3e5?

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

      Yes, I think it would be worth lowering the task limits for n and q a bit. In addition, there will be actually more than 2e8 operations, since the O(n log^2 n) estimate omits a constant that is at least 2 (because for each segtree query we visit at most 2 log n nodes). And even 2e8 operations is tight for C++ on Codeforces :)

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

Problem 0 idea: I think we can use Mo's algorithm to get the answer in $$$O(N*\sqrt{N}*\log_{2}N)$$$. $$$N*\sqrt{N}$$$ is from Mo's algorithm and $$$\log_{2}N$$$ is from Mo's add/remove. Here I used the map to get a count of numbers to get exactly how many elements appear exactly once. Since there are only n elements and q Xs we can combine them and compress them from ($$$1$$$ to $$$10^9$$$) -> ($$$1$$$ to $$$2*10^5$$$) now we can use an array instead of a map and it removes the $$$\log_{2}N$$$ factor. This means we can now solve the problem in $$$O(N*\sqrt{N})$$$. I think this approach can also be used in both problems 1 and 2.

$$$N = 5*10^5$$$ -> $$$N\sqrt{N} ~ 350*10^6$$$ if time is 1seconds it might be hard.

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

    Won't you need something like BIT as well?

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

      Maybe you can use sqrt decomposition (count $$$1$$$s on segment $$$[0,x - 1]$$$ in $$$O(\sqrt n)$$$, updates in $$$O(1)$$$.

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

Then you can try this ...

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

Can someone Reccomend some good problems for Range Queries at intermediate level ?

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

Problem 0 and 1 in O(nlgn): same idea as distinct value query in range, sort queries by right end point, hold BIT for answers of each left end point for current right end point, iterate from left to right and make most recent occurrence of each value equal 1 in bit and next most recent equal -1, all others equal 0.

Oops wxhtzdy already said :pensive:.

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

    Problem 3-4 O(nlg^2n): think similar to above, but instead you had bit for every single right bound. Realize this each element would be set as 1, -1, or 0 for only 4 consecutive ranges of right bounds. Now, you can think of combinations of bits as 2d range, and use sparse 2d segtree with rectangle additions and queries (can be done similar to poi tetris). For point updates, adjust 1d rectangles along y axis for like 3 x positions, and for queries query 1d rectangles along x-axis. Of course compress and use sparse segtree.

    Is there faster datastructure for setting segments parallel y-axis and querying number that intersect certain y in x-range?

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

      Problem 5 O(n^(5/3)): Same as Mazaalai but Mo's with updates (I still cannot think nlgn for problem 2).

      Problem 2/5 O(n^2/128 * lgn): Group values by groups of 128. Hold BITS that can get xor of range, and let each element correspond to a bit in binary values. Add then just take xors in range and add popcounts lol.

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

    Do you need a 2D data structure for $$$l \le j \le r$$$ and $$$A_j \le x$$$?

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

      Oh shoot forgot to deal with this :weary:. Guess add a log factor and do similar to my 2nd comment :(.