CRDGAME - Editorial

PROBLEM LINK:

Contest Link

Author: Aryan Agarwala
Tester: Encho Misev
Editorialist: Rajarshi Basu

DIFFICULTY:

Cakewalk

PROBLEM:

There are two players, each with a deck of N \leq 100 cards. Strength of a card is defined as sum of digits of number A_i \leq 10^9 written on that card. There will be N rounds. In each round, either player will draw the first card on their respective decks. The one with higher strength wins and get 1 point. If both have the same strength, both get 1 point. We have to report who wins after N rounds are over.

EXPLANATION:

We just simulate the process. We iterate over the cards one by one and see whose strength is more. We keep 2 variables to keep track of the score of each person.

In the end, we just compare the scores and output accordingly.
The only important part if finding the sum of digits. The following is a sample code to do that, in C++.

void digitSum(int num){
    int sum = 0;
    while(num > 0){// That means the number has no digits left.
        sum += num %10; // This extracts the last digit. 
        num /= 10; // This Removes the last digit. 
    }
    return sum;
}

SOLUTION:

Setter's code
2 Likes
#include <bits/stdc++.h>
using namespace std;
int sumOfDigits(int n){
   return n==0 ? 0 : n%10+sumOfDigits(n/10);
}
int main() {
	int t;
	cin >> t;
	while(t--){
	    int n;
	    cin >> n;
	    
	    int c_total= 0,m_total = 0;
	    for(int i=0;i<n;i++){
	        int chef,morty;
	        cin >> chef >> morty;
	        int sum_c = sumOfDigits(chef), sum_m = sumOfDigits(morty);
	        if(sum_c > sum_m)c_total++;
	        else if(sum_c < sum_m)m_total++;
	        else{
	            c_total++;
	            m_total++;
	        }
	    }
	    
	    if(c_total > m_total)cout << "0 " << c_total;
	    else if(c_total < m_total)cout << "1 " << m_total;
	    else cout << "2 " << c_total;
	    
	    cout << '\n';
	}
}
2 Likes
#include<bits/stdc++.h>
using namespace std;
int less_10(long long a){
 long long c=a;
 long long l=11,p=0;

while(l>=10){

while(c!=0){
  p += c%10;
  c = c/10;

  } 
l=p;
c=p;
p=0;
}
//cout<<l<<"\n";
return l;

}
int main(){
  int t,p=0;
 cin>>t;
  int ac=0,bc=1,dc=2;
 while(t--){
  int n;
  cin>>n;
  long long count=0,count1=0;
  while(n--){
  long long chef, morty;
  long long a =0,b=0,flag=0,flag1=0;
  cin>>chef>>morty;
  if( chef>=10){
  flag =1;
  a = less_10(chef);
  }
  
  if (morty>=10){
  flag1 =1;
  b = less_10(morty);
  }
  
  if(flag==1 && flag1==1){
   if (a>b)
   	count++;
   else if (b>a)
   	count1++;	
   else {
   count++;
   count1++;
   }
   
  }
 else if (flag ==0 && flag1==1){
   if (chef>b)
    count++;
    
   else if (b>chef)
    count1++ ;
   else {
   count++;
   count1++;
   } 
 
 }
  
  else if (flag == 1 && flag1==0){
   if (a>morty)
    count++;
   else if (a<morty)
    count1++ ;
   else {
   
   count++;
   count1++;
   } 
 
 }
  
  else {
   if (chef>morty)
    count++;
   else if (chef<morty)
    count1++; 
   else {
   count++;
   count1++;
   } 
 
 }
  
  }
 
 
if (count>count1) 
 	cout<<ac<<" "<<count<<"\n";
 else if (count1>count)
	cout<<bc<<" "<<count1<<"\n";
else 
       cout<<dc<<" "<<count<<"\n";
       
 }
 }
 

// THis is my solution why it is giving wrong answer please tell me

The worst case time complexity of this will be 1000.100.(10^9) . It will exceed the time limit.

1 Like

I think you misunderstood the question. You are supposed to find the sum of digits of the number. What your program is finding is the sum of the digits until it becomes a single digit. Like for 99, the sum should be 18 but your function is returning 9.

1 Like
#include <bits/stdc++.h>
using namespace std;
int main()
{
  long long int t;
  cin>>t;
  while(t--){

    long long int num;
    cin>>num;
    long long int final_c=0,final_m=0;
    long long int points_c,points_m,sum1=0,sum2=0;

    while(num--){
      long long int c,m;
      cin>>c>>m;

      if(c < 10){
        points_c = c;
      }

      if(m < 10){
        points_m = m;
      }

      if(c >= 10){
        long long int temp=c;
        while(temp > 0){
          sum1 = sum1 + temp % 10;
          temp=temp/10;
        }
        points_c = sum1;             
      }




      if(m >= 10){
        long long int t=m; 
        while(t > 0){
          sum2 = sum2 + t % 10;
          t=t/10;
        }
        points_m = sum2;
      }





      if(points_c > points_m)
      final_c++;
      else
      if(points_c < points_m)
      final_m++;
      else
      if(points_c == points_m){
        final_m++;final_c++;
      }
    }
    



    if(final_m > final_c){
      cout<<"1 "<<final_m;
    }
    else
    if( final_c > final_m){
      cout<<"0 "<<final_c;
    }
    else
    if(final_c==final_m){
      cout<<"2 "<<final_m;
    }
  }
  return 0;
}

//This is my code. I checked the given testcases, it gave right output. But my code was not accepted . Please let me know what went wrong//

You must initialise sum1 and sum2 back to 0 at the end of every round.

t = int(input())
c, m =[], []
a, b = [], []
for i in range(t):
	N = int(input())
	for num in range(N):
		A, B = list(input().split())
		A.strip(' ').split(), B.strip(' ').split()
		
		for num in A:
			num = int(num)
			a.append(num)
		for nums in B:
			nums = int(nums)
			b.append(nums)
		if sum(a) > sum(b):
			c.append(1)
		else:
			m.append(1)
		a.clear()
		b.clear()

	if sum(c) > sum(m):
		print(0, sum(c))
	if sum(m) > sum(c):
		print(1, sum(m))
	elif sum(c) == sum(m):
		print(2, sum(c))
	c.clear()
	m.clear()`

// This is my solution, I don’t know why this is not accepted? In sample and custom inputs cases, it works perfectly fine. Can somebody tell me where I made mistake?

No, for finding the sum of digits algorithm will take O(log10(n))[base 10] ,which will be 9 in this case. So overall time will be 1000.100.log10(n)

Here, you have to compare sum of digits on cards , not the sum of numbers on the cards.

#include<bits/stdc++.h>
using namespace std;
int sum(int a){
    int x;
    while(a>0){
        x=x+a%10;
        a=a/10;
    }
    return x;
}
void sol(){
    int n,aot,bot;
    cin >>n;
    int apt=0,bpt=0;
    int a,b;
    while(n>0){
    cin >> a >> b;
    if(a>9){
        aot+=sum(a);
    }
    if(b>9){
        bot+=sum(b);
    }
    else{
        bot=b;
    }
    if(aot>bot){
        apt++;
    }
    else{
        bpt++;
    }
    n--;
    }
    if(apt>bpt){
        cout<< "0 " <<apt<<endl;
    }
    else if(bpt>apt){
        cout << "1 "<<bpt<<endl;
    }
    else if(apt==bpt){
        cout<< "2 "<<apt<<endl;
    }

}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
   int t;
    cin >> t;
    while (t>0){
        sol();
        t--;
    }


}

can anyone please help me why the code is throwing wrong answer?

Here is the link to corrected submission. They were many mistakes. Notice the changes.

These are the mistakes in your code

  1. You did not write else condition for if(a>9).
    2.You did not write the condition for draw round.
  2. You are adding the function to aot and bot instead assign the to aot and bot .
    i did the changes here

My code showing WA. It generate correct answer for sample test case. Can anyone please point out what’s wrong with this code.

    /* package codechef; // don't place package name! */

import java.io.IOException;
import java.util.Scanner;
import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.Scanner; 
import java.util.StringTokenizer; 

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
static long sum(long N) {
	long sum = 0;
	while(N % 10 > 0) {
		sum += N % 10;
		N = N/10;
	}
	return sum;
}

public static void main (String[] args) throws java.lang.Exception
		{
			Scanner sc = new Scanner(System.in);
			int t = 0;
			if(sc.hasNextInt()){
			 t = sc.nextInt();
			}
			while( t-- > 0) {
				int rounds = sc.nextInt();
				int chef_count = 0;
				int morty_count = 0;
				for(int i = 0; i < rounds; i++){
					long chef_card, morty_card = 0;
				    chef_card = sc.nextLong();
				    morty_card = sc.nextLong();
				    if(sum(chef_card) > sum(morty_card))
				        chef_count++;
				    else if(sum(morty_card) > sum(chef_card)) 
				        morty_count++;
				    else {
				    	chef_count++;
				    	morty_count++;
				    }
				}
				if(chef_count > morty_count){
				    System.out.println("0 "+chef_count);
				}
				else if(morty_count > chef_count){
				    System.out.println("1 "+morty_count);
				}
				else
				    System.out.println("2 "+chef_count);
				
			}
		}
	}

It goes wrong there. It should be while(N>0). Your code will go wrong for N=100 or any number having the digit 0 in it.

1 Like

What’s Wrong in my code

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

long long findSum(long long n){
	
	long long sum=0;
	while(n>0){
		sum+=n%10;
		n=n/10;
	}
	return sum;
}
long long  sumDigits(long long  no) 
 { 
   return no == 0 ? 0 : no%10 + sumDigits(no/10) ; 
 } 


int main() {
	// your code goes here
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		long long a,b;
		long long x1=0,x2=0;
		for(int i=0;i<n;i++){
			cin>>a>>b;
			long long y1=sumDigits(a);
			long long y2=sumDigits(b);
			if(y1>y2){
				x1++;
			}
			else if(y2>y1){
				x2++;
			}
		}
		if(x1==x2){
			cout<<"2 "<<x1<<endl;
		}
		else if(x1>x2){
			cout<<"0 "<<x1<<endl;
		}
		else{
			cout<<"1 "<<x2<<endl;
		}
	
	}
	return 0;
}

Haven’t checked the whole code yet but seems like when both win the game, you are not increasing their scores.

You must add one point to each of their scores if y1==y2

/* Name of the class has to be "Main" only if the class is public. */
import java.util.*;
import java.util.Scanner;
import java.lang.*;
import java.io.*;
class Solution{
    public static void main (String[] args)
    {
        Scanner scan = new Scanner(System.in);
        int chef=0;
        int morty=0;
        int h = scan.nextInt();
        for(int p=0;p<h;p++) {
        int n = scan.nextInt();
        int[][] b= new int[n][2];
        for(int i=0;i<n;i++){            
            for(int j=0;j<2;j++){
                b[i][j] = scan.nextInt(); 
            }
        }
        
        
        for(int i=0;i<n;i++){
            for(int j=0;j<2;j++){
                int k = b[i][j]/10;
                int l = b[i][j]%10;
                b[i][j]=k+l;
            }
        }
        
        for(int i=0;i<n;i++){
            if(b[i][0]>b[i][1])
            chef++;
            else
            morty++;
            
        }
        if(chef>morty) {
        	System.out.println(0+" "+chef);
        }
        else if(chef<morty) {
        System.out.println(1+" "+morty);
        }
        else if(chef == morty) {
        	System.out.println(2+" "+chef);
        }
        chef=0;
        morty=0;
        }
        scan.close();
    }
}

//why my code is not working

I don’t know java but conditional statements are wrong.