Educational Codeforces Round 159 [Rated for Div. 2]
By awoo, history, 13 months ago, translation, In English

Hello Codeforces!

On Dec/03/2023 17:35 (Moscow time) Educational Codeforces Round 159 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Maksim Neon Mescheryakov, Roman Roms Glazov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: Editorial is out

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

Comments Comments (227)
| Write comment?
»
13 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
13 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Hope to get back to expert after this round! GL everyone :)

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope that it'll be an amazing contest!

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the rating distribution for problems

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No score distribution for icpc style rounds

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone and have fun ^_^

→ Reply
»
13 months ago, # |
  Vote: I like it -32 Vote: I do not like it

Educational Rounds are Mathforces af. Gonna skip this one

→ Reply
»
13 months ago, # |
  Vote: I like it +25 Vote: I do not like it

→ Reply
»
13 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Inshaallah, In this round I will be Green.

→ Reply
»
13 months ago, # |
← Rev. 3   Vote: I like it +2 Vote: I do not like it

→ Reply
»
13 months ago, # |
  Vote: I like it +38 Vote: I do not like it

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

After 127 contests and I'm still a NEWBIE gonna set a world record :(

→ Reply
»
13 months ago, # |
  Vote: I like it -15 Vote: I do not like it

D >> C

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    But E < D imo, so always be sure to read at least one more problem than the one you're stuck on.

    → Reply
»
13 months ago, # |
  Vote: I like it -18 Vote: I do not like it

Speedforces

→ Reply
»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anyone show me the formula to solve the problem B please? For me problem C is easier :D

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can do binary search instead of coming up a formula directly :D

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I can't see the idea to do binary search. Can you help me?

      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        you can binary search the minimum amount of days that Monocarp cannot rest, let's say $$$mid$$$ days, then Monocarp can earn $$$mid*l+\min(2*mid,c)*t$$$ points, where $$$c=\lfloor (n+6)/7 \rfloor$$$ is the number of tasks unlocked within $$$n$$$ days.

        → Reply
        • »
          »
          »
          »
          »
          13 months ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          I think it should be c = [(mid+6)/7] (correct me if I'm wrong)

          → Reply
          • »
            »
            »
            »
            »
            »
            13 months ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            It has to be with $$$n$$$, because maximum number of tasks that you can do is always the same and equals to $$$⌊(n+6)/7⌋$$$.

            → Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    this is my submission, i used math not binary search.

    https://codeforces.net/contest/1902/submission/235665532

    → Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem D is difficult to implement.

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +26 Vote: I do not like it

Problem F is first known as "[SCOI2016] 幸运数字", a problem from 7 years ago

→ Reply
»
13 months ago, # |
  Vote: I like it +10 Vote: I do not like it

For F, why using xor basis gives me WA on test 54?

https://codeforces.net/contest/1902/submission/235578100

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Your code gives WA on 

    2
1 2
1 2
1   
1 1 1

    because in your dfs function, you say if you are the root node, don't initialize xor basis.

    → Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +63 Vote: I do not like it

I might have just clutched problem D

Great success?
→ Reply
»
13 months ago, # |
  Vote: I like it -17 Vote: I do not like it

D >> E,F

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

4 submissions on B :)

Also E < D.

→ Reply
»
13 months ago, # |
  Vote: I like it +9 Vote: I do not like it

If anyone solved E using string hashing, drop the solution here

→ Reply
»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it

:( +1 penalty in C because the constraint 'x is a positive integer' got updated after I opened the link. Also, no idea why directly solving the inequality in B gives WA but a binary search approach passes.

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    When solving the inequality, did you consider the case where the number of unlocked tasks is odd?

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Doesn't floor() take care of parity issues?

      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        Opposite actually, because you need one more day to complete the leftover task. I did calculations, not bisearch.

        → Reply
»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Cluthed D with 2 mins left !!

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

me getting +3 on B but 0 on C didn't include a '()' if you see my submission :(

→ Reply
»
13 months ago, # |
  Vote: I like it +30 Vote: I do not like it

Why E with such tight constraints on ML with trie, was it not intended? Saw many hashing solutions passing instead, made me sad ;(

→ Reply
»
13 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Failed D just because I forgot to check whether set.lower_bound(l) was equal to set.end(). Submitted the moment submissions opened and got AC. Good thing it was "out of competition".

→ Reply
»
13 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Looking into my time spent to solve each problem, the most difficult one from A to E was problem B.

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

First time solved F during contest and finished debugging E 1 sec after contest was over.

→ Reply
»
13 months ago, # |
  Vote: I like it -10 Vote: I do not like it

I fucking missed $$$D$$$ just by a few seconds , bro!!!

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Whats the idea behind E?

→ Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    I built a trie of all strings where each node further keeps track of the number of strings in the subtrie, as well as the total length of the strings in the subtrie while excluding the common prefix that the node represents.

    Then for each string, I read the characters in reverse-order and traverse the trie, with each step denoting a collapse step, while carefully accumulating the contributions to the desired sum of the other branches (concatenation cases) by utilizing the stored values.

    My submission: 235592382 I used a 2D array for the trie, which was probably a terrible idea (almost broke the memory limit), but the logic should be sound. I can elaborate on the details further if you want.

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think problem D should give more time, I am sure I use a right O(nlogn) algorithm and implement it in python， however it's always show "tle". 2000ms is too short for D!

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it is simple to solve D in < 500ms if you use cpp

    → Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    pypy isn't always faster than python. you can sometimes switch from pypy to regular python and won't tle

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Damn, you passed tests even without fast IO. I had to use cpp

      → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please why is my submission for F WA on test 9

My thought is divide and conquer with XOR-basis with $$$q\log^2A$$$ complexity

code for F

thanks very much!!

→ Reply
»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Am I the only fool who spent 1 hour and a half to figure out the solution for C while solved E in merely 15 minutes...

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I'm the fool who couldn't solve E in 1 hour 40 minutes yet solved C in the first 11 minutes.

    → Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem D, does the reversed commands range represent the same path, but mirrored around some line parallel to y = x?

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Nope. Well, it might always be mirrored around some line, but that line definitely isn't necessarily parallel to y = x. For example, if you keep going up, then reversing does nothing, and your mirror line is a vertical line, and similarly, going right only yields a horizontal mirror line.

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think it should be mirrored around some dot, but I don't think that's somehow necessary for solution

      → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hmmm... Is it the line from the start of path to its end? If so, we can always just find it and mirror given point to check if it is within given range.

      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Nope, that's not it either. For example, if you move in a square wave, e.g., URDRURDRURDR..., the mirror line is a vertical line in the middle, which doesn't contain the start or the end.

        If there is some geometry-based solution to solve this problem, it would likely be much harder than simply precomputing the forward and reverse paths separately (which is likely the intended approach), so I wouldn't recommend thinking too hard about these geometric properties.

        → Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nope

    → Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I might be wrong with that thinking, but my base idea is that after flipping, the prefix and suffix of points remains unchanged. If so, we can somehow transform given point and check if it is within prefix, suffix, and given range.

    → Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You're on the right track. Let $$$p_i$$$ be the point we're on before executing the $$$i^{th}$$$ command. Now to reverse a segment $$$[l, r]$$$ of the path, shift the origin to $$$p_{r+1}$$$ and mirror all the points on this segment around $$$x=-y$$$, (the transform is $$$(x,y)\to(-x,-y)$$$). Then, shift the origin to $$$p_l$$$. If we treat the points as vectors, then the point before the $$$i^{th}$$$ command after mirroring (assuming $$$i$$$ is in the segment) is $$$p'_i = -(p_i - p_{r+1}) + p_l = p_l+p_{r+1}-p_i$$$

    Why does this work? If the last command in the segment was R, then the second last point would be to the left of the ending point, so mirroring about the ending point will make the second point of the new segment to the right, which is what we want. Similarly this can be shown for any position and command on the segment. Finally we need to start at the original segment's starting point, so we shift our new points to have $$$p_l$$$ as the origin.

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But isn't it O(r-l) for every query?

      I thought we need to transform the point in query so that it would be possible to check it on straight path stored in set.

      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I made it $$$O(\log n)$$$ per query by using a map that counted the number of times I visited each point. For a query x y l r: - If I visit x y before the $$$l^{th}$$$ command or after the $$$r^{th}$$$ command, then I visit that point after reversing the subarray - Between the $$$l^{th}$$$ and the $$$r^{th}$$$ command, I check if I visit the point $$$(x_l + x_{r+1} - x, y_l + y_{r+1} - y)$$$.

        To do this I sorted all the queries by l, and then updated counts of x y outside each segment and the transformed point inside the segment by using something similar to a sweep line method.

        → Reply
        • »
          »
          »
          »
          »
          13 months ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          Yes, you are right. Simple set of points without visit time is not enough.

          But two simple sets are enough :) One to track from beginning and one to track from the end. I'll check this idea.

          upd: seems like even two sets without proper command times are not enough

          → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Damn, it's so sad I couldn't solve C in time, it was really easy

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will Hashing Not Work in E, I was getting WA on test-5 :(

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D without Mo's ?

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Pre-calculate times when you visit each position when moving forwards and backwards, plus some prefix sums to calculate the x and y offsets, then you're done!

    Basically this, I have been heavily commenting my solution during the contest 235604170

    → Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 4   Vote: I like it +4 Vote: I do not like it

    After reversing, suppose :

    x = s1 + s2 + s3...sl-1 + sr + sr-1 + sr-2.. s(r-z+1)

    => x = prefix_horizontal[l-1] + prefix_horizontal[r]-prefix_horizontal[r-z]

    => prefix_horizontal[r-z] = prefix_horizontal[l-1] + prefix_horizontal[r] — x

    Similarly, prefix_vertical[r-z] = prefix_vertical[l-1] + prefix_vertical[r] — y

    hence there's an index l-1<=z<=r such that,

    prefix_horizontal[r-z] = prefix_horizontal[l-1] + prefix_horizontal[r] — x

    prefix_vertical[r-z] = prefix_vertical[l-1] + prefix_vertical[r] — y

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How do you check in D whether you reach the point during the reversed section? I just guessed.

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you are choosing it inside the reversed part a[l,...,r]. Then it is choosing a[1..l-1] and a prefix from reversed(a[l...r]) which is suffix from a[l...r]

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My screencast of solving A-F
I'm planning to discuss my solutions (~2 hrs from contest end time)

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell what is causing runtime error in my solution? 235592760

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    gcd should not be equal to 0 initlize it with A[1] — A[0]

    → Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    If n = 1, then You are returning without reading the array.So, there will be misinput.

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

abs() dont accept long long in c++ are there any workaround other than to manually calculate it? I got WA in Problem C because of this.

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

guys i want your help in identifying problem in my code, https://codeforces.net/contest/1902/submission/235602795 this is my solution for C, i first calculate the gcd of consecutive elements and then select a(n+1) by binary search,

i am getting runtime error on test case 2 with exit code 3 particularly on

16

9 -10 -7 4 -8 10 -5 -1 -9 8 3 -2 2 5 0 -6

the thing is when i run my code on my computer i get the correct answer, i have tried almost everything but can't figure out the problem

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    read this comment

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      that abs() one? i don't think thats an issue, i tried with llabs it still gives runtime error, i think there's some fault in the judge

      → Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    When $$$n == 1$$$, your function returns without actually reading the array value, so the program would mistakenly treat this array value as the array length for the next test case.

    → Reply
»
13 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Can anyone tell why this code gives TLE?

https://codeforces.net/contest/1902/submission/235611299

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For B. Getting Points, although a mathematical formula exists, you can use Binary Search for ease of implementation.

The total tasks created will always be $$$(n + 6)/7$$$.

Suppose you take $$$r$$$ rest days. Notice that it's always optimal to take the first $$$r$$$ days off (so that you never run out of tasks). Since there are $$$(n - r)$$$ working days, and each day you can do at most 2 tasks, the points gained is $$$min(n + 6/7, 2*(n - r))$$$. The points gained via lessons is of course $$$(n - r)*l$$$.

Submission

→ Reply
»
13 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone share a typical case where C can fail?

→ Reply
»
13 months ago, # |
  Vote: I like it +14 Vote: I do not like it

This educational round was really educative, enjoyed it a lot :)

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Don't understand why to use binary search in B.

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    you don't have to use BS. But fixing the days makes the math easier to not mess up. It introduces new errors that may be caused by binary search, though. In my opinion, its about preference.

    → Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

Hope to become Master tomorrow, first time solved all problems in a contest.

I solved today F in O(n log^3 n) and O(n log^2 n), but the solutions are running in almost the same execution time.

Upd: My O(n log^2 n) solution dropped from 3200 ms to 700 ms after I used vector::reserve in N vectors of size at most 20

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contest/1902/submission/235605516 could someone tell me, why am i getting TLE here? It should work in O(nlogn) which should easily pass for 1e6, right?

→ Reply
»
13 months ago, # |
  Vote: I like it -30 Vote: I do not like it

Bad problemset. Couldn't solve one

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    really cannot believe you are blaming contest for your bad level you have never solved a single problem in any of your contests and you are still nagging

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I misread problem C and ended up giving up :< I hope I wont be kicked off Expert

→ Reply
»
13 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Solved E for the first time in a Div.2 contest. Used Trie Here is the code

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody give me some problems that are similar to B, please? I feel uneasy when I encounter such a problem.

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    just solve randomly rather than looking for problems similar to some particular problem

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What knowledge do D & E require?

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone give an example on how my code failed ?! I can't imagine the test case .

[submission:Hacked C Solution ]

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Don't use unordered_set , because it is achieve by hash ,someone will construct data to make tons of hash cross , then you will get TLE

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Would it pass if gave the unordered_set big initial size ? Or it's necessary to use map<int, bool>?

      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You need to use a custom hash for unordered_set (I'm not sure how hackable it is though). You can use normal set it's only logn

        → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You need map but not unordered_map,unordered_xxx is useless

        → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        read ths blog. For example, I have a custom_hash in my library in case I want to use unordered_map/unordered_set. https://codeforces.net/blog/entry/62393

        → Reply
        • »
          »
          »
          »
          »
          13 months ago, # ^ |
          ← Rev. 3   Vote: I like it +8 Vote: I do not like it

          Thank you, who hacked my code sent the mentioned blog after hacking phase :)

          → Reply
»
13 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I feel that isn't it impolite to write hash cross code to someone else

→ Reply
»
13 months ago, # |
  Vote: I like it +5 Vote: I do not like it

My Nlog^2N solution for D

  1. Think in terms of displacements on the X and Y axis.
  2. For a query L,R — (x,y) either lies in the prefix, the suffix or the middle region.
  3. Traverse the string forward and note down the points/cell reached at ith index for each i.
  4. Build a segment tree(each node contains a vector of pair representing all displacements that are achieved via this path) over this forward cells array and then to check if (x,y) is reached either in prefix or suffix: query the tree from (1,L-1) and (R+1,N) for (x,y)
  5. To check in mid region: build a segment over reversed array. Now you need to query if at any point in reversed section you can achieve the required displacement.
  6. Required displacement: since you have already moved prefix(L-1) so required displacement is Target — prefix(L-1).
  7. Reversed section starts from N-R+1 and ends at N-L+1. The origin here is already displaced by reversed(N-R). So account for that.
  8. Query the reversed segment tree for required displacement.

Submission link: https://codeforces.net/contest/1902/submission/235635773

Segment tree library used: https://youtu.be/K-86mKNAsmU?si=bI_IBJVNU50Mjysf

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give me some tips for the hell C? I'm totally confused by it

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    GCD is the key to success

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Probably you are right.But I wonder who all the elements turn to in the end?

      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        the current biggest or the newest element which is bigger than the current biggest

        → Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

i'm wrong

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone please explain how to do C? How to apply GCD there ?

→ Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    recall that all the numbers are unique.. also, as x is +ve you cannot decrease any number by adding x to it.

    now, we need to reach a common number that can be achieved by adding x multiple(or zero) times to all the numbers. Also, assume that a is sorted initially, so we are willing to achieve:

    a[0]+C1.x, a[1]+C2*x, .... , a[n-1]+Cn*x which makes a[0]+C1.x = a[1]+C2*x = ..... = a[n-1]+Cn*x

    so what you can see here is that we need to maximize x, also, greedily we can see that best choice for that final number as of now would be a[n-1], so we see that for any i, a[n-1]-a[i] will be some Ci*x, so take gcd of all such terms and find x.

    then the probem remains to find optimal the An (try it yourself, if you cant I can help there).

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Hi akshat,

      Initially how i thought was, the best option to make array equal is making the array elements equal to the max element present in array.

      So what i did is found the max in array, for ex : a[] = [1 -19 17 -3 -15], max = 17; as the difference among (max — a[i]) should be multiple of x, so i thought x will be in range x -->[1,16], For which ever x is possible i have collected minimum answer(traversed whole array to check x is possible or not, which ever x is possible collected max-a[i]/x)may be here i can use GCD to find x right ?.

      I think u are also saying to make array equal to max right ?

      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes the idea is same as mine. You can look at my code for any clarifications :)

        → Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    You're adding same x to all elements, if difference between them is not multiple of x they'll never become equal.

    → Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Why does my nlogn solution timeout for D? submission — 235579778

Update — So many other nlogn solution also getting TimeLimitExceeded , any explanation?

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's wrong with my solution 235568240 for C ? Please help me where it is leading to TLE

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    unordered_map leads to O(n^2)

    → Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    By the way, for your check perfect square function you can instead just use __builtin_popcount which returns the number of bits and check if that is equal to one.

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      huh ?? That's wrong ...

      1000 = 8 is not a perfect square 1001 = 9 is a perfect square

      We can just check if a number is a power of 2 from no of set bits = 1

      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        oh I'm dumb. I thought it checked powers of 2 not perfect squares because I was just working on another problem and that was in my head.

        → Reply
»
13 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Why so late Editorial?

→ Reply
»
13 months ago, # |
  Vote: I like it +16 Vote: I do not like it

F can be done in O(n*lognlogA + q*logAlogA) with centroid decomposition. while decomposing the tree, just solve all the queries whose path includes the current centroid. We can do this by rooting the current subtree in the current centroid and calculate the xor base for every path from a centroid to a node in the current subtree(O(nlognlogA) in total) and then we can answer a query in O(logAlogA) by just merging 2 xor bases.

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hey, can you explain your decomposition part a bit?

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Lets say that you are currently solving your problem for a set of nodes S and a set of queries Q. When solving for S and Q, if you find a centroid C in the tree that is consisted of nodes in S, then every query from Q will either contain C, or not contain C. Those who contain C we will solve by precalculating xor bases for every path C->X, where X is in S, and then to answer a query (X,Y,K) we can merge the 2 paths that we precalculated C->X and C->Y and get the answer to our query. Now we decompose the tree into new trees, every query in Q that didnt contain C will now belong completely to some of the new trees. So that means that now we have new subproblems (S1,Q1),(S2,Q2).... which we can solve recursively.

      → Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

my $$$O((n + q) \cdot log_2n \cdot (log_2a_i)^2)$$$ solution on problem F using binary lifting and xor-basis passed during the contest but got TLE on test case 90 on system tests. and an optimized one passed with time complexity $$$O((n \cdot log_2n + q) \cdot (log_2a_i)^2)$$$ after the contest. Is there any solution with better time complexity, like for example $$$O((n + q) \cdot log_2n \cdot log_2a_i)$$$?

UPD: stefanbalaz2 just posted one 2 minutes ago. ty and what a coincidence.

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I have other solution too, using LCA binary lift. submission

    Idea: For each node from root you can mantain the height where a new number is added to the xor-basis and the number added, when you are building the base in a child, you need to try do add only numbers added in the parent, thus at most 20 numbers will be added and at most 20 operations will be needed to know if a number will be added or not. for queries, I need to get the height of lca and add all numbers from basis of the nodes u and v up to the height.

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      oh, I got it, thank you, and your solution is easier to code for me.

      → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, can anyone tell me how to hack "String hashing" solutions, just give a link to an article.

→ Reply
»
13 months ago, # |
  Vote: I like it +6 Vote: I do not like it

unrated？

→ Reply
»
13 months ago, # |
  Vote: I like it +26 Vote: I do not like it

When will rating be updated?

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

@awoo@BledDest Thank you very much for the contest. Could we please get the editorials and ratings change — many thanks!

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Most contests are rated within minutes of system checks completion. This one had hacking session finished over 15 hours back and still not rated.

    → Reply
»
13 months ago, # |
  Vote: I like it +1 Vote: I do not like it

why this contest do not affect to rating's ?

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Oh my stupid me... In problem C, I assumed we must choose A[n+1] > 0, then got confused why it wouldn't work :(

→ Reply
»
13 months ago, # |
  Vote: I like it +5 Vote: I do not like it

after how much time does the rating changes come for educational rounds?

→ Reply
»
13 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I'm sorry but when rating changes ????

→ Reply
»
13 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Can you guys tell me if my ratings could go up? 1902C - Insert and Equalize

Click here to see my blogs

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E, I used string hash and chose modulus 131, got AC during the contest but got WA on test 24 after contest. I tried 135, WA again on test 98. Finally I chose modulus 29123 and got AC. Could anyone tell me how to avoid such situation ?

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Always use double hashing

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I used double hashing. Double hashing can be wrong if choosing unlucky modulus.

      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        131, 137 is common module for hashing so tester use some test case where your code will get WA . So use those prime module that is not common. Obviously not use 135 as a module cz that not a prime.

        → Reply
        • »
          »
          »
          »
          »
          13 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks. I think I refer to some code template which is not so good.

          → Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    here is my wrong submission 235733205 and right submission 235733378

    → Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I understand now, 131 is not mod number, it is base number and should be prime.

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Base not necessary is a prime, I use base number randomed in range $$$[0, MOD)$$$

      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That is a good choice.

        → Reply
»
13 months ago, # |
  Vote: I like it +20 Vote: I do not like it

ratings please..

→ Reply
»
13 months ago, # |
  Vote: I like it +17 Vote: I do not like it

When will the ratings change

→ Reply
»
13 months ago, # |
  Vote: I like it +11 Vote: I do not like it

ratings?

→ Reply
»
13 months ago, # |
  Vote: I like it +23 Vote: I do not like it

Go everyone "WHERE IS RATING!!!"

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

→ Reply
»
13 months ago, # |
  Vote: I like it +12 Vote: I do not like it

If you want to decrease my rating, do it quick :(

→ Reply
»
13 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Any ideas why is the contest showing up as unrated for me?

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why unrated?

→ Reply
»
13 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Where are ratings???

MikeMirzayanov
awoo
BledDest

→ Reply
»
13 months ago, # |
  Vote: I like it +5 Vote: I do not like it

No rating update?

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

Regarding the mail -> Your solution 235540146 for the problem 1902A significantly coincides with solutions agrahariprajjawal5/235540146, iit2022164/235540396. Such a coincidence is a clear rules violation.

This has happened because of the use of a common source published before the competition. It happened because of the same template I and the other fellow user use. The template is taken from some internet source which I don't exactly remember. Unfortunately, the code inside the solve function also matched which is a mere coincidence. It's not strange that such small piece of code get matched. So, this is a mere coincidence and please revoke the submissions of mine done during the contest. I agree on providing more clarification regarding this.

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

guys after the rating recalculations this contest was marked unrated for me while I'm still a newbie and haven't gone to 2100 to make it unrated why?

→ Reply