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

×

NOLOGIC - Editorial

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[i]] = 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 <stdio.h>. 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\n", &T);
for (int tc = 0; tc < T; tc++) {
    gets(question);
}

Here we use "%d\n" 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 "\n" 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. '\n'), 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.

This question is marked "community wiki".

asked 18 Feb '13, 00:01

fushar's gravatar image

3★fushar ♦♦
16345853
accept rate: 0%

edited 18 Feb '13, 02:04

admin's gravatar image

0★admin ♦♦
19.8k350498541

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

(18 Feb '13, 00:22) jangwa2★

Simply one of them will work too.

(18 Feb '13, 02:07) anton_lunyov ♦6★

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

link

answered 18 Feb '13, 00:10

anton_lunyov's gravatar image

6★anton_lunyov ♦
6.7k62119138
accept rate: 12%

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

(18 Feb '13, 00:07) prakhs1234★

read the editorial i still didnt get it!

(18 Feb '13, 00:16) prakhs1234★
1

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

(18 Feb '13, 00:19) prakash15293★

sorry !!!!!

(18 Feb '13, 00:20) prakhs1234★

@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

link

answered 18 Feb '13, 18:16

anton_lunyov's gravatar image

6★anton_lunyov ♦
6.7k62119138
accept rate: 12%

@anton_lunyov My bad :( thankyou very much

(18 Feb '13, 18:22) amitupadhyay2★

silly mistake there @amitupadhyay in the for loop, @anton_lunyov pointed it right. Really, one ignore these things in a tight time bound competition.

(19 Feb '13, 01:31) bugkiller3★

Here we use "%d\n" 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 "n" 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. '\n')

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

link

answered 18 Feb '13, 00:16

prakash1529's gravatar image

3★prakash1529
16625
accept rate: 0%

edited 19 Feb '13, 01:38

betlista's gravatar image

3★betlista ♦♦
16.9k49115225

4

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

(18 Feb '13, 00:19) anton_lunyov ♦6★

And i thought codechef was at fault for not accepting my solution.Quite an easy problem with a twisting catch.Well set Admin.

(18 Feb '13, 02:09) sparshgunner124★
#include<cstdio>
#include<cstring>
#include<cctype>
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[i]))
            {
                if(islower(question[i]))
                    x[question[i]-97]=true;
                else
                    x[question[i]-65]=true;
            }
        }
        bool flag=true;
        for(i=0;i<26;++i)
        {
            if(x[i]==false)
            {
                printf("%c\n",i+65);
                flag=false;
                break;
            }
        }
        if(flag) printf("~\n");
    }
    return 0;
}

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

link

answered 18 Feb '13, 18:04

amitupadhyay's gravatar image

2★amitupadhyay
1.4k92241
accept rate: 14%

Your code is not working, see the test case here - http://ideone.com/LTvWXq

(19 Feb '13, 00:32) betlista ♦♦3★

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###

link

answered 18 Feb '13, 00:06

aichemzee's gravatar image

4★aichemzee
42061224
accept rate: 3%

edited 18 Feb '13, 00:08

1

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

(18 Feb '13, 00:08) anton_lunyov ♦6★

this was never a concern untill today. I mean I always appended ans+"n" and in the end used System.out.println() which caused an additional newline. And yes, i saw that T newline thing, and used the .print() instead. And bingo AC. Still, this kindov thing was rather lame. Gave me 3 WA's.

(18 Feb '13, 02:05) aichemzee4★

OK. Next time I will try to write kinder judge from this perspective. At least existing special judge was easy to code. While allowing all possible new-lines features that contestants are used to is not so trivial to figured it out.

Try to solve something on UVA. They have very strict judge as well but no for all problems.

(18 Feb '13, 02:09) anton_lunyov ♦6★

I meant it shouldn't matter whatever i print after the T required output lines. Ideally those shouldn't be processed. And statistically that should make the judge more efficient :P

(18 Feb '13, 02:14) aichemzee4★

"Ideally those shouldn't be processed." It is completely wrong. The judge should validate the full conformation of the answer to the output format. If for example in the challenge problem you need to print N followed by N lines describing some operations but you print N+1 lines with operation on the last line then it is wrong and actually AC could only make you worse since you may get low score while thinking that all is right with the solution.

(18 Feb '13, 15:58) anton_lunyov ♦6★

I seriously don't feel the above explaination you gave justifies this being rejected

StringBuilder out=new StringBuilder();
while(t-->0){
    // ...
    out.append(ans+" \n");
}
System.out.println(out);
(19 Feb '13, 00:26) aichemzee4★

@aichemzee: your code simply contains T+1 x \n and as stated in statement

Special judge is very strict for this problem and check your output character-by-character. Be sure that you follow the mentioned output format precisely. For instance, your output should contain exactly T new-line characters (ASCII code 10) - one after each answer.

so it's incorrect...

(19 Feb '13, 00:40) betlista ♦♦3★

@anton_lunyov thanks for such problem, I hope a lot of coders learnt lesson in this contest

If it's specified in statement so precisely as in this I think it is perfectly fine to reject such submissions.

On the other hand I prefer no so strict judge, for example if one have to print N numbers in line, typically it's ok when there is space after the last one or so, because one can use FOR(i,0,N) printf("%d ", a[i]) instead of printf("%d", a[0]); FOR(i,1,N) printf(" %d", a[i]) and AFAIK in ACM contest there is special judgement result "wrong format" that is shown sometime in such cases...

(19 Feb '13, 00:46) betlista ♦♦3★

@betlista As I said above try to solve something on UVA.
After struggling to solve some simple problem you will reconsider your opinion :)
To output N space separated integers you could use code
FOR(i,0,N) printf("%d%c", a[i], i<N-1?' ':'\n')
So nothing ugly.

@aichemzee Usually special judge at codechef ignores extra white spaces.
So not need to worry about that in the future.

(19 Feb '13, 01:05) anton_lunyov ♦6★

@anton_lunyov: thanks for your tip, good point ;-) I just said I prefer no so strict judge, but I'm always sticking with format specified in statement, because I never know if the judge is or is not strict ;-)

(19 Feb '13, 01:13) betlista ♦♦3★
showing 5 of 10 show all
link

answered 18 Feb '13, 00:23

jangwa's gravatar image

2★jangwa
17229
accept rate: 10%

2

Guys! Why you all even not try to look through the editorial?
Did you see section "NOTES TO C/C++ USERS" there?

(18 Feb '13, 00:25) anton_lunyov ♦6★

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

link

answered 18 Feb '13, 14:27

anu_chat's gravatar image

2★anu_chat
6112
accept rate: 0%

but if you are using such low level functions you should handle case in which line is ending with \r\n...

(19 Feb '13, 00:34) betlista ♦♦3★

Actually both ways with scanf("%d%*c") and with getchar() do not handle the case with '\r\n'.
So the most general way is to use gets() or do getchar() / scanf("%c") in a loop.

(19 Feb '13, 01:08) anton_lunyov ♦6★

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

link

answered 18 Feb '13, 21:29

anil09's gravatar image

1★anil09
36149
accept rate: 0%

edited 18 Feb '13, 21:29

1

Expression ('a' <= s[i] <= 'z') is equivalent to ('a' <= s[i]) <= 'z'.
So it compares bool value ('a' <= s[i]) with char value 'z'.
Hence, it casts both values to int: 'z' to 122 and
('a' <= s[i]) to 0 if it is false or to 1 if it is true.
So ('a' <= s[i] <= 'z') is always true :)

(18 Feb '13, 21:33) anton_lunyov ♦6★

@anton_lunyov i have been using scanf("%d\n",&t) blindly without knowing how it is working. "The \n 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 ?

link

answered 18 Feb '13, 23:46

shimanshu's gravatar image

2★shimanshu
13
accept rate: 0%

edited 19 Feb '13, 00:29

betlista's gravatar image

3★betlista ♦♦
16.9k49115225

P.S. the ascii character 92 and '*' is not working in comments here.

(18 Feb '13, 23:48) shimanshu2★

it is, but you have to realize what markdown formatting is doing with it...

(19 Feb '13, 00:28) betlista ♦♦3★

@shimanshu Refer to this:
http://www.cplusplus.com/reference/cstdio/scanf/

Search for "Whitespace character: the function will read" and then for "An optional starting asterisk indicates" at this page to clear your doubts.

(19 Feb '13, 01:12) anton_lunyov ♦6★

hm, now I realized, that %d%*c is probably a typo, @anton_lunyov, can you please confirm that?

(19 Feb '13, 01:26) betlista ♦♦3★

Why do you think so?
scanf("%d%*c",&T) will exactly input T and skip the next character after T.

(19 Feb '13, 01:30) anton_lunyov ♦6★

Simply I didn't know about * sub-specifier, thanks for clarification ;-)

(19 Feb '13, 01:36) betlista ♦♦3★
showing 5 of 6 show all

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

link

answered 19 Feb '13, 19:00

nikhil123's gravatar image

3★nikhil123
35338
accept rate: 0%

http://www.codechef.com/viewsolution/1854800 see this i just changed your code

scanf("%d",&t);//instead of scanf("%d\n",&t);
gets(s);//to read the new line

and i got an AC

(19 Feb '13, 19:10) amitupadhyay2★

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

link

answered 24 Feb '13, 15:36

sudharkj's gravatar image

3★sudharkj
5137
accept rate: 0%

space is not a letter. If question contains all possible letters but does not contain spaces you still need to output ~

(24 Feb '13, 15:41) anton_lunyov ♦6★

so does it mean that a question containing spaces can have an answer with spaces in it?

(24 Feb '13, 17:47) sudharkj3★

Why is this problem only available in 3 languages?

link

answered 22 Oct '15, 02:14

yuliyan's gravatar image

0★yuliyan
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,852
×1,688
×968
×8
×5

question asked: 18 Feb '13, 00:01

question was seen: 6,438 times

last updated: 22 Oct '15, 02:14