### 4qqqq's blog

By 4qqqq, history, 18 months ago,

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)
• +90

| Write comment?
 » 18 months ago, # |   +17 Auto comment: topic has been updated by 4qqqq (previous revision, new revision, compare).
 » 18 months ago, # |   +112 Thanks for the lightning fast editorial.
•  » » 18 months ago, # ^ |   +19 We are so sorry for long tutorial :(
•  » » 18 months ago, # ^ | ← Rev. 2 →   +22 We are so sorry for it. Our friend _HossamYehia_ is sick, so he couldn't write editorial fast.
•  » » » 18 months ago, # ^ |   +16 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!
 » 18 months ago, # |   +8 Thanks for the editorial.
 » 18 months ago, # |   +14 Thanks for the editorials.
 » 18 months ago, # |   +5 Thanks a lot.
 » 18 months ago, # |   +8 video Editorial for Chinese: bilibili
•  » » 18 months ago, # ^ |   0 Great
 » 18 months ago, # |   0 Waited for educational #139 rating update, and then rating of #837 "temporarily" (maybe permanently) rolled back
 » 18 months ago, # |   0 Can anyone explain problem B ?
•  » » 11 months ago, # ^ |   0 What are you confused about?
 » 18 months ago, # |   +4 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.
•  » » 18 months ago, # ^ |   +8 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
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 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!
•  » » » 18 months ago, # ^ |   +3 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…
•  » » 18 months ago, # ^ |   0 I was able to make the algorithm pass by multiplying two numbers at a time then factoring the larger number.
 » 18 months ago, # |   +45 F can be solved by persistent segment tree + xor hash with a very straightforward thought.
•  » » 18 months ago, # ^ |   0 can you explain to me ?
•  » » » 18 months ago, # ^ |   +3 Suppose that Unable to parse markup [type=CF_MATHJAX] is a hash function. After compressing the elements, let the Unable to parse markup [type=CF_MATHJAX] 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.
•  » » 18 months ago, # ^ |   0 Yep, that's true. But editorial of F is already long, so i decided dont add third solution here.
 » 18 months ago, # |   +13 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
 » 18 months ago, # |   0 Worth waiting for the editorial, very clear and smooth explanation for C and D
 » 18 months ago, # |   0 After rating of #837 rolled back my rating become 1607->1640 lolPerhaps too many cheaters removed??
 » 18 months ago, # | ← Rev. 2 →   +24 Who else need this mind blowing OPTIMIZER ? show :)
 » 18 months ago, # | ← Rev. 3 →   +11 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 Unable to parse markup [type=CF_MATHJAX]. 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 Unable to parse markup [type=CF_MATHJAX] 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, Unable to parse markup [type=CF_MATHJAX] 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 Unable to parse markup [type=CF_MATHJAX] that are also $\leq v$ is nonzero. We can break this sum up into two prefix sums of Unable to parse markup [type=CF_MATHJAX].Imagine we had infinite time and memory to precompute something that lets us find the xor of all the elements from Unable to parse markup [type=CF_MATHJAX] that are $\leq v$ for some $v$. For instance, if we had a $n$ implicit segtrees (or tries) where on Unable to parse markup [type=CF_MATHJAX] we stored the total xor of all Unable to parse markup [type=CF_MATHJAX] where Unable to parse markup [type=CF_MATHJAX] and Unable to parse markup [type=CF_MATHJAX]. A check would be a query from Unable to parse markup [type=CF_MATHJAX] on Unable to parse markup [type=CF_MATHJAX] xored with a query from Unable to parse markup [type=CF_MATHJAX] on Unable to parse markup [type=CF_MATHJAX].We, unfortunately, do not have infinite memory, we can notice that Unable to parse markup [type=CF_MATHJAX] and Unable to parse markup [type=CF_MATHJAX] 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 Unable to parse markup [type=CF_MATHJAX] 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 Unable to parse markup [type=CF_MATHJAX]; 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 Unable to parse markup [type=CF_MATHJAX].Now for the first problem, we have to avoid collisions. We can assign each value a random hash from Unable to parse markup [type=CF_MATHJAX] such that if Unable to parse markup [type=CF_MATHJAX], Unable to parse markup [type=CF_MATHJAX] and use much larger implicit segtrees. This makes query/update time Unable to parse markup [type=CF_MATHJAX] 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 Unable to parse markup [type=CF_MATHJAX]. My submission can be found here.
•  » » 10 months ago, # ^ |   0 Thanks mate. Very useful :) .
 » 18 months ago, # |   0 What's the proof of the complexity for problem C?
•  » » 18 months ago, # ^ |   +6 https://en.wikipedia.org/wiki/Prime-counting_function The number of prime numbers less than n are of the order of n/log(n)
 » 18 months ago, # |   +8 Dear _HossamYehia_, Are you sure problem C is $O(n \times \frac{\sqrt A}{\log A})$？There is a set inside your code.
•  » » 18 months ago, # ^ |   0 you can use unordered_set. My solution do it. Sorry, tutorial was written by me :( But Hossam solution is fast enough.
 » 18 months ago, # | ← Rev. 2 →   0 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://mirror.codeforces.com/contest/1771/submission/185215774
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » 18 months ago, # ^ |   0 Thank you for the tips.
•  » » » 17 months ago, # ^ |   0 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.
•  » » 15 months ago, # ^ |   0 Don't use unorder_map if the number less than 1e7 or 1e6.Replace with an array, just like the std.
 » 18 months ago, # |   0 Why is my code getting TLE in problem C? Can someone help me to optimize it? 185388869
 » 18 months ago, # | ← Rev. 2 →   0 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
 » 18 months ago, # |   +3 In bitset solution of F what does the line #pragma optimize("SEX_ON_THE_BEACH") do?
•  » » 18 months ago, # ^ |   +6 it teases you to ask about it
•  » » 18 months ago, # ^ |   0 it's my good luck charm :)
 » 18 months ago, # |   0 With the kind of problems like F you can easily just request to print Unable to parse markup [type=CF_MATHJAX], it is just as hard.
 » 18 months ago, # |   0 Why is 185759665 this code passing and 185759576 this code giving TLE verdict.
 » 18 months ago, # | ← Rev. 2 →   +3 Can anyone please help me understand editorial of prblm C in details with examples ? I can't understand the editorial
•  » » 12 months ago, # ^ |   0 did you solve? if so please help
 » 18 months ago, # | ← Rev. 2 →   0 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 operationsFor others it made it pretty much unsolvable unless they do some heavy optimizations and use sophisticated methods.
 » 18 months ago, # |   0 Auto comment: topic has been updated by 4qqqq (previous revision, new revision, compare).
 » 18 months ago, # |   0 Auto comment: topic has been updated by 4qqqq (previous revision, new revision, compare).
 » 17 months ago, # | ← Rev. 2 →   0 Hey everyone. In problem C, if we are calculating prime numbers Unable to parse markup [type=CF_MATHJAX], why isn't the time complexity Unable to parse markup [type=CF_MATHJAX]?Edit: Never mind. It wouldn't matter because that would effectively become Unable to parse markup [type=CF_MATHJAX]
 » 15 months ago, # |   0 Isn't problem D too standard? (the Longest Palindromic Subsequence DP can be easily searchable).
 » 15 months ago, # |   0 F is subproblem of this problem
 » 15 months ago, # |   0 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.
•  » » 15 months ago, # ^ |   0 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
 » 14 months ago, # | ← Rev. 3 →   0 .
 » 12 months ago, # |   0 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
 » 10 months ago, # | ← Rev. 2 →   0 4qqqq Could you please explain the editorial of 1771D - Hossam and (sub-)palindromic tree? I am not getting the part on how to define Unable to parse markup [type=CF_MATHJAX], so I am unable to understand the approach in the editorial where , Unable to parse markup [type=CF_MATHJAX] as well. Does Unable to parse markup [type=CF_MATHJAX], if Unable to parse markup [type=CF_MATHJAX] and $v$ if Unable to parse markup [type=CF_MATHJAX]
 » 9 months ago, # |   0 $2100$ problems all look like alien to me. Do all newbies experience this ?Note: Alien means not even unable to understand even solution.