Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Name |
---|
This was one of the most unbalanced rounds ive been in but div2D was pretty cool i guess
My solution for Div2D/1B.
Let's see what happens if you reverse a whole sequence of length x.
x, x-1, x-2... 3, 2, 1
Now let's imagine how this looks
query(1, 1), query(1, 2), query(1, 3)... query(1, x-1), query(1, x)
it turns out that it looks like this
Yes, length = x = query(1, x) — query(1, x-1) + 1.
Now, Let's do a binary search to find k.
code
I also tried to explain my thought process, hope it helps. :D
I think that's exactly the editorial solution
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
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.
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
speedforces and implementionforces
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!
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
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.
Video Editorial of A
For Div1D, we can just do dfs and use map to store answer.
I passed with the same method
The complexity is similar to the std.
Certainly. I just make every character as the next appeared one in the LCS then it passed
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.net/contest/1588/submission/135533102
UPDATE: 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
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!Bonus! I used Dinic to solve problem C!
I used Hungary Algorithm
For 1584D - Guess the Permutation there is easier solution. Instead of using [x, n] ranges, let's take a look at ranges [1, x].
So, it require around 33 queries in total. No binomial coefficients involved, no quadratic equations envolved.
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 $$$x<j$$$ or not?
If $$$S==TS$$$ it definitely is not.
If $$$S==0$$$ it definitely is.
Otherwise lets try to find a integer solution to the equation $$$\frac{p*(p-1)}{2}=S$$$ for $$$p>1$$$
If we can't find a solution then definitely $$$x>=j$$$. If we can find a solution , it is likely that $$$x<j$$$ but we can't be sure because there may also be a solution to $$$\frac{p*(p-1)}{2}+\frac{q*(q-1)}{2}=S$$$ where $$$p>1$$$ 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 can find $$$i=x-p+1$$$. Once we find the value of $$$i$$$, we can later use it to check whether $$$x<j$$$ or not by checking whether $$$x-p+1==i$$$ or not.
Otherwise $$$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
This is exactly what I did. I'm glad I found someone else with the same solution as me lol. As you said, I don't know how to prove it though.
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}$$$ ?
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}$$$
Got it.Thanks a lot.
What is "efinegraph" in Strange LCS ?
nothing, that's most likely just a typo version of "define graph".
Problem C can be done in O(N) without sorting. Code
Explanation : 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.)1589E - Game with Stones can be solved using "Venice Technique" or whatever you call it. 135753412
Hey can you please explain the idea. I find the code a bit difficult to understand
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.
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?
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.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?
Code: https://codeforces.net/contest/1588/submission/135797278
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<int>
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.net/contest/1588/submission/135885469
That's exactly it, tnx a lot!!
The implementation with deque takes more than 10 times more memory than the vector one.
no one's wondering where the tutorial of 1588F - Jumping Through the Array goes?
or someone just gives a short explanation
I've added editorial now
Could you please publish some STDs to make the solution easier to understand?
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 = 0Div 1D can be solved in $$$O(|\Sigma|^2 2^n)$$$.
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}$$$
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".
here is my code...136264178
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?:)
For Div2E. the problem reduces to finding the nearest position on suffix which is strictly less than some $$$x$$$. Can some one please explain in a bit more detail as to how to do it?
Sorry for necroposting, but why isn't the following solution valid in F:
Take the LCS of first two strings. this is O(sigma^2) (because each string can have up to 2 * sigma characters). Then, take the LCS with the third string (because LCS is associative). this is still O(sigma^2). So on and so forth and we get the final LCS in O(sigma^2 * n), much faster than what is written in the editorial.