to you he is mister master

thanks to Mike MikeMirzayanov Mirzayanov for the amazing platforms Codeforces и Polygon

The great Mr. Master rotavirus has already predicted this.

.

Problem A: The first line contains a single binary number s ( 0 ≤ s < 2^100) without leading zeroes.

Okay guys. Well played (^_^)

Me: -5, Testers: 1e5

выйди отсюда розбiйник

Of course. I can assure you that the grammar for problem A is on point. I ran it through Grammarly just for you bentaji <3.

Good luck! Hoping to get master

Me too!!! :)

He owns half of the master accounts on Codeforces

Please read previous comments before writing one.

Tiat is so cute! (Tiat is the girl in the picture)

It is only rated for women

quantity =/=> quality
although, it's good to be optimistic.

When I finished 2 Ds, I felt scary. But when I saw my comment here, no more fear.

I just solved some problems and gave some advice to make statements better, I didn't try to submit wrong or tricky solutions. Most of other testers too, I think.

over time

haha

How many time subsequence appear as a subsequence in the problem statement?

Ask a question

Better dont discuss problems while the contest is still running.

When did it ever do that

You gotta be kidding me :(

How did that happen? What is the logic behind it?

мы думали что иначе был бы большой разрыв

What is the problem with 998244853?

Agreed, I prefer 993244853 instead.

What was the solution for E?

I tried greedy, but I got WA on 5th. Never mind, I had a bug. It is a greed algorithm. O(n^3) (Floyd–Warshall) + O(m) linear search get we erase b in this scenario (a — b — c). If dist[a][c] == dist[a][b] + dist[b][c] then we can erase b, otherwise he stays in array.

You can apply Greedy algorithm. For each triplet, ( left, current, right ), if you can go from left --> current and from current --> right ,but you can't directly go from left to right, then we can remove current. This ensures that the shortest path from left to right includes current. Hence, it retains the original sequence.

You can use a stack to process every triplet.

The time complexity is O(m + n*n).

Code

Edit --> It can't be solved without using Floyd Warshall

You can make a Floyd-Warshall to calculate the APSP,then you just need to search the sequence (starting with the first number) the number that is farther away and that the difference in positions is the minimum path between those two, then you keep it and go to that one and repeat it until you reach the end,O(N*M)

I think problem E would be much easier if the constraints are set to fit $$$O(n)$$$, e.g. $$$n \leq 100000$$$, because one need not consider an $$$O(n^2)$$$ approach instead, which could simplify thinking.

Any subsequences, not only consecutive.

Consider subsequence in [3,6]. The longest non-decreasing in input is 2, but your example is 3.

In 001100 the longest non-decreasing subsequence is 4 In 000100 the longest non-decreasing subsequence is 5

But in input string the longest non-decreasing subsequence s[1:6] = 4, not 5!

You're considering sub-string(s) . For 't' we have to consider sub-sequences.

Can you explain it more clearly ? Thank you !

Do you have any other problems that use the same technique? :)

how to solve?

In normal rounds yes, but in the extended ICPC rules you get 12 hours of open hacking after the contest ended.

BFS for each vertex works well too.

нет,во-первых, нужно знать путь между всеми вершинами(флойд легче всего),потом фиксируем первую вершину и смотрим расстояние от фиксированной до следующей ,и от следующей до следующей после следующей(был такой массив p : 1 9 5 4 7.Тогда смотрим расстояние от 1 до 9 и расстояние от 9 до 5).Если от 1 до 9 расстояние меньше чем расстояние от 9 до 5 то продолжаем ,иначе фиксируем 9 и кидаем ее массив, далее тоже самое (смотрим d[9][5] и d[5][4],если первое меньше то продолжаем и далее смотрим d[9][4] и d[4][7],или фиксируем 5)...

It means, that there is no strictly shorter path than p passing through all vertexes v1, ..., vk in that order.

The ratings need like an hour or so, sometimes more.

Score distribution? There is a link to "Standings".

I would not say the hardest, although clearly harder than B for me

And the meaning of "The main characters have been omitted to be short."

With numbers up to 2^256 I think using that might be not precise enough.

I mean, they don't need to be adjacent to have a shortest path that goes around the 'inter' in your code.

After experimenting with various test cases, I finally came up with one that your code fails on. I hope this will help you better in understanding where you went wrong

4
0101
0010
0001
0000
4
1 2 3 4

The expected answer is of length 3 , but your code outputs a sequence of length 2.

Hint : Suppose we have a sequence (a,b,c,d). We take a into our path. We cannot reach c from a, hence we neglect b. Now, we cannot reach d from c, hence we also neglect c. This is where you went wrong. Since we've already deleted b, we should check the condition on the triplet (a,c,d).

When testing, testers mostly gave feedback on the problems, not the tests. Also, all testers who solved C did so without running into this test case.

And just because a single case wasn't covered doesn't mean all basic cases weren't covered. A lot of edge cases were covered, for example:

2 0100 2 1 2

System tests and hacks are a part of Codeforces, it's really hard to avoid and check every single case.

Please be considerate of the authors for taking the time to put the round together and writing the problems. It's a shame this happened to many participants.

Best of luck in the future.

dude, the humans' idiotism, retardness and stupidity don't have limits.

See the glass as half full: you have the opportunity to hack someone.

s.size() returns size_t type integer, where size_t is an unsigned integral data type. So, it can't be negative.

s.size() has type size_t, if say size is 1 and you subtract 2 from it, it won't go to -1, it wraps around, see this : size_t in reverse for loop

using ll ensures proper conversion. :)

shit I wrote

for (int j = i - 1; j >= max(1, j - 100); j--) {

instead

for (int j = i - 1; j >= max(1, i - 100); j--) {

get AC in 0.6 s

there is an arc from 3 to 1