10475 - Help the Leaders

[stcheung]

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]

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]

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... )

[brianfry713]

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

[afruizc]

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]

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]

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]

Print a blank line after the output for each case, including the last one.

[masterzemo]

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]

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;
}