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.
what about
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
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