4qqqq's blog

Codeforces Round #837 (Div. 2) Editorial
By 4qqqq, history, 23 months ago, In English

We apologize for the delay in editorial of the tasks.

A. Hossam and Combinatorics

Idea: _HossamYehia_

Tutorial
Solution(_HossamYehia_)

B. Hossam and Friends

Idea: _HossamYehia_

Tutorial
Solution(_HossamYehia_)

C. Hossam and Trainees

Idea: _HossamYehia_

Tutorial
Solution(_HossamYehia_)

D. Hossam and (sub-)palindromic tree

Idea: 4qqqq

Tutorial
Solution(4qqqq)

E. Hossam and a Letter

Idea: _HossamYehia_

Tutorial
Solution(_HossamYehia_)

F. Hossam and Range Minimum Query

Idea: 4qqqq

Tutorial
Solution(4qqqq, trie)
Solution(Aleks5d, bitset)
  • Vote: I like it
  • +90
  • Vote: I do not like it

Comments Comments (61)
| Write comment?
»
23 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Auto comment: topic has been updated by 4qqqq (previous revision, new revision, compare).

→ Reply
»
23 months ago, # |
  Vote: I like it +112 Vote: I do not like it

Thanks for the lightning fast editorial.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    We are so sorry for long tutorial :(

    → Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 2   Vote: I like it +22 Vote: I do not like it

    We are so sorry for it. Our friend _HossamYehia_ is sick, so he couldn't write editorial fast.

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Bro no problem, I was just kidding, we knew there must be some issues, otherwise editorials comes out soon.

      Anyways, I hope _HossamYehia_ recovers soon!

      → Reply
»
23 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks for the editorial.

→ Reply
»
23 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Thanks for the editorials.

→ Reply
»
23 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Thanks a lot.

→ Reply
»
23 months ago, # |
  Vote: I like it +8 Vote: I do not like it

video Editorial for Chinese: bilibili

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Waited for educational #139 rating update, and then rating of #837 "temporarily" (maybe permanently) rolled back

→ Reply
»
23 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Is the algorithm in problem C really fast enough? I implemented that in Python (with pre-computed prime list and still got TLE for test case 3.

Similarly, an n^2 algorithm in Python TLEed in case 15 for D.

I understand C++ is the major language for CP but it was a bit unfair.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    even cpp takes 2.8 seconds for me. scary, and I don't think my implementation is particularly terrible, i tried improving it as well. it still stays around 2.7 seconds

    → Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    If you take a look at my previouscomment you will find that problem C accepted in pypy3 but TLE in pypy3 64bit .
    - The constraints of problem C is very tight even for c++ ,I saw many c++ solutions took above 2s to execute and maybe got TLE!

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

      Thank you for the reply. I did see comments like that in the contest thread, I just want to raise the issue again after the official ‘expected solution’ is published…

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

    I was able to make the algorithm pass by multiplying two numbers at a time then factoring the larger number.

    → Reply
»
23 months ago, # |
  Vote: I like it +45 Vote: I do not like it

F can be solved by persistent segment tree + xor hash with a very straightforward thought.

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

    can you explain to me ?

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

      Suppose that $$$hs$$$ is a hash function. After compressing the elements, let the $$$j$$$th leaf of the $$$i$$$th segment tree store $$$hs(j)$$$ if $$$j$$$ has occured an odd number of times up to index $$$i$$$, and $$$0$$$ otherwise, and store in each node the XOR of its children.

      For each query, we can binary search on the $$$l-1$$$ th and $$$r$$$ th segment trees for the leftmost leaf that has different values, which is the answer we seek.

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

    Yep, that's true. But editorial of F is already long, so i decided dont add third solution here.

    → Reply
»
23 months ago, # |
  Vote: I like it +13 Vote: I do not like it

I think you have flipped the statements in point C, p divides a_i and a_j rather than a_i and a_j divide p

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Worth waiting for the editorial, very clear and smooth explanation for C and D

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

After rating of #837 rolled back my rating become 1607->1640 lol

Perhaps too many cheaters removed??

→ Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

Who else need this mind blowing OPTIMIZER ?

show :)
→ Reply
»
23 months ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

Everything makes sense with the trie until the part where scary hashes came in. I'll present a solution with a persistent trie (which is a persistent segtree) and xor hashing.

Imagine if we took the xor of all the elements in the range $$$arr[l \dots r]$$$. The final result we would get would be the xor of all the numbers that occur an odd number of times. So now imagine we took the xor of all the elements in the range $$$arr[l \dots r]$$$ that are also $$$\leq v$$$ for some $$$v$$$. Again, we would get the xor of all the elements $$$\leq v$$$ that occur an odd number of times. We need to find the smallest value $$$v$$$ such that this xor sum is nonzero. Hey, that is binary search!

There are two problems with this approach so far.

1) It is possible to accidentally get a xor of $$$0$$$ with some elements that each occur an odd number of times. For instance, $$$1 \oplus 2 \oplus 3 = 0$$$ but none of them occur an even number of times.

2) How do we even check this binary search?

Let's tackle problem 2 first.

Our check function is checking if the xor of all the numbers in the range $$$arr[l \dots r]$$$ that are also $$$\leq v$$$ is nonzero. We can break this sum up into two prefix sums of $$$arr[1 \dots r] \oplus arr[1 \dots l]$$$.

Imagine we had infinite time and memory to precompute something that lets us find the xor of all the elements from $$$arr[1 \dots i]$$$ that are $$$\leq v$$$ for some $$$v$$$. For instance, if we had a $$$n$$$ implicit segtrees (or tries) where on $$$st[i][j]$$$ we stored the total xor of all $$$arr[k]$$$ where $$$arr[k] = j$$$ and $$$k \leq i$$$. A check would be a query from $$$(0, v)$$$ on $$$st[l-1]$$$ xored with a query from $$$(0, v)$$$ on $$$st[r]$$$.

We, unfortunately, do not have infinite memory, we can notice that $$$st[i]$$$ and $$$st[i-1]$$$ differ by very little. This leads us to think about persistent segtrees. We can make N versions of a segtree where in each version we xor $$$st[i][arr[i]]$$$ with $$$arr[i]$$$.

This now gives us an $$$O(n \log n + q \log^2 n)$$$ solution since we are binary searching for 1 log and querying the persistent segtree to check for a second log. I don't know if this can pass, but we can improve queries to only be $$$\log n$$$.

Walking on segtree is a special case of binary search where each query only relies on information aggregated in the segtree instead of a segtree query. Each segtree node corresponds to a range $$$[lo \dots hi]$$$; we want to find the leaf node that corresponds to the answer where on each step we can go the left or the right child. If the two left children of versions l-1 and r have a nonzero xor, we know the answer is the left children; otherwise, it is with the right children. Now since checking is $$$O(1)$$$, the complexity is $$$O(n \log n + q \log n)$$$.

Now for the first problem, we have to avoid collisions. We can assign each value a random hash from $$$[0, 2^{60})$$$ such that if $$$arr[i] < arr[j]$$$, $$$hash[arr[i]] < hash[arr[j]]$$$ and use much larger implicit segtrees. This makes query/update time $$$\log MAX$$$ where $$$MAX$$$ is the max hash value used. For the math behind collisions, Odd Mineral Resource (1479D)'s editorial is nice. The final complexity is $$$O(n \log MAX + q \log MAX)$$$. My submission can be found here.

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the proof of the complexity for problem C?

→ Reply
»
23 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Dear _HossamYehia_, Are you sure problem C is $O(n \times \frac{\sqrt A}{\log A})$？There is a set inside your code.

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

    you can use unordered_set. My solution do it. Sorry, tutorial was written by me :( But Hossam solution is fast enough.

    → Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

can someone help me with Problem C? I am getting TLE, though I used the same algorithm as in the editorial to solve the problem. Link to my submission : https://codeforces.net/contest/1771/submission/185215774

→ Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I tried to find a problem. Sadly, I couldn't. I can just give you some general tips how to speed up your code. A must-have is fast IO: ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); This unsyncs cin and cout, which makes the code faster. However, you must remove it on interactive problems, and you mustn't use "endl", use '\n' instead.

    Also there are such things as pragmas. They usually also speed up, however they don't work on some platforms. I use these: pragma GCC optimize("O3,unroll-loops") pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") They start with symbol #, just as include does

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

      Thank you for the tips.

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

      On some compiler " pragma GCC optimize("O3,unroll-loops") pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") " Give error as I have previously asked a drought Spoj. How to fight these types of questions with tight constraints? I was calculating prime till 1e5 getting TLE. I change it to 35000, and it passes.

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Don't use unorder_map if the number less than 1e7 or 1e6.Replace with an array, just like the std.

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is my code getting TLE in problem C? Can someone help me to optimize it? 185388869

→ Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem E is really simple. For each point, determine how far up/down it can go before encountering a yellow, and how far up/down it can go if it encounters exactly one yellow (this isn't that hard).

Then, simply bash out all possible middle lengths, and you get the answer relatively easily.

Code:184788266

→ Reply
»
23 months ago, # |
  Vote: I like it +3 Vote: I do not like it

In bitset solution of F what does the line #pragma optimize("SEX_ON_THE_BEACH") do?

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

With the kind of problems like F you can easily just request to print $$$ans_q$$$, it is just as hard.

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is 185759665 this code passing and 185759576 this code giving TLE verdict.

→ Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Can anyone please help me understand editorial of prblm C in details with examples ? I can't understand the editorial

→ Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

So, let's factorize all numbers and check

For D2C it sounds pretty much like "so, just brute force it"

It will be O(n*A*sqrt(A)/(logA) — fast enouth.

Fast enough if you use c++

100k * 30k / 30 = 1e8 division operations

For others it made it pretty much unsolvable unless they do some heavy optimizations and use sophisticated methods.

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by 4qqqq (previous revision, new revision, compare).

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by 4qqqq (previous revision, new revision, compare).

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hey everyone. In problem C, if we are calculating prime numbers $$$\le \sqrt{A}$$$, why isn't the time complexity $$$O(n\cdot\frac{\sqrt{A}}{\log{\sqrt{A}}})$$$?

Ref: https://en.wikipedia.org/wiki/Prime_number_theorem#Statement

Edit: Never mind. It wouldn't matter because that would effectively become $$$O(2\cdot n\cdot\frac{\sqrt{A}}{\log{A}})$$$

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't problem D too standard? (the Longest Palindromic Subsequence DP can be easily searchable).

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

F is subproblem of this problem

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My submition 198457835 get MLE in test 15. There are no STL or struct or any possible thing which will lead to MLE. I only use 16M for normal c++ array(something like : int dp[2000][2000]) please someone help me, i've tried everything i can come up with but failed.

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

    sorry i just find out i give a too small array for the edge,but still don't understand why it is mle but re

    → Reply
»
19 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can somebody explain why int problem B it adds mn[i] — i to the answer each time? What does it represent? If mn[i] stores the index of the closest non-friend lying on the right of i, then to me mn[i] — i is just the distance between the person i and it's closest non-friend to the right. Ho can this be related to the number of subarrays? Please help

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

    please help

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      If mn[i] is the index of closest friend to the right of i, then any valid subarray with its left endpoint at index i can end at {i, i+1,..., mn[i] — 1}. So the number of such subarrays is (mn[i] — i)

      → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Thanks you so much, really. You teach me One very useful thing.

        → Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Deleted

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the solution for C may actually fail. Can't the numbers Ai and Aj have a prime gcd which is greater than root Ai and root Aj like 2*p and 3*p type numbers there we will ignore accounting for p since it is greater than root of them but it will be wrong!!please rectify me if I am wrong..

→ Reply
»
4 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Deleted

→ Reply