Блог пользователя awoo

Автор awoo, история, 12 месяцев назад, По-русски

1902A - Двоичный дисбаланс

Идея: BledDest

Разбор
Решение (awoo)

1902B - Зарабатывание баллов

Идея: adedalic

Разбор
Решение (adedalic)

1902C - Вставь и приравняй

Идея: Roms и BledDest

Разбор
Решение (awoo)

1902D - Запросы робота

Идея: BledDest

Разбор
Решение (Neon)

1902E - Коллапс строк

Идея: Roms

Разбор
Решение (Roms)

1902F - Снова деревья и XOR-запросы

Идея: BledDest

Разбор
Решение (BledDest)
  • Проголосовать: нравится
  • +43
  • Проголосовать: не нравится

»
12 месяцев назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

E was awesome. Thanks for great problems

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When will you update the rating change for this round?

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится -49 Проголосовать: не нравится

    It has been unrated I guess

    • »
      »
      »
      12 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How could that be!? Contest title clearly says it's Rated for Div2

      • »
        »
        »
        »
        12 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Idk but when I filtered my contests to only unrated.I found it there so I thought maybe it was made unrated.

        • »
          »
          »
          »
          »
          12 месяцев назад, # ^ |
            Проголосовать: нравится +15 Проголосовать: не нравится

          All contests are shown under 'unrated' before ratings are updated. You can't make any assumtions based on that. If a contest is made unrated, it will be announced on the original contest announcement.

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I've noticed that my position on the leaderboard has increased after the competition fully finished. Maybe they are trying to prune out cheaters?

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

C was the coolest

»
12 месяцев назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Thank for contest! But where is rating?

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It's amazing to see how much implementation matters in Question D — the solution by Neon is so concise and pretty.

»
12 месяцев назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

awoo, I think there is a typo in the editorial for Problem 1902E - Collapsing Strings. It should be $$$|C(a,b)|=|a|+|b|− \textbf{2} \times |LCP(a′,b)|$$$.

»
12 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

F was cute :)

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I don't understand how the code works for problem B that is provided in the solution..

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You just do a binary search on k, which is the number of days Monocarp is going to study. Notice that you can binary search on k because your function to calculate the number of points based on k is monotone: func(k)= k*l + min(c,2k). where c is the total number of tasks.

    Hope this helps you ^^.

»
12 месяцев назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

For Problem D

How Δi,j is found over there in editorial? Is there a simpler way?

I did this in the below given way

Found the pattern of how reversing changes the path(about what lines the pattern is reflected) and accordingly what distance each point is moving with respect to reflections, there by finding the Δi,j.

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If you reach point p=path[l]+d then when commands are reversed you'll have to walk d to reach the end: rp+d=path[r]

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You can also see that the path with reversed actions is obtained through a 180-degree CCW rotation and a shift.

»
12 месяцев назад, # |
Rev. 2   Проголосовать: нравится -17 Проголосовать: не нравится

I feel like tests for F are not really strong or otherwise, I am not sure why my $$$O(n \log n B^2 + q B^2)$$$ solution 235594622 is so fast. I didn't try to optimize anything.

»
12 месяцев назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

LOL, I feel so stupid after looking at the editorial for B. but I am happy to have learnt these "new"(for me) techniques (especially, generating files to find failing testcases, use of ceil() function, proving a greedy approach) and I believe that is one of the main objective of the EDU rounds! I tried to apply greedy approach, was not able to figure out on which cases the code was failing, after like 5 submissions I realized that first ,I should find those days where 2 tasks can be completed like on day 8, 22, 36 etc and add (l+2*t) to points. Then if still points are not enough, add (l+t) to answer if left with any task, and then finally add any remaining points in the form of l. this is my messy solution 235754545. looking forward to better performances in the future.

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The Trie answer for E is accepted by PyPy3 but not PyPy3-64. :(

  • »
    »
    12 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Yeah had the same issue, from what i saw you can use lists instead of dicts to pass it, and since there are only 26 letters at max you can check in O(1) time if the element exists.

  • »
    »
    12 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Generally i feel like Div 2 E is as far as you can get with python, which is why i am trying to transfer to C++. I have had it happen so many times, that i couldn't pass E, but after translating my code to C++ it passed.

»
12 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

EASY Editorial in English For problem A,B,C. Link :- Click Here

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Those who down vote, video was processed after 15 minutes of this comment ,now you can watch it.

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is the difference between https://mirror.codeforces.com/contest/1902/submission/235770255 and https://mirror.codeforces.com/contest/1902/submission/235600034 ? Why does it work when I change beginning to 2n*sum(1->n) then subtract and not when i continuously add to a starting val of 0 length*n+sum-subtracted value . of lengths? When I use summation rules the outcome is the same.

(totallength+(sum of all individual length(which is total length)))*n = 2n sum of all length, then I did not change the way I calculated what I need to subtract subtract.

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My first time solving every problem before editorial))))

»
12 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

So, it means that the points that the robot visits can be represented as follows: for an integer k such that l≤k≤r, perform all commands from 1 to r, except for the commands from l to k

Could someone explain this part of the tutorial for D please?

For example if a take k = l, the this means that I'll make all the commands from 1 to l-1 and then from l+1 to r? I don´t get it :'(

  • »
    »
    12 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    It means you can check the path for the commands from 1 to l-1 and then from r to the end.

    Notice that when you flip the instructions from l to r, the path from 1 to l-1 is unaffected (because nothing has changed for those parts).

    Now notice that when you flip the instructions, you are just changing the order of instructions, the instructions that are carried out are still the same (in other words, if there are 5U and 5L before flipping, there will still be 5U and 5L after flipping, the order is just different).

    Let us take the change in coordinates caused by flipped instructions as {dx, dy}.

    Notice that dx = number of r — number of l, and dy = number of u — number of d. Since the number of instructions for each direction remains unchanged, we can conclude that dx and dy remains the same.

    All this means is that before flipping, we start at the same place, and after flipping, we end at the same place as compared to our original path. Since there are no changes to the instructions after flipping, we can also conclude that the path before and after flipping is the same.

    Hence, we can check the original path for 1 to l-1 and r to the end, then check the reversed path (with some simple math) from l to r.

    • »
      »
      »
      12 месяцев назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      Thank you ArtemiszenN!! Actually it was not the answer I was lookinfor but you made me notice something important to understand what I was asking and that is the instructions remain the same just in other order.

      Literally I couldn't notice that when taking k and process instructions from 1 to l-1 and then from k+1 to r leads to the same coordinate when processing instructions from 1 to l-1 and then the first k instructions in the flipped string.

      Thank you ^-^

»
12 месяцев назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

The solution of problem F in $$$O(n\log^2 V)$$$ is awesome! I just came up with a simple $$$O(n\log^3 V)$$$ solution:

Through the definition of XOR base (mentioned in the official tutorial) we can conclude that for two integer set $$$A$$$ and $$$B$$$, $$$X(A\cup B) = X(X(A)\cup X(B))$$$, where $$$X(S)$$$ means the XOR base of an integer set $$$S$$$. Through, we can merge two XOR base in $$$O(\log^2 V)$$$ time: Simply insert all element of $$$X(A)$$$ and $$$X(B)$$$ into the resulting XOR base.

Therefore, using binary lifting algorithm on tree just like solving LCA, we get an $$$O[(n + q)\log^3 V]$$$ solution.

Usually the $$$O[(n + q)\log^3 V]$$$ complexity with no optimization can't pass all tests (TLE on test [70, 93]). So here's a trick to improve your constant factor: When adding integers into a XOR base $$$B$$$, if $$$B$$$ has exactly $$$20$$$ element, then do noting, because it will not change any element of $$$B$$$. Hope this will help you.

Here is an example: (C++)

XOR Base Example
»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Video Editorial For problem A,B,C. Link :- Click Here

»
12 месяцев назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

Can B be solved with just mathematical expressions, without binary search?

I tried finding an expression for minimum number of working days, but it gave me wrong answer. I am unable to figure out what went wrong. Can someone please point out my mistake?

My approach was to find the number of days on which (1 lesson + 2 tasks) can be done, and total number of points that can be gained from such days. Let's call such days as tripleTaskDays.

If the points possible to be gained from tripleTaskDays are less than P, we need extra (1 lesson) days to reach P. Otherwise, if tripleTaskDays are sufficient to obtain P, we can just find the number of such days required to obtain P.

The number of tripleTaskDays will be ((n-8)/14) + 1. Because, on first 8 days we get 2 tasks, and then for every next 14 days we get 2 tasks. The +1 at the end is for the first 8 days. The points that can be obtained from such days is thus (((n-8)/14) + 1)*(l+t+t). Lets call this tripleTaskDaysPoints.

If this is less than P, we need to add extra (1 lesson) days. The remaining points are P-tripleTaskDaysPoints. This can be obtained in (remPoints/l) + (remPoints%l == 0 ? 0 : 1) days with (1 lesson) each.

If this is greater than P, we need (P/(l+t+t)) + ((P%(l+t+t)) == 0 ? 0 : 1) tripleTaskDays to obtain P, and that is the answer.

What is wrong with this approach?

Code

(P.S.: It passed the sample test cases. Failed on 883rd test case, which I couldn't view...)

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Try removing the = in P >= tripleTaskDaysPoints

    (If it is equal then you already satisfied the problem)

    • »
      »
      »
      12 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks for the suggestion. Tried it. Still failing on the same test case with WA. The = case is handled equally well by both the if as well as else block. But there is something else, maybe some edge case, that I am still missing ...

      Still WA in 883rd test case of 2nd test input.

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ok, I got the problem. I was missing out the days on which (1 lesson + 1 task) could be done. Such days are possible and have to be considered if number (n-8)%14 >= 7, that is, there are more than 7 but less than 14 days left after a tripleTaskDay.

    So, there are 3 types of days to be considered:

    • tripleDay => (1 lesson + 2 tasks)
    • doubleDay => (1 lesson + 1 task)
    • singleDay => (1 lesson)

    We need to keep picking the best option and obtaining points until P is achieved.

    Here's my accepted mathematical solution without binary search, in O(1) time (with explanation in comments):

    https://mirror.codeforces.com/contest/1902/submission/236004732

»
12 месяцев назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

For B i submitted the following code and the verdict i got was wrong answer on test 3, now when i submit the same code it got accepted, wtf is this scam codeforces??

ll n, l, t;
ll P;
cin >> n >> P >> l >> t;
ll tasks = (n % 7 == 0) ? n / 7 : n / 7 + 1;
ll tmp = tasks / 2;
ll rem_task = tasks % 2;
ll days = 0;

long long sum = t * 2 + l;
ll rem = (P % sum == 0) ? P / sum : P / sum + 1;
// cout << rem << " ";
rem = min(tmp, rem);
// cout << rem << " ";
days += rem;
P -= rem * sum;

if (P > 0 && rem_task) {
    P -= l;
    P -= t;
    days++;
}

if (P > 0) {
    if (P % l == 0)
       days += P / l;
    else
       days += P / l + 1;
}

cout << n - days << "\n";
  • »
    »
    12 месяцев назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    It's not the same code, check the first line of your solve() function, WA with int and AC with long long

    Also multiple lines after that you used ll

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Btw you can solve E using brute force you just have to speed it up using vjudgian theorem

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please explain how do we arrive at $$$2*n \sum_{i=1}^{n} Si - 2* \sum_{i=1}^{n} \sum_{i=1}^{n} LCP(Si', Sj)$$$.

I wanna know specifically how do we get $$$2*n \sum_{i=1}^{n} si$$$. Thankyou!

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Oh I get it each string occurs $$$2*n$$$ times, once on it's own pairs, and once paired with others.

»
12 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Problem C: Can someone please help me out to understand the limitation of using int[] compared to long long[] for storing all the values in an array.

using long long: https://mirror.codeforces.com/contest/1902/submission/235786184

using int: https://mirror.codeforces.com/contest/1902/submission/235786137

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    did u find it? I've the same issue.

    AC with long long -> link

    WA with int -> link

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    ans += (a[n-1] — (a[idx] — diff))/diff;

    diff can be 2e9

    Hack:

    1
    2
    1000000000 -1000000000
    
    • »
      »
      »
      11 месяцев назад, # ^ |
      Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

      can u please help me to figure out where is my code failing for problem C 236330734 upd : I debugged it on my own..bug is that i m not considering that An+1 can be negative Morover I found out a better approach to this problem -> that An+1 is always the least value of (max_element — hcf) ..so in this approach u don't have to worry about when to take An+1 positive and when to take An+1 negative/0

      submission : 236334475 (u can speed up the o(n) loop with binary search the req An+1 element

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks a lot it, I completely missed it.

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have read the problem D solution but i still don't understand it too much. Can someone explain me about this, because when i read it, i see that the solution only check all the point that are visited by using the given string s, doesn't it ? Thank you so much

»
12 месяцев назад, # |
Rev. 4   Проголосовать: нравится -8 Проголосовать: не нравится

Can someone help with problem E ?

https://mirror.codeforces.com/contest/1902/submission/236106356

I don't see what's the problem really

Code is easy to read if you've read the solution

I've found the problem, nvm

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

F=https://www.luogu.com.cn/problem/P3292

and @hanghang007 solved in log^5 /cf

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For D. I was thinking of a modified version of binary search on the string (landing on mid-point, and then deciding whether the left half or the right half can land me on the target point) — by this, I can answer each query in $$$O(log n)$$$ time. (reversing of string is trivial)

Can this approach work?

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thank you for the awesome problem E!

And could these following lines in the solution of E

    res = 0;
    solve(n, v);
    for(int i = 0; i < n; ++i)
        reverse(v[i].end(), v[i].end());
    solve(n, v);
    cout << res << endl;

just be simplified to these ones?

    res = 0;
    solve(n, v);
    cout << 2LL * res << endl;
  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I just did the same. I don't see the need of the extra lines of code sincerely :b

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to appreciate the beauty of Problem B?

Binary search on monotonically increasing/decreasing function F

Link to my tweet explaining the solution as well as diagram to approach this problem with source code

My submission : 236069749

Thank you so much

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

236268959 I am getting MLE in test case 7. But I have used trie as mentioned in the solution. Should I implement trie in some different way?

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can someone give me counter test case where my code getting failed on problem C 236293291

»
11 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

why does an $$$O(n \ log \ n)$$$ hash based solution for E TLE :/ slow modulo?

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have problem that a lgm can't answer,and if someone is able to, everyone will admire him and he will be legend

problem
»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How do we merge the XOR of two different nodes? What about the possibilities of XOR generated by nodes that appear before the LCA but are not part of the simple path between the two nodes? How is this taken care of during the merging process?

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For D, i suppose offline queries ( sorted by r) method would be more easier. Then no need of binary search also. submission

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The E problem hacks my Hash. I get a little angry! Can we do it without using Trie?

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone please help me in identifying the mistake in the code? My logic is correct but I am not able to identify a case where it is giving a zero answer.

Submission

»
10 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

My code for problem D is giving tle at test 41. Here is the code https://mirror.codeforces.com/contest/1902/submission/241087945 Can anyone suggest any optimization that can be done here. Thanks

»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I tried to solve problem E using Trie, but it repeatedly gives Memory Limit Exceeded on test case 16. I don't see any mistake in the construction of the Trie and looks like it used O(S*26) memory. Any sort of discussion will help a lot. This is the submission link : https://mirror.codeforces.com/contest/1902/submission/244942580

»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Reverse the operation sequence, and the new path is equivalent to the original path being symmetrical about the midpoint of the starting and ending line.

»
9 месяцев назад, # |
Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

nice

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

could anyone tell me why i am getting tle on test case 41? my solution is of o(nlogn) {if i am not wrong} . and by seeing constraints it should pass the testcases?. anyone?

sumbission link :- https://mirror.codeforces.com/contest/1902/submission/256209886

»
4 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Plz help with this submission for problem E, couldn't find any reason for a runtime error. It passes all small test cases. Integer overflow is taken care of.

https://mirror.codeforces.com/contest/1902/submission/287423396