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

×

SUPVIL - Editorial

PROBLEM LINK:

Practice
Contest

Author: Pawel Kacprzak
Tester: Misha Chorniy
Editorialist: Pawel Kacprzak

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Basic programming

PROBLEM:

For a given list $N$ people, where each is either a superhero or a villain, joining the fight between superheroes and villains in the given order, decide which side wins or if the fight ends up with a draw. Superheroes win immediately at the earliest time when there are $2$ more superheroes fighting than villains. Villains win immediately at the earliest time when there are $3$ more villains fighting than superheroes. If none of these cases happens, then the fight results in a draw.

QUICK EXPLANATION:

Whenever a person joins the fight check if one of the sides wins. If yes, print the name of winning group, otherwise continue. If no side wins after all people joined, print draw.

EXPLANATION:

Solutions to both subtasks are based on the approach described in quick explanation, but they differ complexity of checking if one side wins.

Subtask 1

In the first subtask $N$ is at most $500$, so after every person joining the fight, one can count the number of superheroes already fighting and villains already fighting, and then decide if either of the sides wins. This results in $O(N^2)$ solution, because for each of $N$ people joining the fight, in $O(N)$ time we are counting the number of superheroes and villains already fighting.

Subtask 2

In the second subtask $N$ is at most $10^5$, so counting people from the scratch after every joining person will take too much time. However this can be easily avoided by keeping track of counters of superheroes and villains already fighting. After each person joining the fight, we increment exactly one of these counters depending on the type of the joining person and check if either group wins using these counters. This approach works in $O(N)$ time.

AUTHOR'S AND TESTER'S SOLUTIONS:


Setter's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

asked 31 Dec '16, 17:39

pkacprzak's gravatar image

5★pkacprzak ♦♦
75485097
accept rate: 12%

edited 31 Dec '16, 22:35

admin's gravatar image

0★admin ♦♦
19.8k350498541


What's the bug in my solution?

#include<stdio.h>
#include<string.h>
int main(){
    int t; long long i,n,h,v,size_of_names; char names[16];
    scanf("%d",&t);
    while(t--){
        size_of_names = 0; h = v = 1;
        scanf("%lld",&n);
        for(i=0; i<n; i++){
            scanf("%s",&names);
        size_of_names = strlen(names);
        if(names[size_of_names-3] == 'm' && names[size_of_names-2] == 'a' && names[size_of_names-1] == 'n') h++;
        else v++;
        if(h == v+2){
                printf("superheroes"); break;
        }
        else if(h == v-3){
                printf("villains"); break;      
} } if(h == v) printf("draw"); printf("\n"); } return 0; }

link

answered 31 Dec '16, 22:35

aim_ioi's gravatar image

2★aim_ioi
363
accept rate: 6%

edited 31 Dec '16, 22:36

At the end h may not be equal to v ,but it will still be considered as draw

(31 Dec '16, 22:42) tihorsharma1232★

you are breaking prematurely from the loop before scanning all the inputs of the test case. Suppose for t=2, and t=1 has 10 words and t=2 has 6 words. and if you are breaking after 5th word .. file pointer is at 6th word, so at t=2 it will read 6th word instead of 11th word..

(01 Jan '17, 12:36) pankajkhan5★

Please move the problem to practice section

link

answered 31 Dec '16, 22:41

tihorsharma123's gravatar image

2★tihorsharma123
49918
accept rate: 15%

Yeah please move the problem to practice section.

link

answered 01 Jan '17, 08:29

aim_ioi's gravatar image

2★aim_ioi
363
accept rate: 6%

The question cannot be opened since last night. I've been waiting for the question to accept submissions but it shows "Problem is not visible now. Please try again later."

link

answered 01 Jan '17, 09:42

iamravitejag's gravatar image

1★iamravitejag
1
accept rate: 0%

Please move the problem to practice section

link

answered 01 Jan '17, 12:46

prayas_sahni's gravatar image

1★prayas_sahni
311
accept rate: 0%

/dont use break; beacause user may enter more names; instead do this/

include<stdio.h>

include<string.h>

int main(){ int n,i,j,t,k; char a[15]; scanf("%d",&t); for(i=0;i<t;i++){ int="" s="0,v=0,flag=0;" scanf("%d",&n);="" for(j="0;j&lt;n;j++){" scanf("%s",a);="" k="strlen(a);" if(k="">=3&&a[k-3]=='m'&&a[k-2]=='a'&&a[k-1]=='n') s++; else v++;

    if(flag==0){
            if((s-v)==2){
        flag=1;
    }
    if((v-s)==3){
        flag=2;
    }
}
}
if(flag==1){
    printf("superheroes\n");
}
if(flag==2){
     printf("villains\n");
}
if(flag==0){
    printf("draw\n");
}

}

return 0; }

link

answered 01 Jan '17, 12:48

ktcoder's gravatar image

4★ktcoder
212
accept rate: 0%

Can anyone find what's wrong with my code :

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

int main()
{
     int T;
     cin>>T;
     while(T--){
        int h = 1, v = 1;
        int n;
        int flag = 0;
        cin>>n;
        vector<string> vs;
        while(n--){
            string s;
            cin>>s;
            vs.push_back(s);
        }
        for(int i = 0; i < vs.size(); i++){
            if(vs[i].find("man") != string::npos)
                    h += 1;
            else
                    v += 1;
            if(h - v == 2){
                cout<<"superheroes"<<endl;
                flag = 1;
                break;
            }
            else if(v - h == 3){
                cout<<"villains"<<endl;
                flag = 1;
                break;
            }
        }
        if(flag != 1){
            cout<<"draw"<<endl;
        }
     }
}
link

answered 01 Jan '17, 16:01

rinem's gravatar image

3★rinem
213
accept rate: 0%

edited 01 Jan '17, 16:03

Where is the bug in my code?

include<iostream>

include<string>

using namespace std; int main() { int n, k, i, o, p, count, flag, counth, countv, w, countvv, counthh; string person, key; cin >> n; key = "woman"; while (n--) { cin >> k; counth = 0; countv = 0; countvv = 0; counthh = 0; for (i = 0; i < k; i++) { flag = 0;

        w = 4;
        cin >> person;
        for (o = 0; person[o] != '\0'; o++);
        count = 0;
        for (p = o - 1; p >= 0; p--)
        {
            if (person[p] == key[w])
            {
                count++;
            }
            w--;
            if (w == -1)
            {
                break;
            }
        }
        if (count == 3 || count == 5)
        {
            flag = 1;

        }
        if (flag == 1)
        {
            counth++;
        }
        else {
            countv++;
        }

        if (counth - countv == 2 && countvv != 1)
        {
            if (counthh == 0)
            {
                counthh++;
            }
        }
        if (countv - counth == 3 && counthh != 1)
        {
            if (countvv == 0)
            {
                countvv++;
            }
        }

    }
    if (counthh>0)
    {
        cout << "superheroes" << endl;
    }

    else if (countvv>0) {
        cout << "villains" << endl;
    }
    else {
        cout << "draw" << endl;
    }


}

return 0;

}

link

answered 01 Jan '17, 19:28

abhi870's gravatar image

3★abhi870
1
accept rate: 0%

I'm getting a runtime error (NZEC), can't figure out why. Please point out what's wrong with my code.

t = int(input())
for i in range(t):
        superheroes = 1
        villains = 1
        n = int(input())
        flag = 0
        for j in range(n):
                l = raw_input()
                a = len(l)
                b = l[a-3:a]
                if (b == "man"):
                        superheroes += 1
                else:
                        villains += 1
                if (superheroes  - villains == 2):
                        flag += 1
                        print ("superheroes")
                        break
                elif (villains - superheroes == 3):
                        flag += 1                                
                        print ("villains")
                        break
        if (flag == 0):
                print ("draw")

Here's the link to my submission: https://www.codechef.com/viewsolution/12387811

link

answered 02 Jan '17, 10:27

iamravitejag's gravatar image

1★iamravitejag
1
accept rate: 0%

edited 02 Jan '17, 10:29

Pleaese tell me where is the bug in my solution. I have tried a lot but I am getting wrong answer. Please help me.

#include<stdio.h>
#include<string.h>

int strstr1(char *t)
{
int len=strlen(t);
if(len>=3&&t[len-1]=='n'&&t[len-2]=='a'&&t[len-3]=='m')
    return 1;
if(len>=5&&t[len-1]=='n'&&t[len-2]=='a'&&t[len-3]=='m'&&t[len-4]=='o'&&t[len-5]=='w')
    return 1;
return 0;
}

int main()
{
int var,test,n;
char t[100];
scanf("%d",&test);
while(test--)
{
    scanf("%d",&n);
    var=0;
    while(n--)
    {
        scanf("%s",t);
        if(strstr1(t))
        {
            var++;
        }
        else
        {
            var--;
        }

    if(var==2)
    {
        printf("superheroes\n");
        break;
    }
    else if(var==-3)
    {
        printf("villains\n");
        break;
    }

    }
    if(var!=-3&&var!=2)
    {
        printf("draw\n");
    }
}
return 0;
}
link

answered 02 Jan '17, 11:58

rohitsinghal4u's gravatar image

3★rohitsinghal4u
1
accept rate: 0%

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,875
×1,695
×81
×29
×6

question asked: 31 Dec '16, 17:39

question was seen: 1,223 times

last updated: 02 Jan '17, 11:58