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 | 3870 |

2 | Benq | 3618 |

3 | Miracle03 | 3453 |

4 | peehs_moorhsum | 3430 |

5 | Radewoosh | 3418 |

6 | Petr | 3408 |

7 | maroonrk | 3387 |

8 | sunset | 3338 |

9 | ko_osaga | 3334 |

9 | jiangly | 3334 |

# | User | Contrib. |
---|---|---|

1 | YouKn0wWho | 214 |

2 | 1-gon | 203 |

3 | Um_nik | 195 |

4 | Errichto | 182 |

5 | awoo | 180 |

6 | sus | 176 |

6 | tourist | 176 |

8 | antontrygubO_o | 173 |

9 | maroonrk | 170 |

10 | -is-this-fft- | 169 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Technocup 2022 - Elimination Round 2

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/05/2021 01:19:03 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

This was one of the most unbalanced rounds ive been in but div2D was pretty cool i guess

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, 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.cc/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 casesdiv. 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. 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.)1589E - Game with Stones can be solved using "Venice Technique" or whatever you call it. 135753412

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.cc/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.cc/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

Tutorial for Problem E Paragraph 6 Line 3 has the incorrect word"subsegemtns",please correct it.

Could you please publish some STDs to make the solution easier to understand?

I have another idea for 1589E - Игра с камнями 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?:)