FBMT - Editorial

Problem Link

Practice

Contest

Setter: Trung Nguyen

Tester: Hasan Jaddouh

Editorialist: Bhuvnesh Jain

Difficulty

CAKEWALK

Prerequisites

Looping Techniques

Problem

Find the team with the maximum number of goals, or report if there is a “Draw”.

Explanation

The problem simply states to count the number of goals scored by each team and report the name of the winner team. Thus, if the first team scores x goals, then the other team scores (N - x) goals (because the total number of goals scored were N). Clearly, the winner is the one with the higher number of goals. To count the number of goals by the first team, we simply iterate through the list of team which scored the next goal and compare if it has the same name as the first team, then, we increment the counter. Now, we simply check using “If” conditions, whether the first team won or the second team won or there is a draw.

The time complexity of this approach will be the sum of length of strings in input (per test case) as each string comparison takes a total of O( ext{length of string}). This is the most optimal algorithm for even taking the input takes same time asymptotically.

For details, refer to the editorialist solution below.

Time Complexity

O(\sum_{i=1}^{i=N} |S_i|), per test case, where |S| = length of string S.

Space Complexity

O(N)

Solution Links

Setter’s solution

Tester’s solution

Editorialist’s solution

1 Like

My code is not getting accepted and saying it’s NZEC error in java

import java.util.;
import java.io.
;
class football{
public static void main(String[] args)throws Exception{
int T,n;

	BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	T=Integer.parseInt(br.readLine());
	while(T>0){
		n=Integer.parseInt(br.readLine());
		int team1=0;
		String str[]=new String[n];
		String t1,t2;
		int i;
		
		for(i=0;i<n;i++){
			str*=br.readLine();
		}
		t1=str[0];
		t2=str[1];	
		for(i=0;i<n;i++){
			if(t1.equals(str*))	
				team1++;
		}
		if((n-team1)==team1)
			System.out.println("Draw");
		else if((n-team1)>team1)
			System.out.println(t2);
		else if(team1>(n-team1))
			System.out.println(t1);
		T--;
		
		
	}
}

}

Hello, Can anyone please explain me why my solution is getting TLE. This solution is running perfectly in my PC as well as other online IDEs but in codechef IDE it is showing TLE.

My solution: Here

Hello, Can anyone please explain me why my solution is getting WA if i am using FOR loop

    #include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		string s,r,k;
		int n,a=1,b=0;
		cin>>n;
		cin>>s;
		for(int i=0;i<n-1;i++)
		{
			cin>>r;
			if(r==s)a++;
			else {b++;k=r;}
		}
		if(a>b)cout<<s<<endl;
		else if(a<b)cout<<k<<endl;
		else cout<<"Draw"<<endl;
 
 
 
	}
}

Here is my python code. It works, but I think it could be so much better. Any feedback?

n = int(input())
team1 = ""
team1count = 0
team2 = ""
team2count = 0
scoreArr = []

for x in range(n):
    testcaseNumber = int(input())
    for y in range(testcaseNumber):
        scoreArr.append(input())
    for z in scoreArr:
        if team1 != "" and team2 != "":
        continue
    elif team1 == "":
           team1 = z
        team1count = scoreArr.count(z)
    elif team2 == "" and z != team1:
        team2 = z
        team2count = scoreArr.count(z)
if team1count == team2count:
    print("Draw")
elif team1count > team2count:
    print(team1)
else:
    print(team2)
team1 = ""
team2 = ""
team1count = 0
team2count = 0
scoreArr = []

Can anyone explain me why it is tle
My code https://www.codechef.com/viewsolution/16644182

My submission is giving a wrong answer and I can’t seem to know why. Can anyone please help me out?

int main()
{

    int i, t, j, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        char a[21],b[21];
        int count1=0, count2=0;


        scanf("%s", a); //for the first team's name
        count1++;

        for(i=1; i<n; i++)
        {
            scanf("%s", b);
            if(strcmp(a,b)==0)
            {
                count1++;
            }
            else
            {
                count2++;
            }
        }
        if(count1>count2)
        {
            printf("%s

“,a);
}
else if(count2>count1)
{
printf(”%s
",b);
}
else {
printf("Draw
");
}
}
}

I have this code in java

import java.io.*;

public class Main
{
    static void logInput(String[] log,int n) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int a=0,b=0;
        for (int i = 0; i < n; i++)
        {
            String s = br.readLine();
            if (log[0]==null)
            {
                a++;
                log[0] = s;
            }
            else if (log[0].equals(s))
                a++;
            else if (log[1]==null)
            {
                b++;
                log[1] = s;
            }
            else if (log[1].equals(s))
                b++;
        }
        if (a>b)
            System.out.println(log[0]);
        else if (a<b)
            System.out.println(log[1]);
        else if(a==b)
            System.out.println("Draw");
    }

    static void testCase() throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] log = new String[2];
        logInput(log,n);
    }

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++)
        {
            testCase();
        }
        br.close();
    }
}

and I get a nzec now if I combine all the function i.e do everything in main() I get correct ans

import java.io.*;
 
public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++)
        {
            int n = Integer.parseInt(br.readLine());
            String[] log = new String[2];
            int a=0,b=0;
            for (int k = 0; k < n; k++)
            {
                String s = br.readLine();
                if (log[0]==null)
                {
                    a++;
                    log[0] = s;
                }
                else if (log[0].equals(s))
                    a++;
                else if (log[1]==null)
                {
                    b++;
                    log[1] = s;
                }
                else if (log[1].equals(s))
                    b++;
            }
            if (a>b)
                System.out.println(log[0]);
            else if (a<b)
                System.out.println(log[1]);
            else if(a==b)
                System.out.println("Draw");
        }
        br.close();
    }
} 

I don’t understand how dividing it into functions can cause a nzec do I need to catch the exceptions thrown by other methods except main()?

Hello:

My code works on online IDE but is not getting accepted and saying it’s NZEC error in Python

¿Can anybody tell me why?

n1=int(input().strip())
for i in range(n1):
    arr=[]
    n2 = int(input().strip())
    for j in range(n2):
        arr_t = str(input().strip())
        arr.append(arr_t)
    arr_uniq=list(set(arr))
    if (arr.count(arr_uniq[0])>arr.count(arr_uniq[1])):
        print(arr_uniq[0])
    elif (arr.count(arr_uniq[0])<arr.count(arr_uniq[1])):
        print(arr_uniq[1])
    else:
        print("Draw")

its showing run time error?what is the error?its working well for test cases.
#include
#include
using namespace std;

int main()
{
int t,i,x;
cin>>t;
while(t–)
{
int count1=0,count2=0;
cin>>x;
string s[x];
for(i=0;i<x;i++)
cin>>s*;
string a=s[0];
string b;
for(i=0;i<x;i++)
{
if(s*==a)
count1++;
else
{
b=s*;
count2++;
}
}
if(count1>count2)
cout<<a<<endl;
else if(count2>count1)
cout<<b<<endl;
else
cout<<“Draw”<<endl;
}
return 0;
}

I am getting WA in here. the code works fine with no error. Help is appreciated !!. i request codechef team to give data for different test case which is input for our submission. here's my code

https://www.codechef.com/viewsolution/17078404

Nice Editorial

1 Like

#include

//my solution in c++enter code here

 using namespace std;

int main()
{
long long int t;
cin>>t;

for(long long i=0;i<t;i++){
    long long int n;
    cin>>n;
    long long x=0,y=0;
    string temp,b,temp1;
    for(long long j=0;j<n;j++){
        if(x==0){
            cin>>b;
            temp=b;
            x=x+1;//x=1
            continue;
        }
        if(x>=1){
            cin>>b;
            if(b!=temp){
                y=y+1;
                temp1=b;
                
            }
            if(b==temp){
                x=x+1;
                
            }
            
        }
        
        
        
    }
    if(x>y){cout<<temp<<endl;};
    if(x==y){cout<<"Draw"<<endl;};
    if(x<y){cout<<temp1<<endl;};
    
    
}

}

Keep in mind, N can be 0 too and then when you do this

t1=str[0];

t2=str[1];

is not valid!! and that’s the reason you getting NZEC

And first and second String can be same too so if you have input

5

fe

fe

rem

rem

rem

your code’s not going to work

you can check out my code if you want

https://www.codechef.com/viewsolution/16657502 hope this helps!!

n can be 0, so if it is then you’re asking for a string

cin >> s

which is not valid

I corrected your solution here’s the AC link to your solution

https://www.codechef.com/viewsolution/16680712

N = 0 can also be present, in that case while loop runs will give you tle, as it runs for 2*INT_MAX iterations, after which it loops back to 0 and breaks.

Input files are large and cin/cout are the slowest input/output streams. So, use the lines “ios_base::sync_with_stdio(false);” in your code. See editorialist submission for details.

I had used fast input output during the contest but it is also tle
https://www.codechef.com/viewsolution/16644901