10475 - Help the Leaders

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Re: 10475 - Help the Leaders

Post by stcheung » Thu Jan 15, 2009 7:43 am

As for me, I got my several WA because I didn't follow this:
"Print a blank line after the output for each case."

Frankly I consider the fact that each problem may have its own blank line policy to be quite annoying. ACM should probably standarize this. And might as well standardize how the end of input is conveyed, for instance by specifying the number of test cases right at the beginning instead of checking for EOF or other certain things.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10475 - Help the Leaders

Post by mf » Thu Jan 15, 2009 7:57 am

stcheung wrote:Frankly I consider the fact that each problem may have its own blank line policy to be quite annoying. ACM should probably standarize this.
At ACM ICPC Finals, blank lines at the end of output and trailing whitespace on each line is simply ignored. I don't know why most online judges don't do the same (they live independently of ACM, btw), but this would be a rather nice feature to have.

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10475 - Help the Leaders

Post by Mukit Chowdhury » Sun Oct 21, 2012 4:53 pm

I am getting WA !!! need some input for my following code :(

Code: Select all

Thanks a lot brianfry713..... It's accepted now......... :)
My problem is in mapping.... I have made it accepted using matrix... )
Last edited by Mukit Chowdhury on Sun Oct 21, 2012 9:49 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10475 - Help the Leaders

Post by brianfry713 » Sun Oct 21, 2012 9:02 pm

Input:

Code: Select all

1
8 3 2
WAR
TERROR
PEACE
NUCLEAR-BOMB
HUMAN-RIGHT
FOOD
OIL-CRISIS
EQUAL-RIGHT
WAR OIL-CRISIS
WAR NUCLEAR-BOMB
OIL-CRISIS NUCLEAR-BOMB
AC output:

Code: Select all

Set 1:
NUCLEAR-BOMB EQUAL-RIGHT
NUCLEAR-BOMB HUMAN-RIGHT
NUCLEAR-BOMB TERROR
NUCLEAR-BOMB PEACE
NUCLEAR-BOMB FOOD
EQUAL-RIGHT HUMAN-RIGHT
EQUAL-RIGHT OIL-CRISIS
EQUAL-RIGHT TERROR
EQUAL-RIGHT PEACE
EQUAL-RIGHT FOOD
EQUAL-RIGHT WAR
HUMAN-RIGHT OIL-CRISIS
HUMAN-RIGHT TERROR
HUMAN-RIGHT PEACE
HUMAN-RIGHT FOOD
HUMAN-RIGHT WAR
OIL-CRISIS TERROR
OIL-CRISIS PEACE
OIL-CRISIS FOOD
TERROR PEACE
TERROR FOOD
TERROR WAR
PEACE FOOD
PEACE WAR
FOOD WAR

Check input and AC output for thousands of problems on uDebug!

afruizc
New poster
Posts: 15
Joined: Sat Oct 13, 2012 2:04 am

Re: 10475 - Help the Leaders

Post by afruizc » Tue Dec 04, 2012 1:23 am

The trick is to convert everything to uppercase. Even the given constraints. I got like 5 WA before noticing after converting them, I got AC. You can do that when you read the input.

tiendaotd
New poster
Posts: 12
Joined: Mon Jan 14, 2013 12:21 pm

Re: 10475 - Help the Leaders

Post by tiendaotd » Fri Mar 01, 2013 11:16 am

I got WA because I print only one '\n' character after the last case.

Example output should be :

Code: Select all

Set 1:
007 ABA ABC
^
^
Here "^" is new line.

Chuckrute
New poster
Posts: 5
Joined: Thu Apr 10, 2014 12:32 am

Re: 10475 - Help the Leaders

Post by Chuckrute » Fri Apr 25, 2014 6:02 am

Hey guys!
I'm having RE with this code:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

map <string, int> significados;


//função retirada e modificada do www.cplusplus.com
bool myfunction (const string& first, const string& second) {
        return first.size() > second.size();
    }


void imprime(vector <set <string> > proibidos,vector <string> assuntos, vector <string> &sequencia, int index, int impressos, int limiteimpressos){
   int i,j,k; 
   set <string>::iterator ip;
   bool pode=true;
   
    if(impressos==(limiteimpressos-1)){
      for(i=index;i<assuntos.size();i++){
          for(k=0;k<impressos;k++){
          if(proibidos[significados[sequencia[k]]].count(assuntos[i])){
              pode=false;
          }
          }
          if(pode){
              if(sequencia.size()<(limiteimpressos-1)){
                  sequencia.push_back(assuntos[i]);
              }
              else
          sequencia[limiteimpressos-1]= assuntos[i];
          
          for(j=0;j<limiteimpressos;j++){
              if(j==(limiteimpressos-1))
                cout << sequencia[j];
              else
              cout << sequencia[j]<< " ";
          }
          
          
          cout << endl;
          }
          pode = true;
      }   
    }
    else{
    for(i=index;i<assuntos.size()-(limiteimpressos-impressos-1);i++){
        for(k=0;k<impressos;k++){
          if(proibidos[significados[sequencia[k]]].count(assuntos[i])){
              pode=false;
          }
          }
        if (pode){
            if(sequencia.size()<impressos){
                sequencia.push_back(assuntos[i]);
            }
            else
        sequencia[impressos] = assuntos[i];
        imprime(proibidos,assuntos,sequencia,(i+1),(impressos+1), limiteimpressos);
        }
        pode = true;
    }
    }
    
}

int main(){
    bool primeiro=false;
    int n, t, p, s,i, cont=1;
    scanf("%d", &n);
    getchar();
    vector <string> assuntos, seq;
    string temp, temp2;
    vector <set <string> > proibidos;
    set <string> tempset;
    
    set <string>::iterator ip;
    while (true){
        if(n==0){
            break;
        }
        if(primeiro){
            cout<<endl;
        }
        significados.clear();
        seq.clear();
        proibidos.clear();
        temp.clear();
        assuntos.clear();
        
        scanf ("%d %d %d", &t, &p, &s);
        getchar();
        for(i=0;i<t;i++){
           cin >> temp;
           std::transform(temp.begin(), temp.end(),temp.begin(), ::toupper);
           assuntos.push_back(temp);
           
/*
           proibidos.push_back(tempset);
           significados[temp]=i;
           proibidos[significados[temp]].insert(temp);
*/
           getchar();
           
        }
        sort(assuntos.begin(),assuntos.end());
        std::stable_sort(assuntos.begin(),assuntos.end(),myfunction);
        for(i=0;i<t;i++){
            proibidos.push_back(tempset);
           significados[assuntos[i]]=i;
           proibidos[significados[assuntos[i]]].insert(assuntos[i]);
        }
        
        for(i=0;i<p;i++){
            cin >>  temp;
            std::transform(temp.begin(), temp.end(),temp.begin(), ::toupper);
            cin >> temp2;
            std::transform(temp2.begin(), temp2.end(),temp2.begin(), ::toupper);
            proibidos[significados[temp]].insert(temp2);
            
            proibidos[significados[temp2]].insert(temp);
            getchar();
        }
        for(i=0;i<s;i++){
            seq.push_back("");
        }
        cout<<"Set "<<cont<<":"<<endl;
        cont++;
        imprime(proibidos, assuntos,seq, 0, 0, s);
        //ia=assuntos.begin();
        primeiro = true;
           
            

        
        
        n--;
    }
    
    
    
    
    return 0;
}
Can someone tell me the input that's causing the problem?
Thanks in advance!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10475 - Help the Leaders

Post by brianfry713 » Fri Apr 25, 2014 11:32 pm

Print a blank line after the output for each case, including the last one.
Check input and AC output for thousands of problems on uDebug!

masterzemo
New poster
Posts: 2
Joined: Sat Nov 29, 2014 5:57 am

Re: 10475 - Help the Leaders

Post by masterzemo » Sun Mar 15, 2015 11:27 pm

I took several WA before discovering that s can be larger than n. In these cases, there is no valid speech.

I hope this helps someone.

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 10475 - Help the Leaders

Post by jddantes » Sun Jul 26, 2015 4:15 pm

Why WA?

Code: Select all

#include <bits/stdc++.h>

using namespace std;

bool lexcmp(string a, string b){
	int asz = a.size();
	int bsz = b.size();

	if(asz == bsz)
		return a < b;
	return asz > bsz;
}

set<int> build;
// map<string, set<string>> prohibited;
vector<set<int>> prohibited;
vector<string> input;
map<string, int> indexOf;
vector<string> nameOf;
vector<bool> used;

int N, P, S;
int trackSz;
void f(int s, int index){
	if(!s){
		auto itr = build.begin();
		for(int i = 0; i<trackSz; i++, itr++){
			if(i) printf(" ");
			cout << nameOf[*itr];
		}
		printf("\n");
		return;
	}

	if(index == N){
		return;
	}

	bool found = false;
	// for(int i = 0; i<N; i++){
	// 	if(!used[i]){
	// 		bool skip = false;
	// 		for(auto p : prohibited[i]){
	// 			if(build.count(p)){
	// 				skip = true;
	// 				break;
	// 			}
	// 		}
	// 		if(skip) continue;

	// 		used[i] = true;
	// 		build.insert(i);
	// 		trackSz++;
	// 		f(s-1);
	// 		trackSz--;
	// 		build.erase(i);
	// 		used[i] = false;
	// 	}
	// }
	{
		bool skip = false;
		for(auto p : prohibited[index]){
			if(build.count(p)){
				skip = true;
				break;
			}
		}
		if(!skip){
			build.insert(index);
			trackSz++;
			f(s-1, index+1);
			trackSz--;
			build.erase(index);
		}
	}

	{
		f(s, index+1);
	}
	

	// if(!found){
	// 	auto itr = build.begin();
	// 	for(int i = 0; i<trackSz; i++, itr++){
	// 		if(i) printf(" ");
	// 		cout << nameOf[*itr];
	// 	}
	// 	printf("\n");
	// 	return;
	// }

}

int main(){
	int cases;
	cin >> cases;
	for(int e = 0; e<cases; e++){
		cin >> N >> P >> S;
		trackSz = 0;
		prohibited.assign(N, set<int>());
		used.assign(N, false);
		input.resize(N);
		indexOf.clear();
		nameOf.resize(N);
		for(int i = 0; i<N; i++){
			cin >> input[i];
			for(int j = 0; input[i][j]; j++){
				input[i][j] = toupper(input[i][j]);
			}
		}
		sort(input.begin(), input.end(), lexcmp);
		for(int i = 0; i<N; i++){
			indexOf[input[i]] = i;
			nameOf[i] = input[i];
		}

		for(int p = 0; p<P; p++){
			string strA, strB;
			cin >> strA >> strB;
			int indexA = indexOf[strA];
			int indexB = indexOf[strB];
			prohibited[indexA].insert(indexB);
			prohibited[indexB].insert(indexA);
		}
		printf("Set %d:\n", e+1);
		f(S, 0);
		printf("\n");

	}	

	return 0;
}

Post Reply

Return to “Volume 104 (10400-10499)”