### isaf27's blog

By isaf27, history, 2 months ago,

• +40

 » 2 months ago, # |   +18 This was one of the most unbalanced rounds ive been in but div2D was pretty cool i guess
 » 2 months ago, # | ← Rev. 6 →   0 My solution for Div2D/1B. This was the main observation of solution (and the coolest part about this problem for me)Let's see what happens if you reverse a whole sequence of length x.x, x-1, x-2... 3, 2, 1Now let's imagine how this looksquery(1, 1), query(1, 2), query(1, 3)... query(1, x-1), query(1, x) it turns out that it looks like this  0, 0 + 1, 0 + 1 + 2... (0... x-3) + x-2, (0... x-4) + x-1 Yes, length = x = query(1, x) — query(1, x-1) + 1. Now, Let's do a binary search to find k. length of segment [j, k] = k - j + 1 = query(1, k) - query(1, k-1) + 1. j = k - query(1, k) + query(1, k -1) you can repeat this for [i, j-1] to figure out i. codeI also tried to explain my thought process, hope it helps. :D
•  » » 2 months ago, # ^ |   0 I think that's exactly the editorial solution
•  » » » 2 months ago, # ^ | ← Rev. 3 →   0 oh really, I didn't carefully read the editorial. I saw this "Finaly, we can solve quadratic equation for k−j+1 and get k." and closed, lol.I didn't do anything like that (quadratic equations scary) and it seems they binary searched on i. It is much cleaner and quite different IMO
•  » » » » 2 months ago, # ^ |   0 Theyre just optimizing for the query count in a weird way. In practice you could've just have asked an extra query to figure out the size of the other part is.
•  » » » » » 2 months ago, # ^ |   0 Oh, my bad then. I actually saw some people solving with some similar solution (turning the problem into some quadratic equation) in the contest. So I felt lazy to carefully read it. My bad
 » 2 months ago, # |   +33 speedforces and implementionforces
 » 2 months ago, # | ← Rev. 4 →   0 For problem D div 2, I don't know what went wrong with my submission at 135395991 (it received a Query Limit Exceeded), since I had the same approach and even took some time to reduce 2 binary searches down to 1. I then changed my binary search implementation (135421249), and got Accepted, but I still don't know why my old implementation of binary search used much more queries though. I hope somebody could tackle my code and find out what's wrong with my old implementation. And I still feel pretty bad for having been so close to D, I could've been promoted to pupil. But overall, nice problem and great contest!
•  » » 2 months ago, # ^ |   +1 What you were doing was an incorrect implementation of binary lifting. The idea of binary lifting is that you have a condition that will be fullfiled by jumping a values less or equal $x$, but not bigger or equal to $x + 1$ (in your case, that condition is that the query from $1$ to $n-x$ to get the entirety of the reversed segments). But since $x$ can be represented in binary, we can progressively make jumps in all powers of two in decreasing order. For example, lets say that $x = 1011001_2$. Our program could first try $1000000_2$ and it would work, so we jump that ammount. Then, it would try $100000_2$ and it would fail, because $1100000_2 > 1011001_2 <=> 1100000_2 > x$. Then it would try $10000_2$ and it will work, because $1010000_2 <= 1011001_2 <=> 1100000_2 <= x$. This algorithm will find the exact x we're looking for in $log(n)$ steps.However, in your algorithm, since youre not working with clean powers of two, you have to keep using the same value until it doesnt fit anymore, but in a case where you would have to use each value exactly once it would waste queries. For example, if $x = 111111_2$ your algorithm could try $100000_2$ once, it would work, then it would try it again, it wouldnt work, and then you try $10000_2$, it works, then you try again, it doesnt anymore...That way you end up doing $log(n)*2$ queries, or $60$ queries, which doesnt pass.Because of the map optimization you did preventing the same query to be answered twice, just changing to powers of two already works: 135543351, but ideally you should not have the while in the first place: 135553555
•  » » » 2 months ago, # ^ |   0 Woah, I've been implementing binary search like this for ages and never realized what I did was wrong. Today I learned something, thanks for pointing out.
 » 2 months ago, # |   +8
 » 2 months ago, # |   +55 For Div1D, we can just do dfs and use map to store answer.
•  » » 2 months ago, # ^ |   +10 I passed with the same method
•  » » » 2 months ago, # ^ |   +34 The complexity is similar to the std.
•  » » » » 2 months ago, # ^ |   0 Certainly. I just make every character as the next appeared one in the LCS then it passed
 » 2 months ago, # | ← Rev. 2 →   0 I seem to get a runtime error for Div1C, which I can't reproduce locally for the same test case- anyone have ideas on what could be wrong?https://codeforces.com/contest/1588/submission/135533102UPDATE: I was able to edit the logic for modifying the map to get A/C but unable to see what the issue was. New submission- 135560689
 » 2 months ago, # |   +77 I see... you guys have developed a new LaTeX formula usage.It's normal for beginners to not use $\log$ instead of $log$. But when I see lonely =s and <s are excluded from the great union form by the  delimiters, my eyes blurred, poor little symbols.Things all changed when you wrote binomial coefficients as $\Large (_2^{k - j + 1})$, a very impressive and revolutionary act. Now I can write Stirling numbers so easily: $\large [_2^{k - j + 1}]$ and $\large \{_2^{k - j + 1}\}$, forget about \brace and \brack, great job guys!
 » 2 months ago, # |   +4 Bonus! I used Dinic to solve problem C!
•  » » 2 months ago, # ^ |   0 I used Hungary Algorithm
 » 2 months ago, # |   0 For 1584D - Guess the Permutation there is easier solution. Instead of using [x, n] ranges, let's take a look at ranges [1, x]. Notice, that starting from k number of inversions never change, because all numbers after k is greater than k, so they can't produce any inversions. So, using binary search over x we know k after around 30 queries. Then, notice that new value at position k is actually j, because this is how we reverse things. And before it there is exactly (k — j) numbers which are greater than j. So, if we ask [1, k — 1] we get number (k — j) and it's easy to derive j from it. This require single additional query (if you don't cache results). Notice that for [1, j — 1] works same approach: at position (j — 1) stands i. And before it there is exactly (j — 1 — i) numbers which are greater than i. So if we ask [1, j — 2] we get number (j — 1 — i) and it's easy to derive i from it. This require two additional queries in case when range [j, k] is not short. So, it require around 33 queries in total. No binomial coefficients involved, no quadratic equations envolved.
 » 2 months ago, # | ← Rev. 5 →   0 Different algorithm for 2D: First do the query [1,n] and find the total inversion $TS$. Lets try to find the position of $j$. Lets do query in the form [1,x]. Suppose we get $S$. How to know $x1$ If we can't find a solution then definitely $x>=j$. If we can find a solution , it is likely that $x1$ and $q>0$. So lets do the query [1,x-p+1] and get the sum $QS$. If $QS==0$ then $x=j$ and we continue with binary search. According to my intuition there are not so many cases we would encounter where we can find integer solutions to both the equations $\frac{p*(p-1)}{2}=S$ and $\frac{p*(p-1)}{2}+\frac{q*(q-1)}{2}=S$ for $p>1$ and $q>0$. Thus we won't be doing double queries that much, at least until finding the value of $i$, after which we won't be needing double queries any more. And we have 40 queries which means 7-8 extra queries. **I have not proven the correctness the algorithm yet and there may exist hack cases
 » 2 months ago, # | ← Rev. 4 →   0 div. 2 E $c_i^l = a_i^l - a_{i - 1}^l + \ldots + (-1)^{i-1} \cdot a_1^l = a_{l+i-1} - a_{l+i-2} + \ldots + (-1)^{i-1} \cdot a_{l} = c_{l+i-1} + (-1)^{i-1} \cdot c_{l - 1}$Doesn't $c_i^l$ mean $c_{l+i-1}$ ?
•  » » 2 months ago, # ^ |   0 Yes, $c^{l}_{i} = c_{l+i-1}$. I think you might be getting confused as to why there is that $(-1)^{i-1}\cdot c_{l-1}$ term in the end. Notice how the last term in the expansion of $c^{l}_{i}$ is $(-1)^{i-1}\cdot a_{l}$, not $(-1)^{l+i-2}\cdot a_{1}$ :$c^{l}_{i} = a^{l}_{i} - a^{l}_{i-1} + ... + (-1)^{i-1}\cdot a^{l}_{1} = a_{l+i-1} - a_{l+i-2} + ... + (-1)^{i-1}\cdot a_{l}$ (As written in the editorial)We can write the above as:$c^{l}_{i} = (a_{l+i-1} - a_{l+i-2} + ... + (-1)^{l+i-2}\cdot a_{1}) - ((-1)^{i}\cdot a_{l-1} + (-1)^{i+1}\cdot a_{l-2} + ... + (-1)^{l+i-2}\cdot a_{1}) = c_{l+i-1} - (-1)^{i}\cdot c_{l-1} = c_{l+i-1} + (-1)^{i-1}\cdot c_{l-1}$
•  » » » 2 months ago, # ^ |   0 Got it.Thanks a lot.
 » 2 months ago, # |   +11 What is "efinegraph" in Strange LCS ?
•  » » 2 months ago, # ^ |   0 nothing, that's most likely just a typo version of "define graph".
 » 2 months ago, # |   0 Problem C can be done in O(N) without sorting. CodeExplanation : Just count the frequency of each number then for each number it's enough to check this condition :extra[x] + cnta[x] >= cntb[x]. (extra[x] here defines frequency of x-1 left over in the array a.)
 » 2 months ago, # |   +14 1589E - Game with Stones can be solved using "Venice Technique" or whatever you call it. 135753412
 » 2 months ago, # | ← Rev. 2 →   0 imo it would be better to make elimination rounds with full tests and not pretests, because it isn't just matter of rating, many people can be eliminated because of terrible pretests like in this round.
 » 2 months ago, # |   +23 Just wondering for Eligible Segments. You have a constraint that $R$ being changed by $10^{-2}$ will not affect the answer. How did you write the validator to check that hacks do not violate this constraint?
•  » » 2 months ago, # ^ |   +3 Let's just check, that the answers for $R - 10^{-2}$ and $R + 10^{-2}$ are equal.The answer increases then $R$ increases, so this works.I hope it was a good way to avoid double issues.
 » 2 months ago, # |   0 Hey guys, in problem Div2-E/Div1-C, I'm getting MLE on test 37 here and I'm not able to see why. Can someone help me?
•  » » 2 months ago, # ^ | ← Rev. 2 →   +8 I guess deque takes up a lot of space. From what I've read, in libstdc++ it allocates memory in blocks of 512 bytes. Testing deque on codeforces, it seems that even when declared empty in a global variable it takes up a huge amount of memory (around 600 bytes), and if you add even one element it's size becomes around 1100 bytes.Changing deque to vector results in AC: https://codeforces.com/contest/1588/submission/135885469
•  » » » 2 months ago, # ^ |   0 That's exactly it, tnx a lot!!The implementation with deque takes more than 10 times more memory than the vector one.
 » 2 months ago, # |   0 no one's wondering where the tutorial of 1588F - Jumping Through the Array goes?or someone just gives a short explanation
•  » » 2 months ago, # ^ |   0 I've added editorial now
 » 2 months ago, # |   -19 Tutorial for Problem E Paragraph 6 Line 3 has the incorrect word"subsegemtns",please correct it.
 » 2 months ago, # |   +39 Could you please publish some STDs to make the solution easier to understand?
 » 2 months ago, # |   0 I have another idea for 1589E - Game with Stones 136087401. Find all l for r(r -> count(l)). s[i] = k * x[i] + b. After taking i-th rock apply k_new = -k, b_new = k * b + s[i], and lets encode every s[i] as x[i], so after taking j-th rock, k * x[i] + b — gives addition for every rock in [i, j], and then delete every x, s.t. k * x[i] + b < 0. Because k = +-1, we can find such x, kx + b = 0, and then xs that we must delete will be x + dir, x + 2 * dir, x + 3 * dir, etc. For every rock we must add count of xs that kx + b = 0
 » 2 months ago, # |   0 Div 1D can be solved in $O(|\Sigma|^2 2^n)$.
 » 2 months ago, # |   0 In editorial of 2E, shouldn't it be $C^l_i<0$ if and only if $C_{l+i−1}<(−1)^iC_{l−1}$ instead of $C^l_i<0$ if and only if $C_{l+i−1}<(−1)^{i-1}C_{l−1}$
 » 2 months ago, # | ← Rev. 2 →   0 can anyone tell whats wrong in my approach for problem C. Two Arrays .... I am first matching all the already matched elements of array b with array a and deleting them simultaneously from both arrays. Then I am matching the remaining elements of array a with remaining elements of array b by adding 1 to them...If some element is not matched I am printing "NO". Else after end of loop I am printing "yes".
•  » » 2 months ago, # ^ |   0 here is my code...136264178
•  » » 2 months ago, # ^ |   0 For 3,4 and 2,3 you can see that 2 will match to 3 and the other 3 will match with 4. In your solution 3 and 3 will match and live happily ever after but what about 2 and 4?:)