Problem solved

.

For problem C, isn't the upper bound of the answer always n — 2 and not n — 1, since we can always pick two elements to make an AP and then check how many elements we have to change?

could someone explain D in more detail.

can anybody help me pls in "B"problem I have two codes for the problem out of them one is accepted and another is getting TLE . can anybody let me know why this is happening.

link1-TLE: https://codeforces.com/contest/1616/submission/141148880 Link2-AC: https://codeforces.com/contest/1616/submission/141149035

what's wrong with my code ? please help my submission : problem C thanks in advance

Could someone explain 1616F - Tricolor Triangles in a little bit more detail?

Brute force with random can passed...

there are many limitations, and we just choose 1000 of them randomly and it got accepted...

141155530

Can someone tell me is this contest was unrated as I participated and its showing this contest name under unrated and still my rating didn't updated too kindly guide me .

I can't understand why my solution for C didnt pass, its seems i did the thing that was explained in editorial, can someone explain why?

141129320

In problem E, for some reason during the contest I thought it would be very complex to maintain the shifts using a BIT. So here is another way I used to solve this problem without any data structures (albeit with trickier implementation).

Similar to the editorial we realize that the optimal answer will be of the form $$$s_i = t_i$$$ for all $$$i \lt k$$$ and $$$s_k < t_k$$$ for some $$$1 \leq k \leq n$$$.

Let us suppose $$$t_1 = t_2 = \ldots = t_x$$$ and $$$t_x \ne t_{x + 1}$$$. We have two cases for this block:

1. The smaller position $$$k$$$ will be in this block.

   • We want to make $$$s_1 = s_2 = \ldots = s_{y - 1} = t_1$$$ and $$$s_y < t_1$$$ for some $$$y \leq x$$$.
   • For each possible $$$1 \leq y \leq x$$$, we could fix the first $$$y - 1$$$ occurrences of $$$t_1$$$ and then move the first occurrence of a character less than $$$t_1$$$ to $$$y$$$, and take the min over these subcases.
   • However since we need to remove the first $$$y$$$ occurrences of $$$t_1$$$ from $$$s$$$ so we can find the actual distance of the closest character less than $$$t_1$$$ after moving them, we use upto $$$O(n)$$$ time for each $$$y$$$, this could become $$$O(n ^ 2)$$$ overall for a large block, so this wont work.
   • If you write out and compare the equations for various $$$y$$$, we can notice that there is always an optimal $$$y = z$$$. This is just the smallest $$$z \leq x$$$ such that $$$s_z \ne t_1$$$ before we perform any moves. (or $$$x$$$ if there is no such position)
   • So with this optimal $$$y = z$$$, $$$ans = min(ans, cost + (\text{first_smaller} - z))$$$, where $$$cost$$$ is the cost for previous blocks and $$$\text{first_smaller}$$$ is the first index such that $$$s_{\text{first_smaller}} \lt t_1$$$

2. The smaller element will be in a later block.

   • We want to make $$$s_1 = s_2 = \ldots = s_x = t_1$$$.
   • Let the first $$$x$$$ positions of $$$t_1$$$ in $$$s$$$ be $$$pos_1, pos_2, \ldots, pos_x$$$, then the min cost of making it equal is $$$\sum_{i = 1}^{x} {pos_i - i}$$$.
   • Since the first $$$x$$$ characters of $$$s$$$ and $$$t$$$ will be equal after this operation, we can note this is identical to the initial problem but comparing $$$s$$$ with the first $$$x$$$ occurances of $$$t_1$$$ removed to $$$t[x + 1, n]$$$ instead of comparing $$$s$$$ to $$$t$$$.
   • So we set $$$cost = cost + \sum_{i = 1}^{x} {pos_i - i}$$$ and repeat the process for the first block of the newly obtained strings.

So we effectively are repeating the process of case 2 for each block in order, and take the min of case 1 for each block.

However this still runs in $$$O(blocks * n)$$$, and the number of blocks can be upto $$$n$$$ (all characters different), so this is still $$$O(n ^ 2)$$$ in the worst case.

Suppose there exists some $$$t_i \gt t_{i + 1}$$$. Lets say we have processed the blocks upto index $$$i$$$ and made $$$s[1, i] = t[1, i]$$$ at some cost $$$c$$$. Now to proceed with this process we will have to make $$$s_{i + 1} \leq t_{i + 1}$$$. Let the cost of the moves for this be $$$d$$$. But it will take only one more move than this to make $$$s_{i} \lt t_{i}$$$ since $$$t_{i} \gt t_{i + 1}$$$.

So we know the answer is $$$\textbf{AT MOST}$$$ $$$c + d + 1$$$, and that the answer for any further block is $$$\textbf{AT LEAST}$$$ $$$c + d$$$. This $$$c + d$$$ is only achievable when $$$d = 0$$$ and $$$s[i + 1, n] < t[i + 1, n]$$$ which can be checked for in $$$O(n)$$$ time.

If a block has a smaller character than its preceding block we can immediately check if there is an optimal answer from a further block and don't need to check further blocks one by one. So we only care about at most the first 26 blocks. So our solution now runs in $$$O(min(blocks, 26) * n)$$$ which is clearly good enough for the given constraints.

Submission — 141162437 (with comments), 141162629 (without comments)

Can someone explain how do you use bitsets in F? Isn't it mod 3?

Anyone please tell me why in problem B, when s[0] == s[1] the answer becomes only s[0]s[0]??

My solution for C.

141153641

Problem C can also be solved in O(n^2 log(n)) by just selecting one element at a time(ith element) and then we will calculate the value of d for every other element (d is the common difference by which we can reach jth element without altering the jth element) and we will store it in a map. The maximum value of d(maxd) which has occurred is the number of element which we do not have to change plus the ith element. So the ans will be n-1-maxd .

    int n;
    cin>>n;
    vi a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int ans=1e9;
    for(int i=0;i<n;i++){
        map<pii,int> mp;
        int mx=0;
        for(int j=0;j<n;j++){
            if(i==j)continue;
            int tot=abs(j-i);
            int diff;
            if(i>j)diff=a[i]-a[j];
            else diff=a[j]-a[i];
            int sign=1;
            if(diff<0)sign=-1;
            diff=abs(diff);
            int g=__gcd(diff,tot);
            diff/=g;
            tot/=g;
            diff*=sign;
            mp[{diff,tot}]++;
            mx=max(mx,mp[{diff,tot}]);
        }
        int change=n-1-mx;
        ans=min(ans,change);
    }
    cout<<ans<<endl;

problem C why it is failing on testcase 7

141145372 this is my submission id

Here are alternative ideas for D and E using two pointers.

D: the first thing to notice is that we can simplify the condition. In this case if we subtract x from all a_i the condition simplifies to having the sum of values in all subsegments be greater than 0. Now all we have to do is use two pointers and greedy. Start the two pointers at the start of the array. Increase the right pointer while this sum is negative. If the current segment length is greater than 1 unselect the last value and set the left and right pointers to after this value. Repeat until you get to the end of the array. Additionally if the sum ever gets greater than or equal to 0 and the segment size is greater than 1 then we should increase the left pointer until it becomes negative or the segment size becomes equal to 1.

E: First notice that there must be a prefix of values where a_i=b_i followed by one value where a_i>b_j. In order to make a<b it is necessary to change one of the values in this prefix or single value. Otherwise a will still be greater than b. It's pretty obvious that we only need to swap to values in a. The answer is the distance between these two values. Let's call these two positions i and j. Without loss of generality the final result of this swap will be a[i] = a[j]. We also know that for this result to work we need it to be the case that a[i]<b[i] after the swap. Therefore we simplify the problem to finding the minimum value of j-i where a[j]<b[i], j>i, and i is a position in the prefix before and including the first different value between a and b (which we will now notate as i<=P). Now we use a common greedy trick where we notice that many values of i and j are unoptimal. In particular we will only keep values so that when i<j, b[i] > b[j] and a[i] > a[j]. This means that we have two monotonic sets for a and b which we can choose from. From here we simply apply a two pointers technique in which i=P and j=N. We decrease j as much as we can while a[j]<b[i]. Then we decrease i. In total this gives us the answer in O(N).

Problem E:

How can Binary Indexed Tree be useful? I'd be grateful if someone explained.

The editorial for problem G seems to have "a -> b" in the reversed/wrong order.

can somebody explain d in detail after subtracting x what is to be done?

Hello. I can't understand why my solution of D problem isn't working. I told that we can use some kind of greedy algorithm. Let's choose every number from prefix in our array. So if our prefix i isn't available(it's organize not possible situation), so we just don't mark this, in other case we just mark that number and go for i + 1. In that situation we know that for every possible combination of l and r < i problems statement is correct, so we should just check the case there i equal to r and compute the minimum avg_number for all possible l. If that minimum avg_number < x we don't mark x. I barely can understand why this isn't a solution for this problem. Can someone explain why this isn't working and probably give me not such a big sample of this? 141117167 — my submission. I understand that it's working with square n time, but problem with Wrong Answer and it's not very hard to organize nlog(n) time complexity.

Can anybody please give a counter testcase for my solution for problem C (WA on test 3). 141135074

And I would also like to hear some tips about how to debug the solution if my approach is right? Since last 4-5 contests I am getting the approach and key observations right but not able to code it correctly. How to improve upon this?

For problem E's solution: "In general, we can easily see that the optimal strategy is to move characters one by one, every time choosing the closest character".

How can we prove that this is true?

For C, i thought about each element v[i] as being a point in the plane (v[i],i). If a point k is in the same arithmetic progression as points i and j, then (v[i],i), (v[j],j) and (v[k],k) are colinear. That way you just do shoelace theorem to see if the area of the polygon of those 3 points is 0. Code: 141085542

Im currently in a war to let the geometry tag be on C rn

can anyone help me with problem B I'm getting WA 141164645 is my sumbission

I dont know but this has been done with me for the 3rd time. Although I had written my code myself completely then too it has been pliagrised.This is way too much man.Last time also the same thing happened.What should I do to make my code look different than other people code that I havent even seen. Pliagrising people who had written their code themselves and then solutions getting skipped really breaks us.Many people have the same logic. Moreover to say most of the people have the same approach. Moreover many people have same template and initial declarations same. Is this how codes are getting pliagrised? Really disappointing man just because I'm a newbie and my implementation method matches with some random person I am declared as a cheater and my solutions get skipped. Man this is way too bad.Even who are trying hard everyday are getting disappointed because of this. Sorry in advance if anyone gets offended by this post. NO OFFENSE TO ANYONE.

Why isn't anyone talking about the System Testing of Problem-C. Only 5 tests were used for system testing and later after calculation of points and final standings, 2 more tests were added. Many solutions failed to clear those 2 tests but still in the contest their solution is being shown Correct. This testing looks unfair to me. We should talk about every detail and a wrong solution should be judged wrong. This is also in conflict with codeforces culture where even a minute test cases is important as any other. Please take a look into it.

Why is it optimal to choose $$$k + 1$$$ when $$$s_k = s_{k + 1}$$$ in problem B ? I thought choosing $$$k$$$ would be optimal since we want to make the answer the smallest in length and lexicographically.

Regarding question C, why is my co``de wrong in the seventh sample? Have a good brother help me to see it, thank you，

Your text to link here...

Can anyone please tell me why this solution 141227084 fails for Problem D. Pre[i] denotes the minimum sum (Σ(ai — x)) till i and dp[i] denotes maximum elements can be taken till i?.

Suggestions regarding my approach or any corrections would be appreciated.

Thanks in advance :)

Anyone solve problem F by local search ?

I am unable to understand why my code for question C is giving wrong ans in testcase 7. Someone help me please. below is link for my code : https://codeforces.com/contest/1616/submission/141240022

I did C using Geometry...

141250782

I got a RUNTIME_ERROR verdict on this solution: https://codeforces.com/contest/1616/submission/141075698. Can someone point out the problem? Unfortunately I can't view the full test case because it is very long.

Can someone please explain Note that there should be a negative-sum subsegment of length 2 or 3, if there is a negative-sum subsegment. It is easy to see as x<0,y<0⇒x+y<0.

141255861 Why I get TLE it is a O[n] ,is not it? its about 3*100000?????

in the 2nd question can anyone tell me, a or aa which appears earlier in dictionary. i guess a if so then why is there a test case that has aa as output

I’ve used a weird method accepting F in the contest.

Specifically, for each test case, I repeat several times doing the following things: 1. giving edges random value. 2. adjust it to minimize the ternary rings which is not same and not {1,2,3}. If the number of illegal ternary rings haven't changed for several adjusting operation, then I just do it again.

In problem H's tutorial, there is

add a bunch of simple combinatorial formulas in case none elements are chosen in one of these pairs.

I don't know how to do it. Can anyone give me some more clearly explaination?

Thanks in advance.

UPD: I wonder why downvote? although I solved this problem by another way, but I wonder how to solve it in this way. Can anyone help me?

Many C solutions i saw had 3 loops inside each other, doesn't that make its time complexity O(n^3) ? If yes then how it gets accepted.

Can you explain a little more about why the solution for question a works?

in problem D ,can someone prove why we check only negative sum segments with lengths 2 ,3 only??

Thanks for contest! Really enjoyed problem E :)