You are not logged in. Please login at www.codechef.com to post your questions!

×

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

Solution Links

Setter's solution

Tester's solution

Editorialist's solution

This question is marked "community wiki".

asked 21 Dec '17, 17:20

likecs's gravatar image

6★likecs
3.7k1978
accept rate: 9%

edited 25 Dec '17, 21:13

admin's gravatar image

0★admin ♦♦
19.5k348496535


12next »

Nice Editorial

link

answered 12 Feb, 16:15

chiranjit97's gravatar image

3★chiranjit97
12
accept rate: 0%

what is wrong in my soln .link

link

answered 25 Dec '17, 06:12

lokesh2002's gravatar image

4★lokesh2002
886
accept rate: 5%

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[i]=br.readLine();
        }
        t1=str[0];
        t2=str[1];  
        for(i=0;i<n;i++){
            if(t1.equals(str[i]))   
                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--;


    }
}

}

link

answered 26 Dec '17, 09:42

ajmalhsn's gravatar image

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★

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

link

answered 26 Dec '17, 11:04

antar1's gravatar image

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★

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;

    }
}
link

answered 27 Dec '17, 19:12

shivg7706's gravatar image

3★shivg7706
1
accept rate: 0%

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;



    }
}
link

answered 27 Dec '17, 19:16

shivg7706's gravatar image

3★shivg7706
1
accept rate: 0%

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

cin >> 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★

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 = []
link

answered 27 Dec '17, 23:34

kalesaur's gravatar image

2★kalesaur
363
accept rate: 33%

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

link

answered 28 Dec '17, 01:29

manaranjanfav's gravatar image

4★manaranjanfav
235
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) manaranjanfav4★

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\n",a);
        }
        else if(count2>count1)
        {
            printf("%s\n",b);
        }
        else {
            printf("Draw\n");
        }
    }
}
link

answered 28 Dec '17, 15:49

f2014576's gravatar image

0★f2014576
1
accept rate: 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 (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()?

link

answered 28 Dec '17, 16:14

blazekill's gravatar image

2★blazekill
1
accept rate: 0%

okay I found the solution there was a memory leak which happens due to multiple buffer reader objects sharing the same input stream so I declared a static field like

static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

and it worked fine

(28 Dec '17, 20:56) blazekill2★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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