STARCP's blog

By STARCP, history, 3 years ago, In English
Recently when i'am practicing i encounter two problems that have something common in them i could not understand editorial and others solutions too can someone help to find a approach for this kind of problems below are the links to two problems.

1237B - Balanced Tunnel
the editorial to this problem written by tourist

Spoiler

and the second problem.

591B - Rebranding
the solution to this problem in editorial

Spoiler

can anyone explain the intution behind this two problems?

  • Vote: I like it
  • +8
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

$$$First$$$ $$$problem:$$$ There are multiple ways you can try to solve this, but the one i thought first, is using BIT aka fenwick tree (which you should definitely learn if you dont know it already, but its a way of doing prefix sums on a array with updates), where for each car in the exit order we will check if we already passed through all the cars that come before it in the entrance order. That would be $$$O(nlogn)$$$.

The editorial solution is basically saying that, going through the sequence of the exit, the car would be fined if it entered before the car that entered last that you already passed through, but they explain it in a mathy way. You can check that pretty easily in $$$O(n)$$$

$$$Second$$$ $$$problem:$$$ The important observation is that you dont need to construct the string again every step of the way, what matters is only how the letters will be swaped in the end. For that we just need two arrays: let $$$s[i]$$$ be the letter that the letter i will be swapped by, and $$$t[i]$$$ be the letter that will be swapped by i. When a new version comes that swap the letters x and y given by the problem, you just need to swap s[t[x]] and s[t[y]], and then you swap t[x] and t[y]. If you can't see it at first, try looking at the test cases and costructing both arrays in a piece of paper. Then, you just need to, in the end, swap each letter of the original string with the letter in s[i].

When you see those kinds of problems 1300 elo ish problems, normally the concepts used on them are very simple, but in editorials they use a lot of math to describe them because it's easier to prove that your solution works if you do that. So try when reading similar stuff, try to understand what they are trying to acomplish behind what they are saying and i think you have a better chance of understanding the editorials. Most of them are pretty shit tho so dont feel bad