×

# FBMT - Editorial

Practice

Contest

Setter: Trung Nguyen

Editorialist: Bhuvnesh Jain

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(\text{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)$

Setter's solution

Tester's solution

Editorialist's solution

This question is marked "community wiki".

6★likecs
3.7k1978
accept rate: 9%

19.5k348496535

 1 Nice Editorial answered 12 Feb, 16:15 1●2 accept rate: 0%
 0 what is wrong in my soln .link answered 25 Dec '17, 06:12 88●6 accept rate: 5%
 0 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;iteam1) System.out.println(t2); else if(team1>(n-team1)) System.out.println(t1); T--; } }  } answered 26 Dec '17, 09:42 2★ajmalhsn 1 accept rate: 0% 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 (26 Dec '17, 10:11) kunnu1201★ 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!! (26 Dec '17, 10:12) kunnu1201★
 0 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 answered 26 Dec '17, 11:04 2★antar1 1 accept rate: 0% 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. (28 Dec '17, 00:33) likecs6★
 0 Hello, Can anyone please explain me why my solution is getting WA if i am using FOR loop #include 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>r; if(r==s)a++; else {b++;k=r;} } if(a>b)cout<
 0 Hello, Can anyone please explain me why my solution is getting WA if i am using FOR loop  #include 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>r; if(r==s)a++; else {b++;k=r;} } if(a>b)cout<> s which is not valid (27 Dec '17, 19:23) kunnu1201★ I corrected your solution here's the AC link to your solution https://www.codechef.com/viewsolution/16680712 (27 Dec '17, 19:29) kunnu1201★
 0 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 = []  answered 27 Dec '17, 23:34 2★kalesaur 36●3 accept rate: 33%
 0 Can anyone explain me why it is tle My code https://www.codechef.com/viewsolution/16644182 answered 28 Dec '17, 01:29 23●5 accept rate: 0% 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. (28 Dec '17, 11:35) likecs6★ I had used fast input output during the contest but it is also tle https://www.codechef.com/viewsolution/16644901 (28 Dec '17, 12:07)
 0 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; icount2) { printf("%s\n",a); } else if(count2>count1) { printf("%s\n",b); } else { printf("Draw\n"); } } }  answered 28 Dec '17, 15:49 0★f2014576 1 accept rate: 0%
 0 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 (ab) System.out.println(log[0]); else if (a
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,038
×1,537
×589
×176
×106
×72
×7

question asked: 21 Dec '17, 17:20

question was seen: 2,381 times

last updated: 21 Aug, 15:39