4qqqq's blog

By 4qqqq, history, 3 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

 » 3 months ago, # |   +17 Auto comment: topic has been updated by 4qqqq (previous revision, new revision, compare).
 » 3 months ago, # |   +112 Thanks for the lightning fast editorial.
•  » » 3 months ago, # ^ |   +19 We are so sorry for long tutorial :(
•  » » 3 months ago, # ^ | ← Rev. 2 →   +22 We are so sorry for it. Our friend _HossamYehia_ is sick, so he couldn't write editorial fast.
•  » » » 3 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!
 » 3 months ago, # |   +8 Thanks for the editorial.
 » 3 months ago, # |   +14 Thanks for the editorials.
 » 3 months ago, # |   +5 Thanks a lot.
 » 3 months ago, # |   +8 video Editorial for Chinese: bilibili
•  » » 3 months ago, # ^ |   0 Great
 » 3 months ago, # |   0 Waited for educational #139 rating update, and then rating of #837 "temporarily" (maybe permanently) rolled back
 » 3 months ago, # |   0 Can anyone explain problem B ?
 » 3 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.
•  » » 3 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
•  » » 3 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!
•  » » » 3 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…
•  » » 3 months ago, # ^ |   0 I was able to make the algorithm pass by multiplying two numbers at a time then factoring the larger number.
 » 3 months ago, # |   +45 F can be solved by persistent segment tree + xor hash with a very straightforward thought.
•  » » 3 months ago, # ^ |   0 can you explain to me ?
•  » » » 3 months ago, # ^ |   +3 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.
•  » » 3 months ago, # ^ |   0 Yep, that's true. But editorial of F is already long, so i decided dont add third solution here.
 » 3 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
 » 3 months ago, # |   0 Worth waiting for the editorial, very clear and smooth explanation for C and D
 » 3 months ago, # |   0 After rating of #837 rolled back my rating become 1607->1640 lolPerhaps too many cheaters removed??
 » 3 months ago, # | ← Rev. 2 →   +24 Who else need this mind blowing OPTIMIZER ? show :)
 » 3 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 $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.
 » 3 months ago, # |   0 What's the proof of the complexity for problem C?
•  » » 3 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)
 » 3 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.
•  » » 3 months ago, # ^ |   0 you can use unordered_set. My solution do it. Sorry, tutorial was written by me :( But Hossam solution is fast enough.
 » 3 months ago, # | ← Rev. 2 →   0 C taught too much
 » 3 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://codeforces.com/contest/1771/submission/185215774
•  » » 3 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
•  » » » 3 months ago, # ^ |   0 Thank you for the tips.
•  » » » 3 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.
•  » » 3 weeks ago, # ^ |   0 Don't use unorder_map if the number less than 1e7 or 1e6.Replace with an array, just like the std.
 » 3 months ago, # |   0 Why is my code getting TLE in problem C? Can someone help me to optimize it? 185388869
 » 3 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
 » 3 months ago, # |   0 Thanks for the editorial
 » 3 months ago, # |   +3 In bitset solution of F what does the line #pragma optimize("SEX_ON_THE_BEACH") do?
•  » » 3 months ago, # ^ |   +6 it teases you to ask about it
•  » » 3 months ago, # ^ |   0 it's my good luck charm :)
 » 3 months ago, # |   0 With the kind of problems like F you can easily just request to print $ans_q$, it is just as hard.
 » 3 months ago, # |   0 Why is 185759665 this code passing and 185759576 this code giving TLE verdict.
 » 3 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
 » 3 months ago, # | ← Rev. 2 →   0 Problem ratings were released just now. Is it reasonable to believe that the ratings were blown out of proportion? No way problem E is 2500, that one looked like 2200 max.
 » 3 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.
 » 3 months ago, # |   0 C is too good
 » 3 months ago, # |   0 Auto comment: topic has been updated by 4qqqq (previous revision, new revision, compare).
 » 3 months ago, # |   0 Auto comment: topic has been updated by 4qqqq (previous revision, new revision, compare).
 » 3 months ago, # | ← Rev. 2 →   0 I am not able to pass the test case 24 in A. Hossam and Combinatorics. //My Java code import java.math.BigInteger; import java.util.Arrays; import java.util.Scanner;public class A_Hossam_And_Combinatorics { public static void main(String[] args) { Scanner s = new Scanner(System.in); int t = s.nextInt(); for (int i = 0; i < t; i++) { int[] a = new int[s.nextInt()]; for (int j = 0; j < a.length; j++) { a[j] = s.nextInt(); } Arrays.sort(a); System.out.println(helper(a)); } s.close(); } public static String helper(int [] a) { if (a[0] == a[a.length - 1]) { return (BigInteger.valueOf(a.length).multiply(BigInteger.valueOf(a.length-1))).toString(); } int i = 0, j = a.length - 1; while (a[0] == a[i]) ++i; while (a[a.length - 1] == a[j]) --j; return ""+ (2 * i * (a.length - j - 1)); } }//This is the test case resultTime: 233 ms, memory: 680 KB Verdict: WRONG_ANSWER Input 1 100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... Participant's output 705032704 Jury's answer 5000000000 Checker comment wrong answer 1st numbers differ — expected: '5000000000', found: '705032704'
 » 3 months ago, # |   0 can anyone explain the idea for problem B
•  » » 2 months ago, # ^ |   0 Well the last person has no more people in right, so no problem from him, the second last can only have problem with the last, but let say the person at index 2 has a problem with that of index 5 and that of index 3 has a problem with index 4, obviously the max you can go will be uptil 3 not 4, since if you get to 4 person at index 3 will have a problem. Same way if you start from behind and just make sure i and (i+1)th peoples interest are aligned
 » 2 months ago, # | ← Rev. 2 →   0 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}}})$?Edit: Never mind. It wouldn't matter because that would effectively become $O(2\cdot n\cdot\frac{\sqrt{A}}{\log{A}})$
 » 4 weeks ago, # |   0 In problem A, 3rd test case where all elements are same, the expected answer is wrong. If we multiply the count by two for every chosen points for the positions of the two friends can reverse, so I think the answer there should be multiplied by 2 again.
 » 3 weeks ago, # |   0 Isn't problem D too standard? (the Longest Palindromic Subsequence DP can be easily searchable).
 » 3 weeks ago, # |   0 F is subproblem of this problem
 » 6 days 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.
•  » » 6 days 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