Hello. Thank you for participating in the BITCode October Round. We hope that you enjoyed the problems we prepared for you. We would like to apologize for the late editorial. Incase, if you weren’t able to solve them, here are the solutions with tested code that you can go through to figure out what went wrong in the contest.

 

Upsolving the problems is the most important thing to do after a contest. Here they are:-

Odd Digit Problem

Problem Setter’s Solution:

#include <bits/stdc++.h>
using namespace std;


int main() {
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        vector<string> v(n);//taking string as an input would be more efficient and easy to implement rather than taking as integer.
        //It is a common misperception that integers can't be taken input as string(In C++)
        //String has large number of built-in template classes and different types of implementation so we should try to bring our question to string implementation
        //as and when applicable.(Ex: Dealing with very large numbers)
        for(int i=0;i<n;i++)
        {
            cin>>v[i];
        }
        long ans=0;
        for(int i=0;i<n;i++)
        {
            if((v[i].length())%2)//equivalent to((v[i].length()%2)!=0)
            ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

Magical Keyboard

Problem Setter’s Solution:

#include<bits/stdc++.h>
using namespace std;
int main()
{

    string s; cin>>s;
    stack<char> st;
    int n=s.length();

    // if pressed '#' just remove the last entered char in the stack
    // else if the key pressed is not '#' then just add that char in the stack.
    for(int i=0; i<n; i++){
        if(s[i]=='#')st.pop();
        else st.push(s[i]);
    }
    // now after performing the above operation the stack contains that string.
    
    // To get the string from the stack we have to take out char one by one
    // and the print the string in reverse order.
    string anss;
    while(!st.empty()){
        anss+=st.top();
        st.pop();
    }
    reverse(anss.begin(), anss.end());
    cout<<anss;
    return 0;
}

Maximize Score

Problem Setter’s Solution:

Alex will try to move to the next room such that at the end his score is maximum. So, for each room he will check for each possible ways to reach that room and goes from where he gets maximum score. The ways to reach ith position is either from (i-1)or(i-p) position where p is a prime with least significant digit equals to 3.

#include<bits/stdc++.h>
using namespace std ;

bool isPrime(int n){
    if (n <= 1)
        return false;
 
    for (int i = 2; i*i<= n; i++)
        if (n % i == 0)
            return false;
 
    return true;
}
 
int main() {
    int n;
    cin>>n;
    vector<int>room(n);
    for(int i=0;i<n;i++)cin>>room[i];
    
    int dp[n];
    dp[0]=room[0];

    for(int i=1;i<n;i++){
        dp[i]=dp[i-1]+room[i];
        int j=3;
        while(i>=j){
            if(isPrime(j)){
                dp[i]=max(dp[i],dp[i-j]+room[i]);
            }
            j+=10;
        }
    }
    cout<<dp[n-1]<<"\n";

    return 0;
}

XOR and Tree

Problem Setter’s Solution:

The answer is always YES if the xor of the array is 0. Because you can delete any edge in the tree, and the 2 components will have the same xor. Otherwise, We need to partition the tree into 3 components that have the same xor. Let x be the xor of all node values in the tree, then The xor of every component will equal x. We need to search for 2 edges to delete from the tree and one of them such that the xor every component equals x and if we found them and K≠2 then the answer is “YES” otherwise “NO”.

#include<bits/stdc++.h>
typedef long long ll;
#define vll vector<ll>
#define pb push_back
#define pll pair<ll,ll>
#define vpll vector<pair<ll,ll> >
#define st(x) sort(x.begin(),x.end())
#define sz(x) (ll)x.size()
#define input(n,x) for(ll i=0;i<n;i++){ll k;cin>>k;x.pb(k);}
#define fr first
#define sc second
#define rep(i,j,k) for(ll i=j;i<k;i++)
#define repn(i,j,k) for(ll i=j;i>=k;i--)
#define vvll vector<vll>
#define vvpll vector<vpll>
#define vb vector<bool>
 
using namespace std;
vll x;
vvll tree;
 
vll xo;
vb there;
 
bool dfs(ll k,ll v,ll val){
    ll count=0;
    ll u=x[k];
    bool pos=false;
    for(auto i:tree[k]){
        if(i == v){continue;}
        if(dfs(i,k,val)){return true;}
        count+=there[i];
        u^=xo[i];
    }if((tree[k].size()==1) && (tree[k][0] == v)){
        pos = (x[k]==val);
    }
    if(count==2){
        return true;
    }else if((count==1) && (u)==0){
        return true;
    }
    pos = pos|(count>0);
    there[k] = pos|(u==val);
    xo[k] = u;
    return false;
}
 
void solve(){
    ll n,k;
    cin>>n>>k;;
    xo = vll(n);
    xo.clear();
    there.clear();
    there = vb(n);    
    x.clear();
    input(n,x);
    ll y=0;
    rep(j,0,n){
        y^=x[j];
    }
    tree = vvll(n);
    rep(j,0,n-1){
        ll p,q;
        cin>>p>>q;
        p--;
        q--;
        tree[p].pb(q);
        tree[q].pb(p);
    }
    if(!y){
        cout<<"YES\n";
        return;
    }else if(k==2){cout<<"NO\n";return;;}
    if(dfs(0,-1,y)){cout<<"YES\n";}
    else{cout<<"NO\n";}
    return;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Divide Gold

Problem Setter’s Solution:

This question can be solveed un multiple ways using different Data Structures. It can be solved using queue, Dp or even without one of these.

Approach of Dynamic Programming

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

const int inf = (int)1e9;

char a[2000];
int res[2000];
int d[2000][2000], dd[2000][2000], ud[2000][2000];

int main(){
  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);
  int n;
  cin>>n
  for(int i = 1; i < n; i++){
    cin>>a[i]
  }
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
      d[i][j] = inf;
    }
  }
  for(int i = 1; i <= n; i++){
    d[1][i] = i;
  }
  for(int i = 1; i <= n; i++){
    if(i > 1){
      for(int j = 1; j <= n; j++){
    if(a[i - 1] == '='){
      d[i][j] = min(d[i][j], d[i - 1][j] + j);
      continue;
    }
    if(a[i - 1] == 'L'){
      d[i][j] = min(d[i][j], ud[i - 1][j + 1] + j);
      continue;
    }
    d[i][j] = min(d[i][j], dd[i - 1][j - 1] + j);
      }
    }
    dd[i][0] = inf;
    for(int j = 1; j <= n; j++){
      dd[i][j] = min(dd[i][j - 1], d[i][j]);
    }
    ud[i][n + 1] = inf;
    for(int j = n; j > 0; j--){
      ud[i][j] = min(ud[i][j + 1], d[i][j]);
    }
  }
  int ans = inf, num;
  for(int i = 1; i <= n; i++){
    if(d[n][i] < ans){
      ans = d[n][i];
      num = i;
    }
  }
  for(int i = n; i > 0; i--){
    res[i] = num;
    if(i == 1){
      break;
    }
    if(a[i - 1] == '='){
      continue;
    }
    if(a[i - 1] == 'L'){
      for(int j = num + 1; j <= n; j++){
    if(d[i - 1][j] + num == d[i][num]){
      num = j;
      break;
    }
      }
      continue;
    }
    for(int j = 1; j < num; j++){
      if(d[i - 1][j] + num == d[i][num]){
    num = j;
    break;
      }
    }
  }
  for(int i = 1; i <= n; i++){
    cout<<res[i]<<" ";
  }
  return 0;
}

Queue implementation

#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair <ld ,ld > pt;

const ld EPS=1e-9;
const ld PI=3.1415926535897932384626433832795;

const ll INF=1e15;

int main()
{
    ifstream ifile("input.txt");
    if (ifile) {
        freopen("input.txt", "rt", stdin);
    }
    #ifdef ONLINE_JUDGE
        //freopen("output.txt","wt",stdout);
    #endif
    ll n;
    while(cin >>n)
    {
        vector<ll> a(n,0);
        ll cur=0;
        string s;
        cin >>s;
        queue<int> q;
        if(s[0]=='R'||s[0]=='=') 
        {
            a[0]++;
            q.push(0);
        }
        if(s[n-2]=='L'||s[0]=='=')
        {
            q.push(n-1);
            a[n-1]++;
        }
        for(int i=1;i<=n-2;i++)
        {
            q.push(i);
            a[i]++;
        }
        while(!q.empty())
        {
            int v=q.front();
            q.pop();
            if(v>0&&s[v-1]=='L'&&a[v-1]<=a[v])
            {
                a[v-1]=a[v]+1;
                q.push(v-1);
            }
            if(v<n-1&&s[v]=='R'&&a[v+1]<=a[v])
            {
                a[v+1]=a[v]+1;
                q.push(v+1);
            }
            if(v>0&&s[v-1]=='='&&a[v-1]<a[v])
            {
                a[v-1]=a[v];
                q.push(v-1);
            }
            if(v<n-1&&s[v]=='='&&a[v+1]<a[v])
            {
                a[v+1]=a[v];
                q.push(v+1);
            }
        }
        for(int i=0;i<n;i++) cout <<a[i]<<" ";
        cout <<endl;
    }
    return 0;
}

Simplest code

Although this wouldn’t be the most optimal code but its easiest to implement

#include <bits/stdc++.h>
using namespace std;
typedef long long li;
typedef vector<int> vi;
typedef pair<char, char> pi;
typedef pair<li, li> pli;
#define mp make_pair
void solve();

int main(){
#ifdef DEBUG
    freopen("input", "r", stdin);
#endif
    solve();
    return 0;
}
void solve(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    int a[1111];
    a[0]=1;
    for(int i=0;i<n-1;++i){
        if(s[i]=='R')
            a[i+1]=a[i]+1;
        else if(s[i]=='=')
            a[i+1]=a[i];
        else{
            a[i+1]=1;
            for(int j=i;j>=0;--j){
                if(s[j]=='R')
                    break;
                if(s[j]=='L')
                    if(a[j]<=a[j+1])
                        a[j]=a[j+1]+1;
                    else
                        break;
                else if(s[j]=='=')
                    if(a[j]!=a[j+1])
                        a[j]=a[j+1];
                    else
                        break;
            }
        }
    }
    for(int i=0;i<n;++i)
        cout<<a[i]<<' ';
}

Happy Learning!!!