GENIUS - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Practice

Setter: Utkarsh Gupta
Testers: Tejas Pandey and Abhinav sharma
Editorialist: Taranpreet Singh

DIFFICULTY

Simple

PREREQUISITES

Basic math

PROBLEM

Chef attempted an exam consisting of N objective questions. The marking scheme of the exam is:

  • +3 marks for a correct answer.
  • -1 marks for an incorrect answer.
  • 0 marks for an unattempted question.

Find whether it is possible for Chef to score exactly X marks.

If it is possible, print 3 integers A, B, and C denoting the number of correct answers, incorrect answers, and unattempted questions respectively.

QUICK EXPLANATION

  • We never need B \geq 3, since we can reduce A by 1, B by 3, and increase C by 4, leading to the same score.
  • Considering each value of B in the range [0, 2], there’s exactly one value, which would make X+B a multiple of 3. Chef needs to answer (X+B)/3 questions correctly.
  • Chef needs at least (X+B)/3 + B questions in order to achieve score X, so if (X+B)/3+B \gt N, then it is impossible.
  • Lastly, we can choose C = N - ((X+B)/3+B) which will be non-negative.

EXPLANATION

Let’s try to write this down in form of equations. We need to find three integers A, B, and C s.t.

  • A+B+C = N
  • 3*A-B = X
  • A, B, C \geq 0 (Number of questions cannot be negative).
  • A, B, C are integers.

Since C is non-negative, we can convert first equation into inequality A+B \leq N.

Simpler problem

Consider following problem. Minimize A+B, subject to conditions

  • A, B \geq 0
  • 3*A-B = X
  • A, B are integers.

An observation we can make is that if B \geq 3, then we can reduce A by 1 and B by 3, still satisfying 3*A-B = X and reducing A+B by 4.

Hence, it is never optimal to have B \geq 3. If there’s a solution with B \geq 3, there will be a solution with B \lt 3 as well.

So now, let’s try all values of B in the range [0, 2]. Since A = (X+B)/3 cannot be a fraction, only the value of B which makes X+B a multiple of 3 is viable. There would be exactly one such value in [0, 2]. Let’s call this p.

Hence, we have found B = p, and for that B, we can calculate A as (X+p)/3. So we have found (X+p)/3+p to be the minimum value of A+B.

Returning to the original question, A+B represents the sum of correct and incorrect answers. If we have (X+p)/3 + p \gt N, then Chef has attempted more than N questions, which is impossible. So no valid A, B and C exist in this case.

Otherwise, the number of attempted questions is (X+p)/3 + p, So we can assign C = N - ((X+p)/3 + p), making total number of questions equal to N, and score X, which is the required values.

Bonus
Prove that the resulting values will be A = \lceil \frac{X}{3} \rceil, B = 3*A-X and C = N-A-B. The answer would be impossible only when C \lt 0.

TIME COMPLEXITY

The time complexity is O(1) per test case.

SOLUTIONS

Setter's Solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);

            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }

            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }

            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
void solve()
{
    int n=readInt(1,100000000,' ');
    int x=readInt(0,3*n,'\n');
    int correct=(x+2)/3;
    int incorrect=(3*correct)-x;
    if((correct+incorrect)>n)
        cout<<"NO\n";
    else
    {
        cout<<"YES\n";
        cout<<correct<<' '<<incorrect<<' '<<(n-correct-incorrect)<<'\n';
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int T=readInt(1,1000,'\n');
    while(T--)
        solve();
    assert(getchar()==-1);
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester's Solution 1
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;


/*
------------------------Input Checker----------------------------------
*/

long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);

            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }

            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }

            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}


/*
------------------------Main code starts here----------------------------------
*/

const int MAX_T = 1000;
const int MAX_N = 100000000;

#define ll long long int
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

long long int sum_len=0;


void solve()
{
    int n = readIntSp(1, MAX_N);
    int x = readIntLn(0, 3*n);
    if((x + 2)/3 + ((3 - (x%3))%3) <= n) {
        cout << "YeS\n";
        cout << (x + 2)/3 << " " << ((3 - (x%3))%3) << " " << n - ((x + 2)/3 + ((3 - (x%3))%3)) << "\n";
    } else {
        cout << "nO\n";
    }
}

signed main()
{
    //fast;
    #ifndef ONLINE_JUDGE
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif


    int t = readIntLn(1, MAX_T);

    for(int i=1;i<=t;i++)
    {
        solve();
    }

    assert(getchar() == -1);
}
Tester's Solution 2
#include <bits/stdc++.h>
using namespace std;
 
 
/*
------------------------Input Checker----------------------------------
*/
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
 
const int MAX_T = 1e5;
const int MAX_N = 1e5;
const int MAX_SUM_LEN = 1e5;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
 
int sum_n = 0, sum_m = 0;
int max_n = 0, max_m = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll mod = 998244353;

ll po(ll x, ll n){ 
    ll ans=1;
    while(n>0){ if(n&1) ans=(ans*x)%mod; x=(x*x)%mod; n/=2;}
    return ans;
}



void solve()
{   
    int n = readIntSp(1, 1e8);
    int x = readIntLn(0, 3*n);

    int a,b,c;
    a = (x+2)/3;
    b = (x%3?(3-x%3):0);

    if(a+b>n) cout<<"NO"<<'\n';
    else{
        cout<<"YES"<<'\n';
        cout<<a<<" "<<b<<" "<<n-a-b<<'\n';
    }
}
 
signed main()
{

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r" , stdin);
    freopen("output.txt", "w" , stdout);
    #endif
    fast;
    
    int t = 1;
    
    t = readIntLn(1,1000);
    
    for(int i=1;i<=t;i++)
    {    
       solve();
    }
   
    //assert(getchar() == -1);
    assert(sum_n<=1e6);
 
    cerr<<"SUCCESS\n";
    cerr<<"Tests : " << t << '\n';
    cerr<<"Sum of lengths : " << sum_n <<'\n';
    cerr<<"Maximum length : " << max_n <<'\n';
    // cerr<<"Total operations : " << total_ops << '\n';
    //cerr<<"Answered yes : " << yess << '\n';
    //cerr<<"Answered no : " << nos << '\n';
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class GENIUS{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni(), X = ni();
        int A = (X+2)/3;
        int B = A*3-X;
        int C = (N-A-B);
        if(A+B+C == N && C >= 0){
            pn("YES");
            pn(A+" "+B+" "+C);
        }else pn("NO");
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new GENIUS().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

1 Like
#include <iostream>
using namespace std;

int main()
{
    int T, X, N, A, B, C;
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        cin >> N >> X;
        if (X == 0)
        {
            A = 1;
            B = 3 * A;
            C = (N - A - B);
            cout << "Yes" << endl;
            cout << A << " " << B << " " << C << endl;
        }
        else
        {
            if (X <= 3 * N)
            {
                if (X % 3 == 0)
                {
                    A = X / 3;
                    B = (3 * A) - X;
                    C = (N - A - B);
                    if (A >= 0 && B >= 0 && C >= 0)
                    {
                        cout << "Yes" << endl;
                        cout << A << " " << B << " " << C << endl;
                    }
                    else
                    {
                        cout << "No" << endl;
                    }
                }
                if (X % 3 == 2)
                {
                    if (X % 2 == 0)
                    {
                        A = (X + 1) / 3;
                    }
                    else
                    {
                        A = (X + 4) / 3;
                    }
                    B = (3 * A) - X;
                    C = N - (A + B);
                    if (A >= 0 && B >= 0 && C >= 0)
                    {
                        cout << "Yes" << endl;
                        cout << A << " " << B << " " << C << endl;
                    }
                    else
                    {
                        cout << "No" << endl;
                    }
                }
                if (X % 3 == 1)
                {
                    A = (X + 2) / 3;
                    B = (3 * A) - X;
                    C = N - (A + B);
                    if (A >= 0 && B >= 0 && C >= 0)
                    {
                        cout << "Yes" << endl;
                        cout << A << " " << B << " " << C << endl;
                    }
                    else
                    {
                        cout << "No" << endl;
                    }
                }
            }
            else
            {
                cout << "No" << endl;
            }
        }
    }
    // your code goes here
    return 0;
}

Pls let me know mistake in this code.

Can anyone point out for which corner test case it is giving WA

Hey there, team codechef…can u provide me the the 2nd test case, my logic was the same as mentioned over here but that test case has given me a lot of frustation and had to change the complete code toward a different approach to solve it.

I did just this… and got AC.

// Author: Tushar

#include <stdio.h>
#include<stdlib.h>
#define AC 3

int main(void) {
	int T;
	scanf("%d",&T);
	
	while(T--) {
	    int N,X;
	    int A,B,C;
	    scanf("%d%d",&N,&X);
	    if(X%AC==0)
	    	A=X/AC;
	    else
	    	A=X/AC+1;
	    B=A*AC-X;
	    C=abs(N-A-B);
	    if(A+B+C>N)
	    	printf("NO\n");
	    else
	    	printf("YES\n%d %d %d\n",A,B,C);
	}
	return 0;
}

def main():

testcases=int(input())

for test in range(testcases):
    
    #length=int(input())


    l=list(map(int,input().split()))
    
    n,x=l[0],l[1]
    
    a=x%3
    
    b=x//3
    
    if x==(3*(n-2)+1) or (x>(3*(n-1)) and x<(3*n)):
        
        print("NO")
        
    else:
        
        print("YES")
        
        if a==0:
            
            print(b,0,n-b)
            
        else:
            
            a1=b+1
            a2=3-(a)
            a3=n-(a1+a2)
            
            print(a1,a2,a3)

This was My solution in Python.

I am not sure what’s wrong with my solution , it was showing task no 2 failed but I am getting output for every input
CODE -

#include <iostream>
using namespace std;

int main() {
	int t;
	cin>>t;
	while(t--){
	    int n,x;
	    int a,b,c;
	    cin>>n>>x;
	    if(x==0){
	        a = 1;
	        b = 3;
	        c = n-a-b;
	    }
	    else if(x%3==0){
	        a = x/3;
	        b = 0;
	        c = n - a - b;
	    }
	    else{
	        a = x/3 + 1;
	        b = 3 - x%3;
	        c = n - a - b;
	    }
	    if(c<0){
	        cout<<"NO"<<endl;
	    }
	    else{
	        cout<<"YES"<<endl;
	        cout<<a<<" "<<b<<" "<<c<<endl;
	    }
	}
	return 0;
}

please let me know what’s mistake

Your solution will fail when n <= 3 and x = 0

1 Like

Hey, there are a lot of mistakes in your code where you have not considered the cases where A + B becomes greater than N itself.
Then you have simply set C = (N - A - B), where C just becomes a negative number, which cannot be the case.

SORRY but I guess you haven’t checked my code correctly I have added an if statement for A,B,C all three have to be greater than or equal to zero.

Not in the if(X==0) block.
What if N = 1 and X = 0.
The answer should be:

yes
0 0 1

But your code would print

yes
1 3 -3

Hey @anon93981735, we cannot make the input files public but we can help you debug your code or point to some corner cases where your code fails. Please share your code that is causing problem and we will help

Hey, your code would fail on cases where X == 0, but N < 4, for ex:

1
3 0

Your code will output:

yes
1 3 -1

which is wrong.
The thing is, you don’t actually need to put a = 1 if X is 0. you can simply put both a and b as 0 and it would solve the problem :slight_smile:

Yes sir you are correct I didn’t notice that sorry for bothering you again