NOLOGIC - Editorial

ad-hoc
cakewalk
cook31
editorial
nologic

#1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

CAKEWALK

PREREQUISITES

Ad Hoc

PROBLEM

We are given several questions. Answer each question such that the answer has no logic, i.e. has no common letters with the corresponding question.

QUICK EXPLANATION

Iterate over all allowed letters. For each letter, check whether it is present in the question. If it is not, then a string consisting of the letter is valid as an answer to the question. If all possible letters are present, then there is no possible answer.

EXPLANATION

There are many ways to solve this problem. However, since this problem appears in a cook-off contest, we obviously want the simplest solution that just works. Here we will present such solution.

The problem asks for an answer (a string) that has no common letters with the corresponding question. Therefore, the simplest answer is just a letter that is not present in the question. We can iterate the letters in the question and mark them as "used", and then iterate all allowed letters and print one that is not marked as "used". If all allowed letters are "used", then there is no answer to the question.

Here is the pseudocode that produces the answer for each question. Note that we have to be aware that lowercase and uppercase letters should be considered equal.

for i := 0 to length(question) - 1:
    used[question*] = true

found := false
for i := 0 to 25:
    if not used['a' + i] and not used['A' + i]:
        found := true
        println('a' + i)
        break
    if not found:
        println('~')

NOTES TO C/C++ USERS

This applies to those that use I/O functions in . Since each question can contain spaces, we can use gets() to read the question. A very common way to do this is as follows:

scanf("%d
", &T);
for (int tc = 0; tc < T; tc++) {
    gets(question);
}

Here we use "%d " format to read the number of test cases and the following new line. This is wrong if the first test case only consists of spaces! The " " format will skip all whitespaces until it finds a non-whitespace character. Therefore, the first test case will not be read at all.

The correct way is to use "%d%*c" format to skip exactly one character (i.e. ' '), or

scanf("%d", &T);
gets(question);
for (int tc = 0; tc < T; tc++) {
    gets(question);
}

SETTER'S SOLUTION

Can be found here.

TESTER'S SOLUTION

Can be found here.


#2

and the judge wasn’t accepting my solution if it had two newlines at the last test case.
took me 3 WA to figure out ###sigh###


#3

@prakhs123 @vinoth03
Common guys! Try to read editorial at least by one eye :slight_smile:


#4

Here we use "%d
" format to read the number of test cases and the following new line. This is wrong if the first test case only consists of spaces! The "
" format will skip all whitespaces until it finds a non-whitespace character. Therefore, the first test case will not be read at all.

The correct way is to use “%d%*c” format to skip exactly one character (i.e. ’
')

Very well explained. Caused me 5 WA, but lesson learnt :slight_smile:


#5

http://www.codechef.com/viewsolution/1851711 please check my code


#6

we can also use a getchar() after the scanf("%d",&t) to read the enter pressed.


#7

#include
#include
#include
using namespace std;
int main()
{
int t;
char question[320];
bool x[26]={false};
int i;
scanf("%d",&t);
while(t–)
{
gets(question);
for(i=0;i<(int)strlen(question);++i)
{
if(isalpha(question*))
{
if(islower(question*))
x[question*-97]=true;
else
x[question*-65]=true;
}
}
bool flag=true;
for(i=0;i<26;++i)
{
if(x*==false)
{
printf("%c
“,i+65);
flag=false;
break;
}
}
if(flag) printf(”~
");
}
return 0;
}

I don’t know why this code is not working can any one tell why?


#8

@amitupadhyay
Your solution has several mistakes.

  1. You should read a new-line character after scanf("%d",&t) as explained in the editorial.
  2. Declaration of bool x[26]={false}; should be moved inside while-loop.

By simply fixing this I’ve got AC:
http://www.codechef.com/viewsolution/1853065

But your code also has another bad place.
You calculate strlen(question) each time in the loop.
Note that strlen() function works in O(N) time.
So your solution is actually has complexity O(N * N).
If constraints would be higher (like question length up to 31415) you would probably get TLE.
It is always better to save the length at some variable like int this fix of your solution:
http://www.codechef.com/viewsolution/1853057


#9

it might be the dumb question but i want to know what’s wrong in writing if(‘a’ <= s* <= ‘z’) (than if(‘a’ <= s* && s* <= ‘z’)) in c? I am getting wrong answer for first case.


#10

@anton_lunyov i have been using scanf("%d ",&t) blindly without knowing how it is working.
“The format will skip all whitespaces until it finds a non-whitespace character” . why does it skips?

also please explain %d%*c format. what is %*c doing ?


#11

can anybody plz help me with my code…
its giving WA…and i m unable to figure it out…
here is my code
http://www.codechef.com/viewsolution/1854752


#12

can anyone tell me what is wrong with my code? I feel that my program is exactly according to the editorial, but it still gives me WA.
http://www.codechef.com/viewsolution/1861051


#13

Why is this problem only available in 3 languages?


#14

What’s problem in this code. Its getting WA.
ideone link


#15

The note in the problem statement clearly indicates that the number of new-lines should be exactly T. Additional new line in the end violates this rule so no wonder :slight_smile:


#16

read the editorial i still didnt get it!


#17

That was one of the insights behind the problem to teach this lesson :slight_smile:


#18

The problem exists in line scanf("%d ", &T);. Please read the editorial explaining the problem with using format specifier "%d
".


#19

sorry !!!


#20

Do we need to print the all letters those are not in the question
or Simply one of them will work?