# GENIUS - Editorial

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

Simple

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];
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 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){
}
long long readIntLn(long long l,long long r){
}
}
}
void solve()
{
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);
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 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){
}
long long readIntLn(long long l,long long 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()
{
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

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 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){
}
long long readIntLn(long long l,long long 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 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;

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;
void run() throws Exception{
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());}

StringTokenizer st;
}

}

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

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


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

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;
}
}
}
return 0;
}


Pls let me know mistake in this code.

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.

yes
0 0 1

yes
1 3 -3

Hey @david03, 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