# Codeforces Round 637 Div 2

Hello everyone ,
My solution to problem C 6CAylm - Online C++0x Compiler & Debugging Tool - Ideone.com
Anyone please help me in figuring out the test case where it failed and share your approach. Since codeforces is down right now so I cannot see the test case where it failed

Failing on this case

1
5
5 4 3 2 1

1 Like

Here’s my approach.

I tried to construct the permutation, I go from 1 to N , let idx hold the index of the last unfilled position, so if the index of ith number is idx , simply decrement idx and move on to the next number else, first let j=i,then from the index of ith number till idx ,check if a[i]+1 = a[i+1] (keep incrementing i) is valid or not , if not ans is No , else idx = (index of j)-1 and move on to the next number.

1 Like
1
4
4 3 1 2


It gives no for this testcase, however the answer is yes.

I am not sure if its correct. since system testing is yet to take place. For every index I checked if a[i]+1=a[i+1]||i>=n-a[i].

Note the +1 condition is being checked first always and if only its not satisfied is the second condition checked…

That’s such a nice solution. I just optimised their given algorithm and tried to generate the test case.

Like this
void solve(){
int n;
cin>>n;
vector<int> pos(n);
for(int i=0;i<n;i++){
int x;
cin>>x;
pos[--x]=i;
}
set<pair<int,int>> values;
set<int> free;
vector<int> indexvalue(n, 1);
for(int i=0;i<n;i++){
values.insert(mp(1,i));
free.insert(i);
}
free.insert(n);
for(int i=0;i<n;i++){
if(indexvalue[pos[i]]!=(*(values.rbegin())).first){
cout<<"No\n";
return;
}
values.erase(mp(indexvalue[pos[i]], pos[i]));
free.erase(pos[i]);
int next=*(free.upper_bound(pos[i]));
if(next!=n){
values.erase(mp(indexvalue[next], next));
indexvalue[next]+=indexvalue[pos[i]];
values.insert(mp(indexvalue[next], next));
}
}
cout<<"Yes\n";
}

2 Likes

For the problem A of division 2 why this logic was giving wrong answer any idea.

    int x = n*(a-b); int y = n*(a+b);
if( (c-d<=x and x<=c+d) or (c-d<=y and y<=c+d) ) cout<<"Yes\n";
else cout<<"No\n";


It was failing on pretest 2.

n=1, a=10, b=9, c=10, d=2

2 Likes

It should print Yes since 19 lies between 16 and 20. What would be the correct answer ? @everule1

1 Like

I didn’t fully think it through. Sorry. Corrected the test case:/

1 Like

I also got WA in div2 A . Could not find any negative case. Can someone explain their approach for div2 A please?

void solve(){
int n, a, b, c, d;
cin>>n>>a>>b>>c>>d;
int maxgrain=n*(a+b);
int mingrain=n*(a-b);
int maxval=c+d;
int minval=c-d;
if(maxgrain < minval || mingrain>maxval){
cout<<"No\n";
}
else{
cout<<"Yes\n";
}
}


Maybe this will help/

1 Like

It will print No. and I think that is correct. @everule1

Yup the solution is right I get it. But could you mind suggesting test case where mine code fails. Thanks.

On the new test case? It’s yes. I think you misunderstood the question. You have to find if there is an intersection between the segments n(a-b), n(a+b) and c-d, c+d

1 Like

Your issue is, if both c - d and c + d are between x and y, there will be a valid answer, but you won’t find it.

1 Like

Well you checked for the boundary conditions but what about when (a - b) * n < c - d and (a + b) * n > c + d ,
you see that clearly according to your condition it would fail.

1 Like

Did you solve D? I had no clue how to approach without O(nk|d||s|\log{nk}) time complexity. I did precompute the distances between all binary strings.

Let dp[i][j] be the highest digit you can get at position i with j moves having been made. Then you can construct the string with a parent array. O(10 \cdot nk) in total.

edit: For this to work, you have to reverse the initial order of the strings.

1 Like

Thank you I got it. Thanks @everule1 and @galencolin.

1 Like