Rishabh.Jain's blog

By Rishabh.Jain, history, 3 years ago, In English

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.

Thanks, in advance.

  • Vote: I like it
  • -27
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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).