What was the point of making B so hard ?

Not able to see Jury solution.

You are not allowed to view the requested page

Thanks for the super fast editorial. Link for Solution not working

Can anyone explain the solution for D in a more clear and detailed way? Thanks!

Disappointed with B.

So fast editorial :)

My binary search solution for problem B FST'd, giving WA on TC-14 173495467 I used that same solution as editorial, finding the intersection of segments. Any help?

B has multiple solutions, one being implementation heavy, and the others being also implementation heavy. Hands down, this is the worst round I have seen excluding the plagiarized ones.

upd: yep turns out my B solution was overcomplicated

For B, just move everyone towards the person who takes maximum time, and then print (min+max)/2.

173498541

Solution for A (https://www.youtube.com/w[user:MikeMirzayanov]atch?v=gHxV9jwwJyk). Solution for C (https://www.youtube.com/watch?v=VhZytayYfhk). Solution for D (https://www.youtube.com/watch?v=QWYxr-IEwE0).

These solutions were leaked on youtube and the name of the user is clearly visible so MikeMirzayanov please look into this.

B is a great problem, but I think testers should have suggested to swap it with C. Very clever solutions

I think that the problem writers should remind us or include a warning to use setpercision() in these type of problems, similar to how interactive problems say to use flush.

How is the value for problem B unique? For the given example: test case 3:- 1 4 0 0

the optimal value here is 2.5 as per solution, but it can be 1,2,3,4 as well. Where am I wrong?

My intuition for Problem C:

I used stack to keep a track of non-decreasing substring possible along with their indices. Then I added all stack items to another string 'ans', and then added the rest of indices with a increase in their value by 1 (except for 9) and then sorted the 'ans' string to get the required string!

Solution : https://codeforces.me/contest/1730/submission/173460849

Thx for fast editorial)

thanks for fast editorial

I am shocked by the massiveness of the d*** author put on the editorial of the D. Seems like he couldn't care less

UPD: he added example, but still no proves

I cannot make head or tail of the editorial for D.

https://codeforces.me/contest/1730/submission/173497901 --> I understood the logic for B from the editorial but can any one tell me why have we done 2*t[i] and 2*x[i] in problem B ?? unable to figure it out :/

Can someone explain why in the editorial of E, we are considering only j1 and j2 positions of the divisor d and also how we are avoiding overcounting the segments ?

Does anyone have suggestions for resources to read about double and precision like that was used in problem B?

Eventually, I got a working algorithm, but still failed some of the test cases because of precision. When I put the line

std::cout << std::fixed << std::setprecision(10) << pos / 2.0 << "\n";

I successfully passed the test cases whereas just doing

std::cout << double (pos) / 2 <<"\n";

failed. Here are the two submissions:

Failed 173508008

Accepted 173508382

For problem B I did ternary search over the time selected for everyone to meet and it worked but I'm not sure why.

Code

Is there a solution you wanted to cut that took O(NDlogN) in E, or why are the constraints high?

Other solution to C problem is using merge sort.

The idea is increment elements of left array in merge if have an element of right array merged before the remaining left, but this increment can be performed once in all merges. Using an array of pairs with boolean flag to store if the element was incremented or not.

solution: 173513587

I got WA on this submission during contest time.(https://codeforces.me/contest/1730/submission/173466205) But after using "printf" instead of "cout", my submission is accepted. This is link of accepted version. (https://codeforces.me/contest/1730/submission/173516968) I am unable to understand the reason .Can anyone please help me out?

In the solution 1 of Problem B, The segment should be [xi−(T-ti),xi+(T−ti)].

B would have been good if the answer fitted in a double or a float. That division by 2 just ruins what would have been a very good B

edit: ok, read other comments. I need to put a setprecision in my template

For proof of B,

if xi <= y, xi + ti is not guaranteed less or equal to y, right? why the time needed is y — xi — ti then?

Can someone explain the logic? why Problem B classic solution working here?

B’s problem itself is good (the difficulty is higher than normal B’s though), but what is “std::setprecision”? This is similar to mistakes like “printing Yes instead of the required YES”, or forgetting to use “std::endl” to flush the output for interactive problems.

In the future should we add hints in the problem statement on those issues (or at least add test cases revealing such issues in the problem statement)? They are not related to algorithms/problem-solving at all. We might still should learn them, but I don't want to fail contests just for learning / remembering such boring things.

Furthermore, (this might be aggressive), I also believe "int overflow" shouldn't be tested in contests (they are typically not related to algorithm/problem-solving either).

D: "interesting"

E: "5s, what's the f**k"

In the end I got a solution of $$$O(\sum d(a_i)\log n)$$$ but I think it's too slow.

After the contest, my friend told me he passed E with $$$O(\sum d(a_i)\log n)$$$.

The story tells me, lower_bound is so fast.

Why setprecision(6) fail on B? Took me 20 mins just to debug it lol

explanation of editotial B:

1.Why the object(in other words, the pair) is unordered? That is because we can easily reverse a pair. for example, if we want to reverse a pair {c1,c2} initial:

{a1,a2},{b1,b2},{c1,c2},{d1,d2}

reverse a prephix to set {c1,c2} to the the top:

{c2,c1},{b2,b1},{a2,a1}

reverse the first pair:

{c1,c2},{b2,b1},{a2,a1},{d1,d2}

reverse a prephix to set {c1,c2} to its initial position:

{a1,a2},{b1,b2},{c2,c1},{d1,d2}

We can see that each pair remains their position, and {c1,c2} has been reversed.

2.Why can we sort the objects to a palindrome if a palindrome exists? That is because here is a method to arbitrarily sort the objects. Suppose you have a sequence like this:

{a,a},{b,a},{b,a},{c,d},{c,d}

Its palindrome may be this:

{b,a},{c,d},{a,a},{c,d},{b,a}

First we reverse the phephix to move {b,a} to the beginning:

{b,a},{a,a},{b,a},{c,d},{c,d}

Second we reverse the whole sequence to move {b,a} to the end:

{c,d},{c,d},{b,a},{a,a},{b,a}

Then we have made the last position equal, repeate the work on tht next position till the whole positions equal.

Has anyone tried finding the position X0 in problem B using Ternary Search? I tried but I am not able to find why I am getting wrong answer in the third test :( , Here's my submission 173457434 , Update : I had not applied setprecision(10) and because of which I was getting marginal error :-| ; Idk weird solution

why my B always wrong on test 3 in two ways, maybe some details fault, but I can't find. Can anyone remind

As a participant that solved B in less than 10 lines in 7 minutes, I suggest it would be better if the positions are even numbers.

I have a greedy solution for B. For the persons whose times are below the maximum t,you can just let them gather towards the person whose time is the maximum.If one person meets the person with the maximum dressing time,he stops.It is obviously the optimum choice. Then sort the position,the mid point of the maximum and the minimum is the answer.

Another intuition for binary search solution in problem B:-

We want to minimize $$$max(t_{i}+|x_{0}-x_{i}|)$$$, so thinking about this graphically, the graphs of each of the terms $$$t_{i}+|x_{0}-x_{i}|$$$ will be a shifted 'V' graph in the X-Y plane,

take the fifth example in the first test case, the graph will be like:- If the image isn't visible above please visit this link https://postimg.cc/7bQM0WJJ

So we see that the curve for the maxima of all these group of graphs will again be a V shaped graph, and it will have a unique minimum value, further we can deduce that this minimum value will either occur at an integer value or a decimal terminating in .5.

Now the minima can be obtained by binary search on the variable x

I am so Angry i submitted this solution a thousand times but i did not set precision.

https://codeforces.me/contest/1730/submission/173553138

I tried solving B using double ans=(Min+Max)/2; got wrong answer on testcase 3

Submission link : https://codeforces.me/contest/1730/submission/173555196

but tried doing the same with int ans=(Min+Max)/2; cout<<ans/2; if(ans%2!=0){ cout<<".5"; } cout<<endl; It got accepted that way

Submission Link : https://codeforces.me/contest/1730/submission/173555548

Can anyone help me in this ?

Hi, Brovko! In the solution (1) of problem B's editorial, the segment will $$$[x_i−(T-t_i), x_i+(T−t_i)]$$$. You have written $$$[x_i−(T+t_i), x_i+(T−t_i)]$$$.

For QC why is this thing showing TLE>I have used only one loop with complexity of time as O(n).

include<bits/stdc++.h>

define ll long long

using namespace std; int main(){ int t; cin>>t; while(t--){ char str[200002]; cin>>str; ll arr[200002]; for(ll i=0;i<strlen(str);i++){ arr[i]=(str[i]-'0'); } ll poke=arr[strlen(str)-1]; for(ll i=strlen(str)-1;i>0;i--){ if(poke<arr[i-1]){ if(arr[i-1]+1>9){ arr[i-1]=9; } else{ arr[i-1]=arr[i-1]+1; }

}
else{
    poke=arr[i-1];
}

} sort(arr,arr+strlen(str)); for(ll i=0;i<strlen(str);i++){ cout<<arr[i]; } cout<<endl;

} }

Can someone explain what exactly does set precision do in B. As only the average of the extremes is to be taken, at max a single decimal point would be there. Hence if the sum of the extremes is even I just do integer division and if it is odd I just do the same and add 0.5 in cout. But I got WA in test case 3, but adding set precision passed all test cases. I then just printed .5 as a string in the case of odd and I passed all.

Which classical problem is being referred to with regards to B?

Could somebody provide a link?

Nice contest,tks！

(To me, Problem E & F is far easier than D ...)

Hello Brovko, can you please tell one thing for question B, what made you not to think in direction of DP. How you will describe your intuition for this? Is B at all solvable by DP if not considering it's time constraint and input size in consideration.

Can anyone tell why my answer is wrong for 1st testcase. https://codeforces.me/contest/1730/submission/173617360

s2 += (char)min(s[i]+ 1 — '0', 9); s2 += (char)min(int(s[i]) + 1, int('9')); here s2 and s are strings USING THE first one i am getting empty string and using the second one i am getting correct answer . WHY ? is this happening

Brovko, I think in editorial of 1730B - Meeting on the Line in 2nd part(i.e classic part): ** and the two we want to replace him with — y−xi+ti and y−xi−ti ** . In 1st equation sign of y should be positive i.e (y-xi+ti). Sorry if I am disturbing you by pinging again and again but I think it can be very confusing for beginner sometimes. Although it is a very small mistake i think. I can be wrong also.

Brovko just one final question on the problem B after a long time(I asked you some questions earlier). Why binary search would take nlogn in problem B. Shouldn't it be nlogT, where T = 10^8. And will not it give TLE. As nlogn works for n <= 10^5. From this blog Your text to link here.... Why sir shnirelman code is not giving TLE. Sorry again but this one is really confusing me.

Does C really have an annoyingly simple(interesting) solution? Brovko

#define nfs ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define test int t;cin>>t;while(t--)
#define outl(n) cout<<(n)<<'\n';
#define rf(i,b,a) for(int (i) = (a)-1; (i) >= (b); --(i))  

int main(void){
    nfs
    test
    {
        string s;cin>>s;
        char mn='9';
        rf(i,0,s.length())
            if(s[i]<=mn)mn=s[i];
            else s[i]=min(char(s[i]+1),'9');
        sort(s.begin(),s.end());
        outl(s)
    }
    return 0;   
}

In B, isn't taking average of all points more accurate?

why b is much more harder than c and why the solution with time complexity o(n*log(n)) gets tle? it's just like a bullshit for me!!!

Lets say : x[ ] = {1,2,3,10} and t = 0 for all , shouldn't it be optimal for them to meet at x = 2.5 instead of x = 5.5 ? How are we taking average of the extremes while we should take median of whole imo.

In B, What if positions are X = [1, 2, 3, 10] t = [0 0 0 0] According to editorial, optimal answer is 5.5 For 5.5, distance = 4.5 + 3.5 + 2.5 + 4.5 = 15 For 3, distance = 2 + 1 + 0 + 7 = 10 So shouldn't answer be the median??

The suffix minimums **mni** should be left, because no matter what digit we leave after **mni**, it will be no less than **mni**, and therefore will not improve the answer. is it mandatory to keep mni on left ? can't we simply sort the updated string ?if we can do this how this will work ?

Can someone explain, how unique answer in problem B, test case 3 : answer also exist for point 2 and 3 ?

Ternary Search Solution for B: 262674398

In Problem B:

We get our answer in the classic solution of using point xi-ti, xi+ti for (xi, ti). I understand the solution, but this approach is not trivial; how can I ensure it comes again and I figure this out?

Please help Brovko,shnirelman

B had the same idea as this contest's B, which had appeared earlier too https://codeforces.me/contest/782/problem/B , basically the idea of intersection of L, R points to yield a small segment(or possibly a point)

Sorry if I'm asking a somewhat silly question.

In question B, why do we need to double up? And why does the method of checking intersecting segments work (why max, min)?

I really don't understand.

Any help is greatly appreciated.