pashka's blog

Codeforces Round 927 (Div. 3)
By pashka, history, 2 years ago, In English

Hello! On Feb/18/2024 15:05 (Moscow time) will start Codeforces Round 927 (Div. 3), the next Codeforces round for the third division.

The round is based on problems from JetBrains Academy Youth Challenge. If you participated in it, please don't participate in this round.

Problems for this round are prepared by denk, step_by_step, goncharovmike, ikrpprppp, pashka, Vladosiya and MikeMirzayanov.

Thank you very much awoo, BledDest, buyolitsez, EgorUlin, Gojova, GrandFruit, Hello_zoka, petyb, scanhex, ibraevdmitriy, shnirelman, SomethingNew, Toy_mouse, Zandler for testing the round.

As usual for the third division rounds:

  • there will be 6-8 tasks in a round
  • round duration is 2 hours 15 minutes
  • the round follows the ICPC rules, penalty for an incorrect submission is 10 minutes
  • round is rated for participants with ratings up to 1600
  • after the round there will be a 12-hour open hacking phase

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behaviour. To qualify as a trusted participant of the third division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them)
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Good luck to all!

UPD: Editorial

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

Comments Comments (219)
| Write comment?
»
2 years ago, hide # |
← Rev. 6  
Vote: I like it +3 Vote: I do not like it 
 █████  ██      ██          ████████ ██   ██ ███████     ██████  ███████ ███████ ████████ 
██   ██ ██      ██             ██    ██   ██ ██          ██   ██ ██      ██         ██    
███████ ██      ██             ██    ███████ █████       ██████  █████   ███████    ██    
██   ██ ██      ██             ██    ██   ██ ██          ██   ██ ██           ██    ██    
██   ██ ███████ ███████        ██    ██   ██ ███████     ██████  ███████ ███████    ██

All The Best (Zoom out if not visible)

→ Reply
»
2 years ago, hide # |
 
Vote: I like it -13 Vote: I do not like it

"The round is based on problems from JetBrains Academy Youth Challenge. If you participated in it, please don't participate in this round." Does this mean if someone participated in that one ,they would have some advantage in this round?(wanted to clarify it)

→ Reply
»
2 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

What is the score distribution?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +15 Vote: I do not like it

Can the timing be changed? It clashes with ARC. Moreover, this time is quite awkward for me, as I have an important appointment at that time.

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it -7 Vote: I do not like it

    Ohh why not sir. Please tell us when you're free and we'll change the timing according to your availability. Thank you.

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Great that u understood. I prefer to have it on regular Cf time so that it doesn't coincide with Atcoder Regular Contest and people like me can go on with their regular Sunday Schedule.

      → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it -8 Vote: I do not like it

    Oh yes lets change the contest date because Six_Seconds has an appointment at that time.

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

Hey boy, are you a semicolon? Because my program is missing you ;)

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

as not a tester i would like to solve this round

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Finally after a tedious global round which took away my *1800 it's time to relax. Hope to solve A-F

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +2 Vote: I do not like it

This comment has been deleted.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Good start time for Chinese.

But I must finish my winter vacation homework!!!F**k

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I have a feeling this round will be amazing.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it -10 Vote: I do not like it

If problems are already based on jetbrains youth academic challenge, then it means people already know the problems. Not just that, we can find them from internet also.

Therefore, let's not participate in this round.

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


→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

problems of this contest are prepared "step_by_step"

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

My 1st unrated Div 3 !(;

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I would target solving >75% problems.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Good start time!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Yesterday i became specialist so i hope to reach expert again.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Please note the unusual start time: 18:05 UTC+6

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

The timing is great, but it overlaps with ARC's timing.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Good lucks for everyone!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Good luck to all of my grey friends :D

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Redemption time

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

extra registration ??

→ Reply
»
2 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it -12 Vote: I do not like it

c Problem is very tough :(

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +34 Vote: I do not like it

tourist speedrun the division 3 in 28 minutes to clinch first position,then started Atcoder regular contest 45 minutes late and still came 3rd(Standings ). GOAT stuff.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

I got PTSD because of Problem C

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

Ugh, I feel so dumb for not being able to figure out C

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +25 Vote: I do not like it

Silent moment for ones who tried so hard for bigint in E

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Was F dp + segment trees?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

when will i can see the editorial ??

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

how to solve the E?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

E and D are just implementation didn't like them that much.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

went good for a first div3 unrated contest

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

How this code not able to pass C ? link anyway i solve it using Segment Tree link

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I can't figure out why this code fails for C: 247057083

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    Maybe a long long overflow when calculating the product at the beginning.

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    Every value of A(i) can go upto 1e4. Now imagine 1e4 values in all the n elements... It will be (1e4)^n and as n can itself go upto 2e5.

    So, (1000)^(20005). Do you think It can be stored?

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    This line is definitely the problem:

    for(int i = 1; i <=n; i++){
    prefArr[i]=prefArr[i-1]*nums[i-1];
}

    Because you could end up with a number as big as $$$10^{8 * 10^{5}}$$$ which just can't fit into a 64 bit integer.

    → Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Nowadays Div 3 is harder than Div 2. I don't know if it is only for me or if other users also feel it. BTW happy coding...........

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

E got TLE with python but in c++ with making bignum get AC.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Problem F was really nice. Thanks authors. :blobheart:

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

problem C was quite pleasure to solve

I felt like being Elegia

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to solve C?

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

Am I the only one who is able to solve C but could not solve any other problem.

what is wrong with me... :(

could anyone tell what is wrong in :

Problem B submission

Problem A submission

EDIT: I found the small bugs in my code both above submissions are incorrect

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    for A i use recursive it's kinda similair to minimum jump problem code

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    For problem A: you will not be able to move further after two consecutive thorns cells. The answer to the problem will be the number of coins up to two consecutive cells with thorns

    → Reply
»
2 years ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

Is G just Dijkstra's but edge weights are computed using some x such that a + bx = c + dx, if the two sides of the equation are 2 different platforms?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Is there a more effective way to do D other than making an if-else chain?

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    backtracking

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I imagine you could create a custom comparator and then sort, correct me if I am wrong.

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I did the following. I keep the sorted values of the cards for each suit. For the non-winning suits, I can just have the cards beat each other in sorted order, taking 2 at a time until I have 0 or 1 left. If I have 1 left, I'll save it for later. Then afterwards I can just take the winning suit, eliminate all of the remaining ones from other suits, and eliminate the rest in the winning suit the same way as before.

      → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Store in map

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

    Sort card for each suit and greedily remove 2 cards at a time, if there is one card left, u need to match it with any trump. At last u do the same thing for the rest of the trump cards.

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    Group each card by suits. Then sort by rank for each suits

    Now for each suit other than the trump, take two adjacent card rank. If there are some excesses, keep it and use the trump to beat them

    Now use the remaining trump suit to battle each other

    The impossible case is only when the excesses are greater than the trump suit

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

    I used this comparator function to sort all the cards

    bool comp(string a, string b) {
    // Both are trump
    if (a[1] == trump && b[1] == trump) {
        return a[0] < b[0];
    }

    // One is trump
    if (a[1] == trump) {
        return false;
    }
    if (b[1] == trump) {
        return true;
    }

    // Both are normal, same suit
    if (a[1] == b[1]) {
        return a[0] < b[0];
    }

    // Both are normal, different suit
    return a[1] < b[1];
}

    Then my logic for the ans is just go from left to right

    • If there are still 2 cards of the same suit -> Choose them
    • If there is only 1 card left of that suit then get a trump card from the back (If I still has trump cards)
    • Otherwise, I can't beat the current card -> This game is impossible
        vector<pair<string, string>> ans;
    int rightIdx = 2 * n - 1;
    bool ok = true;
    for (int i = 0; i + 1 <= rightIdx; i++) {
        if (a[i + 1][1] == a[i][1]) {
            ans.push_back({a[i], a[i + 1]});
            i++;
        }
        else if (a[rightIdx][1] == trump) {
            ans.push_back({a[i], a[rightIdx]});
            rightIdx--;
        }
        else {
            ok = false;
            break;
        }
    }
    → Reply
»
2 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

Spent a long time to understand what problem B wants

You too?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

Ac F at 2:14 i can't believe myself

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

If you need video explanations of C, D, E and F, you can check my video editorials here

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Why long long doesn't work for problem C. Calculating the product in long long then dividing the product by left or right whatever element is deleted?

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

    it's long long overflow, a[i] can be 1e4, and n can be 2e5 imagine array all the elements are 1e4 of length 2e5 so the product all of them is (1e4)^(2e5) that can't fit in long long

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Because there is a test case which $$$n=2\cdot10^5$$$ and all $$$a[i]$$$ are $$$10^4$$$, then it will be $$$10000^{200000}$$$ :)

    → Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

BE CAREFUL OF CARD SIMULATIONS 23min D, 7min E

I did F with linear DP, first finding out bar[x] = which spot is the leftmost viable spot on x's right if x is chosen.

Could someone explain how G works?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can somebody tell me why deque can't solve problem c??? I can't pass test 3.

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it 
    p *= a[i]

    gonna make integer overflow


      if (s[i] == 'L')
            {
                p /= a.front();
                a.pop_front();
            }
            else
            {
                p /= a.back();
                a.pop_back();
            }

    Is not accurate, because you need to use modulo inverse, although I think it is not usable in this problem (because m isn't a prime number sometimes)

    → Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Whats wrong with the naive implementation of problem C?

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

    If you have $$$2\cdot 10^5$$$ elements and all of them are $$$10^4$$$, your product will be $$$(10^4)^{2\cdot 10^5}$$$ so it overflows.

    → Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

D can be solved by using Blossom algorithm, even though it is just an overkill of the problem

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +5 Vote: I do not like it

    Must we use Blossom? I believed the graph wouldn't contain a cycle and is thus bipartite, so I tried to find the matching with max flow. However, I failed on test 3.

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

      I suppose that it can be solved using max_flow algorithms, but max matching is more intuitive, i think

      → Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

why greedy does not work for F? :(

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    how you suppose to do it greedily?

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
      ← Rev. 3  
      Vote: I like it 0 Vote: I do not like it
      1. sort according to the left points
      2. put those intervals into lists of non-overlapping intervals, like this:

      2 4, 5 7, 10 11

      2 6, 7 7

      4 5

      1. in each iteration, I'll increment the answer by the number of overlapping intervals in the first element of the lists (a little bit confusing description :(, those intervals will form a larger interval (called concatenated intervals) and also removes all intervals contained in the concatenated interval. Then remove empty lists.
      2. output the answer
      → Reply
»
2 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

C problem is really hard for Div3 XD.

p.s Who solved this problem without trees? :)

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I'm curious about the segment tree solution, can you explain a little bit?

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

      Very simple problem if you think using segment tree.find my solution here..

      C++ Code
      → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    It’s pretty simple just compute if offline in reverse order. Start from index after n-1 operations. This index is both l and r. in reverse order, if operation is R, append the righter value and increment.

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

      yes very simple if you know how to solve it. not so simple if you dont.

      → Reply
      • »
        »
        »
        »
        2 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        basically the reverse approach is hard to think of but it is not the only one you can use segtree and just recompute again for every range thanks to segtree this will be done in n log n instead of n^2

        → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I solved it with sqrt decomposition

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Start from reverse. Start from one element that is going to be remaining at last, after removing every other. Then keep multiplying second last, third last… while taking modulo. And then print array of answers in reverse

    → Reply
»
2 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

I loved Problem E,Great contest

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

very good D and E problem,makes my rating down down down.

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

Nice contest! Anyway here is my solution for problem F :
Let call cover[i] means the number of segment that cover point i. We can find this by using a multiset.

Iterate from 1 to n. Let's call dp[i] : Consider to position i, what is the maximum answer can we make

  • If we did not choose a point on i : dp[i] = dp[i-1]
  • If we did choose a point on i : dp[i] = dp[j] + cover[i] with condition : i and j does not lied in any same segments.
  • Here's how to find j. For all segments that contain point i, let's call L is the minimum left border of all segments. It's obvious that j = L — 1.

Hope it make sense!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Problems E & F were great! Nice contest! I enjoyed it!

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

Why is this impossible in problem D ?

1
S
7S 3S

Since both belong to trump suit, and 7S has a higher rank, it can beat 3S. ??

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Did anyone use DP to solve E? I usually don't use Python and thus had TLE at case 6. Submission

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

How to solve Problem G?

→ Reply
  • »
    »
    2 years ago, hide # ^ |
    ← Rev. 4  
    Vote: I like it +25 Vote: I do not like it

    Here is my solution:

    For each passages, find the times in which the levels of the connected platforms are the same. To do so, you need to solve the equation:

    $$$\begin{alignat*}{2} && l_u + t \cdot s_u &\equiv l_v + t \cdot s_v \quad&(\text{mod } H)\\ &\implies& t \cdot(s_u - s_v) &\equiv l_v - l_u &(\text{mod } H)\\ &\implies& t \cdot(s_u - s_v) + k \cdot H &\equiv l_v - l_u &\text{for some } k \in \mathbb{Z} \end{alignat*}$$$

    You can solve this equation using the extended Euclidean algorithm. Define $$$C = \frac{l_v - l_u}{\gcd(s_u - s_v, H)}$$$. Note that if $$$t_0$$$ is one solution, then $$$t_0 \pm C$$$ is also a solution.

    So, for each passage, you know you can cross it if and only if $$$t \equiv t_0 \left(\text{mod } C\right)$$$.

    Then, you can solve the rest of the problem using a simple modified Dijkstra algorithm, where when crossing a passage you update the new distance as $$$t_0 + C \cdot max\left(0, \left\lceil\frac{t_0 - curdist}{C}\right\rceil\right) + 1$$$.

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Can you please explain this, we can find t using the extended euclidean algorithm but how will we get the smallest t ?

      → Reply
      • »
        »
        »
        »
        2 years ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it +8 Vote: I do not like it

        If $$$d = gcd(a, b)$$$ and $$$(x_0, y_0)$$$ is a solution to $$$ax + by = d$$$, then the general solution to $$$ax + by = dj$$$ is:

        $$$\left\{\left(x_0j + \frac{b}{d}k, \, y_0j - \frac{a}{d}k\right)\mid k \in \mathbb{Z}\right\}$$$

        Thus, the solution with the smallest value of $$$x$$$ would be $$$\left(x_0j \text{ mod } \frac{b}{d}\right)$$$.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, hide # ^ |
           
          Vote: I like it +5 Vote: I do not like it

          why is it x0j + (b/d)k and not x0j + bk, this will also keep the equation balanced, x0j + bk and y0j — ak

          I am sorry I looked at many resources but no one explains this if you could please explain it

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, hide # ^ |
             
            Vote: I like it +1 Vote: I do not like it

            Honestly, I just memorized that as a fact without giving it much thought. However, if I have to try to justify it, it would go like this:

            If we substitute $$$\left(x_0j + \frac{b}{d}k, \, y_0j - \frac{a}{d}k\right)$$$ in the the equation $$$ax + by = dj$$$, we have:

            $$$ \begin{alignat*}{2} &&a\left(x_0j + \frac{b}{d}k\right) + b\left(y_0j - \frac{a}{d}k\right) &= dj \\ &\iff& ax_0j + \frac{ab}{d}k + by_0j - \frac{ab}{d}k &= dj \\ &\iff& ax_0j + by_0j &= dj \\ \end{alignat*} $$$

            As for why we choose $$$\frac{b}{d}$$$ and $$$\frac{a}{d}$$$, it is becuase they are the smallest integers which can cancel each other out as above.

            For example, note that $$$x_0j + bk$$$ also gives us a set of valid answers. However, they don't give us the full set of answers. More formally:

            $$$\left\{\left(x_0j + bk, \, y_0j - ak\right)\mid k \in \mathbb{Z}\right\} \subseteq \left\{\left(x_0j + \frac{b}{d}k, \, y_0j - \frac{a}{d}k\right)\mid k \in \mathbb{Z}\right\}$$$
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 years ago, hide # ^ |
               
              Vote: I like it +5 Vote: I do not like it

              Thankyou so much,this was just basic LCM calculation,i completely understood this now

              → Reply
»
2 years ago, hide # |
 
Vote: I like it -6 Vote: I do not like it

tourist used dp just to solve a Div3A lol 246990951

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

B getting hacked like potatoes!!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Dunno about you all but this is imo very confusing descrption:

description

Why use words sequentially? Why use "strictly after". If there werre not example input/output I would think that you have to find years p, p+1, p+2, ..., p+n such that first sign happens on p, second sign happens on p+1 and so on.

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

I tried solving C by calculating product of the range left after each operation using sqrt decomposition (247032959). It was giving TLE. Is there something wrong in implementation ? Because a same problem with similar constraints (243011064) got AC. I know it's not a good approach. It could be solved much simply but that's the approach I thought in contest.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Why is B getting hacked?

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

    1000000 1 1000000 1 1000000 1... causes tl for solutions that try to linear search next year every time

    → Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

one of the best div 3s ever

thanks a lot

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

HackForces

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Editorial when?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

MikeMirzayanov I have an optimization for system testing. Instead of testing on whole set of test cases again, test just on new test cases because anyway the submissions which are being tested have passed the pretests. This can potentially speed up system testing.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Getting the system test done is like waiting for a snail to finish a marathon!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

A testcase for A question has been missed in the system testing as well. The case is when the staring point is a goldcoin.Many users dint write the code to cover this edge case.Please look into it.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

Anyone knows when Editorial will be out?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Why does this C++ segment tree for problem C get a TLE? https://mirror.codeforces.com/contest/1932/submission/247091172

The code copied here:

void build(vector<int> a, int v, int tl, int tr, int m, vector<int> &t) {
    int n = a.size();
    if (tl == tr) {
        t[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm, m, t);
        build(a, v*2+1, tm+1, tr, m, t);
        t[v] = (t[v*2] * t[v*2+1]) % m;
        }
}
 
int product(int v, int tl, int tr, int l, int r, const vector<int> &t, int m) {
    if (l > r) 
        return 1;
    if (l == tl && r == tr) {
        return t[v] % m;
    }
    int tm = (tl + tr) / 2;
    return (product(v*2, tl, tm, l, min(r, tm), t, m)
           * product(v*2+1, tm+1, tr, max(l, tm+1), r, t, m)) % m;
}
 
void solve(){
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    string s;
    cin >> s;
 
    vector<int> t(4*n, 1);
    build(a, 1, 0, n-1, m, t);
    int low = 0;
    int high = n-1;
 
    for (auto c : s){
        cout << product(1, 0, n-1, low, high, t, m) << " ";
        if (c == 'L'){
            low++;
        } else {
            high--;
        }
    }
    cout << endl;
}
→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    You should pass vector through pointer in the build function. That is, replace the following:

    void build(vector<int> a, int v, int tl, int tr, int m, vector<int> &t)

    with: 

    void build(vector<int> &a, int v, int tl, int tr, int m, vector<int> &t)
    → Reply
»
2 years ago, hide # |
 
Vote: I like it +17 Vote: I do not like it

when's the editorial come out?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

When is editorial?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

When will the editorial be posted

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

pashka MikeMirzayanov Publish the editorial Bro.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Where can I get solutions of this round??

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

    It haven’t been posted now(though it should have been posted), you can view other’s submission instead.

    → Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hello I think this has been a mistake:

Attention!

Your solution 247092052 for the problem 1932F significantly coincides with solutions Bobsy_is_back/247078909, bdyby10101/247085106, nohellodotcom/247085167, Sahilamin219/247086160, soumyadipdasmahapatra664/247086213, orazalyy/247087989, siddhantbhardwaj234/247088775, lender/247088979, nishkarsh1215/247089048, naked_soul/247091483, 3mk_leader/247091900, _Fer3on_/247092036, bgopc/247092052, orzdevinwangg/247092115, AkshitSharma/247092541, AJ_25/247092808, Ari10/247093633, JOO_91/247095387. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

That contest was unrated for me and I didn't even got in the contest in the start time and I didn't even care? why would I cheat when it's unrated? and the codes aren't even alike like WHAT?? The algorithm looks alike I agree but the code doesn't like why would I even cheat in an unrated contest???

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Sorry !!

    Correct me please, Are you talking about anything I did? that solution you mentioned I am not even aware of the question!!

    if I have misunderstood please let me know, I am sorry for my wrong understanding then!

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Idk, why would you cheat in the unrated contest?

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I haven't that's the reason I'm appealing

      → Reply
      • »
        »
        »
        »
        2 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Dude I asked you why, not if you did it

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          I didn't bro, there doesn't exist a reason for a thing that hasn't happened

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, hide # ^ |
             
            Vote: I like it 0 Vote: I do not like it

            Bro, again, I didn't ask you to explain cause-and-effect relationship, I asked why you'd cheated in the contest

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 years ago, hide # ^ |
               
              Vote: I like it 0 Vote: I do not like it

              I think u're not getting the point I DIDN't CHEAT so I don't have a reason to cheat in an unrated contest

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                2 years ago, hide # ^ |
                 
                Vote: I like it 0 Vote: I do not like it

                So what is your final answer?

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, hide # ^ |
                   
                  Vote: I like it 0 Vote: I do not like it

                  I don't have a reason for something I haven't done

                  end of conversation

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, hide # ^ |
                   
                  Vote: I like it 0 Vote: I do not like it

                  So you cheated because you didn't have a reason to cheat? But that makes no sense!

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, hide # ^ |
                   
                  Vote: I like it 0 Vote: I do not like it

                  sounds like a u problem, end of the conversation

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, hide # ^ |
                   
                  Vote: I like it 0 Vote: I do not like it

                  Well, it wasn't really a conversation since you pretty much ignored my question

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, hide # ^ |
                   
                  Vote: I like it 0 Vote: I do not like it

                  Bro, When I haven't cheated, how can I answer it?

                  U think I cheated and asking me for a reason which I'd be doing the same in this situation, but I actually didn't cheat

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, hide # ^ |
                   
                  Vote: I like it 0 Vote: I do not like it

                  Ok, I'm done now, I was messing with you, for a reason ofc

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, hide # ^ |
                   
                  Vote: I like it 0 Vote: I do not like it

                  If the reason was get me to admit, I don't lie

                  peace

                  → Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

good contest

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

the question E has previously appeared in Atcoder Beginner Contest Question 233 E. Exactly the same

→ Reply