### Rishabh.Jain's blog

By Rishabh.Jain, history, 3 years ago,

Problem: Cards

This code got accepted

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define int lli
int n;
int m;
vector<int> arr;
vector<int> inp;
void can(int pos){
if(pos == m){
cout<<"YES"<<endl;
exit(0);
}

int  cur = inp[pos];
assert(cur>=0);

if(arr[cur]<=0){
return;
}

arr[cur]--;

if(cur == 0){
if(arr[cur+1]>0){
arr[cur+1]--;
can(pos+1);
arr[cur+1]++;
}
}else{
if(arr[cur-1]>0){
arr[cur-1]--;
can(pos+1);
arr[cur-1]++;
}
if(arr[cur+1]>0){
arr[cur+1]--;
can(pos+1);
arr[cur+1]++;
}

}
}
void solve(){
cin>>n>>m;
arr.resize(n+4);
inp.resize(m);
for(int i=1;i<=n;i++){
arr[i-1]++;
arr[i]++;
}

for(int i=0;i<m;i++){
cin>>inp[i];
}
sort(inp.begin(), inp.end());
can(0);

cout<<"NO"<<endl;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}


But the following code, which is essentially the same(looks same to me) didn't:

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define int lli
int n;
int m;
vector<int> arr;
vector<int> inp;
void can(int pos){
if(pos == m){
cout<<"YES"<<endl;
exit(0);
}

int  cur = inp[pos];
assert(cur>=0);

if(arr[cur]<=0){
return;
}

arr[cur]--;

if(cur == 0){
if(arr[cur+1]>0){
arr[cur+1]--;
can(pos+1);
arr[cur+1]++;
}
}else{
if(arr[cur+1]>0){
arr[cur+1]--;
can(pos+1);
arr[cur+1]++;
}

if(arr[cur-1]>0){
arr[cur-1]--;
can(pos+1);
arr[cur-1]++;
}
}
}
void solve(){
cin>>n>>m;
arr.resize(n+4);
inp.resize(m);
for(int i=1;i<=n;i++){
arr[i-1]++;
arr[i]++;
}

for(int i=0;i<m;i++){
cin>>inp[i];
}
sort(inp.begin(), inp.end());
can(0);

cout<<"NO"<<endl;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}


I want to know what's causing this, aren't both the same? It's my first blog so I am learning how to write a good looking blog, be merciful in that respect. If the doubt is stupid, I'll happily accept the downvotes.

 » 3 years ago, # |   +1 A few observations: Why are you checking cur+1 and cur-1? If you see number i on a card, it either comes from card i or i+1 (1-based), so at first glance it looks like the -1 is a mistake. I also don't get why you do arr[i-1]++; arr[i]++; in solve. Can't it lead to the same card being used twice? Backtracking may work on time, but can you prove it runs in polynomial time? If not, can you find a solution that's guaranteed to run in polynomial time? Sometimes it's best to have a slower solution whose worst-case runtime is easier to estimate (as long as this worst case is good enough for the TL, of course).