E was awesome. Thanks for great problems

When will you update the rating change for this round?

C was the coolest

Thank for contest! But where is rating?

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

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)|$$$.

F was cute :)

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.

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.

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.

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

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.

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

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 :'(

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++)

struct HamelBasis
{
 
    int tot; ///< the count of elements
    int basis[20];
 
    HamelBasis() : tot(), basis{} { }
 
    void insert(int x)
    {
        // helpful trick
        if (tot == 20) 
            return ;
        for (int i = 19; ~i; i--) 
            if ((x >> i) & 1) {
                if (basis[i]) 
                    x ^= basis[i];
                else {
                    basis[i] = x;
                    ++tot; 
                    break; 
                }
            }
    }
 
    bool check(int x)
    {
        for (int i = 19; ~i; i--) 
            if ((x >> i) & 1) 
                x ^= basis[i];
        return !x;
    }
 
    void merge(HamelBasis &t)
    {
        for (int i = 0; i < 20; i++) 
            if (t.basis[i]) 
                insert(t.basis[i]);
    }
 
};

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?

ll n, P, l, t;
cin >> n >> P >> l >> t;

ll work = 0; // minimum number of days of work required
ll tripleTaskDays = ((n-8)/14) + 1; // no. of days on which (1 lesson + 2 tasks) can be done
ll tripleTaskDaysPoints = tripleTaskDays * (l+t+t); // total points from such days

if(P >= tripleTaskDaysPoints) {
    work = tripleTaskDays;
    // if even after all (1 lesson + 2 tasks) days, more points need to be obtained,
    // they have to be obtained from single lesson days
    ll remPoints = (P - tripleTaskDaysPoints);
    work += (remPoints/l) + (remPoints%l == 0 ? 0 : 1);
} else {
    // if (1 lesson + 2 tasks) days can obtain required points, we just need to find
    // how many such days are required
    work = (P/(l+t+t)) + ((P%(l+t+t)) == 0 ? 0 : 1);
}

cout << (n-work) << nline;

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

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";

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!

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

Alternate solution of problem E: https://mirror.codeforces.com/contest/1902/submission/236207452

Alternate solution of problem E: https://mirror.codeforces.com/contest/1902/submission/236207452

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

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

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

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

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

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.

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

Sorry for necroposting but I found a slightly different solution to D which I think is interesting.

Solve for the 1D case (ie, only X coordinates). This is easily solved with prefix sums if we consider L as -1 and R as +1.

Well, it turns out you can convert the 2D case to the 1D case by considering U as +2e5 and D as -2e5, because the magnitude is large enough not to interfere with the L/R.

Solution