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

×

CNOTE - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sunny Aggarwal
Tester: Hiroto Sekido
Editorialist: Kevin Atienza

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Basic programming

PROBLEM:

Chef has a poem that fits in X pages, but his notebook has only Y pages. So he wants to buy another notebook so that he can finish writing the poem. There are N notebooks for sale and the ith notebook has Pi pages and costs Ci rubles. Chef only has K rubles to spend.

Is it possible for Chef to finish writing his poem?

EXPLANATION:

You simply need to check each notebook if its price is not greater than K and it has at least X - Y pages (because we need X pages but we already have Y pages, we need X - Y more pages). That being said, many contestants still got it wrong, so we'll describe here some common mistakes, and a few suggestions on how to debug and prevent these mistakes from happening in the future.

First, we include implementations in three popular programming contest languages.

C++ code

#include <iostream>
using namespace std;
// allocate more than necessary
int P[111111];
int C[111111];
int main() {
    int T;
    cin >> T;
    for (int cas = 1; cas <= T; cas++) {
        // we use 'cas' because 'case' is a keyword
        int X, Y, K, N;
        cin >> X >> Y >> K >> N;
        bool found = false;
        for (int i = 0; i < N; i++) {
            cin >> P[i] >> C[i];
        }
        for (int i = 0; i < N; i++) {
            if (P[i] >= X - Y && C[i] <= K) {
                found = true;
                break;
            }
        }
        cout << (found ? "LuckyChef" : "UnluckyChef") << '\n';
    }
}

Note that we used '\n' instead of endl, because endl forces a flush, which is unnecessary in our case and significantly slows down our program, causing TLE in the second subtask.

Actually, there is no need to collect books in an array, because we can process each notebook on the fly. thus we can also do the following:

#include <stdio.h>
int main() {
    int T;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        int X, Y, K, N;
        scanf("%d%d%d%d", &X, &Y, &K, &N);
        bool found = false;
        for (int i = 0; i < N; i++) {
            int P, C;
            scanf("%d%d", &P, &C);
            if (P >= X - Y && C <= K) {
                found = true;
            }
        }
        printf(found ? "LuckyChef\n" : "UnluckyChef\n");
    }
}

We use C-style I/O here (printf/scanf) just to illustrate. Also, note that we removed the "break" statement because we need to finish taking all input lines.

Java code

import java.util.Scanner;
public class Main {
    public static void main(String args[]) throws Exception {
        // "throws Exception" is not recommended in real life, but is
        // very convenient in algorithmic contests!
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int cas = 1; cas <= T; cas++) {
            int X = sc.nextInt();
            int Y = sc.nextInt();
            int K = sc.nextInt();
            int N = sc.nextInt();
            boolean found = false;
            for (int i = 0; i < N; i++) {
                int P = sc.nextInt();
                int C = sc.nextInt();
                if (P >= X - Y && C <= K) {
                    found = true;
                }
            }
            System.out.println(found ? "LuckyChef" : "UnluckyChef");
        }
    }
}

Note that java.util.Scanner provides an easy way to tokenize and read the input. However, for problems with huge inputs and strict time limits (such as the current problem!), it is not recommended because it is slow. Instead, one should use BufferedReader, like so:

import java.io.*;
public class Main {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int cas = 1; cas <= T; cas++) {
            String[] parts = br.readLine().trim().split("\\s+"); // split on whitespace
            int X = Integer.parseInt(parts[0]);
            int Y = Integer.parseInt(parts[1]);
            int K = Integer.parseInt(parts[2]);
            int N = Integer.parseInt(parts[3]);
            boolean found = false;
            for (int i = 0; i < N; i++) {
                parts = br.readLine().trim().split("\\s+");
                int P = Integer.parseInt(parts[0]);
                int C = Integer.parseInt(parts[1]);
                if (P >= X - Y && C <= K) {
                    found = true;
                }
            }
            System.out.println(found ? "LuckyChef" : "UnluckyChef");
        }
    }
}

Python code

T = input()
for cas in xrange(1,T+1):
    X, Y, K, N = map(int, raw_input().strip().split())
    books = []
    for i in xrange(N):
        P, C = map(int, raw_input().strip().split())
        books.append((P, C))
    for P, C in books:
        if P >= X - Y and C <= K:
            print "LuckyChef"
            break
    else:
        print "UnluckyChef"

Note that the python code has a bit of different flavor, specifically the for..else statement. The advantage of it is that there is no more need for a found flag. However, we now have to collect the data in a list.

Common mistakes

Here we list down common mistakes made by the contestants. Note that many of these mistakes apply to most other problems too, and although they are made more frequently by newbies, they occasionally are made by veterans too.

  • Writing out the if condition incorrectly. Here are a few examples (they are all wrong!):

    • P > X - Y && C <= K
    • P >= X - Y && C < K
    • P >= X - Y || C <= K
    • P >= X + Y && C <= K
    • P >= Y - X && C <= K
    • P - Y >= X && C <= K
  • Failing to reinitialize some variables. for example, if you have a flag saying that you found a notebook, then failing to initialize it back to false will most likely mean "WA". For example, the ff is wrong:

    import java.io.*;
    public class Main {
        public static void main(String args[]) throws Exception {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int T = Integer.parseInt(br.readLine());
            boolean found = false;
            for (int cas = 1; cas <= T; cas++) {
                String[] parts = br.readLine().trim().split("\s+");
                int X = Integer.parseInt(parts[0]);
                int Y = Integer.parseInt(parts[1]);
                int K = Integer.parseInt(parts[2]);
                int N = Integer.parseInt(parts[3]);
                for (int i = 0; i < N; i++) {
                    parts = br.readLine().trim().split("\s+");
                    int P = Integer.parseInt(parts[0]);
                    int C = Integer.parseInt(parts[1]);
                    if (P >= X - Y && C <= K) {
                        found = true;
                    }
                }
                System.out.println(found ? "LuckyChef" : "UnluckyChef");
            }
        }
    }

Note that the found variable is not reinitialized to false for every test case, which means that when it prints LuckyChef once, it will continue doing so for all subsequent cases. This even fails the sample input!

  • Breaking out of the loop early, without collecting all the input lines. Take a look at the following code:
    #include <iostream>
    using namespace std;
    int P[100000];
    int C[100000];
    int main() {
        int T;
        cin >> T;
        for (int cas = 1; cas <= T; cas++) {
            int X, Y, K, N;
            cin >> X >> Y >> K >> N;
            bool found = false;
            for (int i = 0; i < N; i++) {
                cin >> P[i] >> C[i];
                if (P[i] >= X - Y && C[i] <= K) {
                    found = true;
                    break;
                }
            }
            cout << (found ? "LuckyChef" : "UnluckyChef") << '\n';
        }
    }

The problem with this code is that if you found a good notebook early on, it immediately breaks out of the loop, failing to read all (Pi, Ci) pairs. So it fails to read the next case properly, possibly causing TLE/WA/RE verdicts, depending on how the next few numbers are interpreted.

  • Not following the output format exactly. Many things can go wrong here:

    • Failing to print newlines, e.g. in C++, wrongly using printf("LuckyChef") instead of printf("LuckyChef\n") (or puts("LuckyChef")), and in Java, wrongly using System.out.print instead of System.out.println.
    • Wrong capitalization: printf("luckyChef\n")
    • Printing extra characters: printf("LuckyChef!\n"). This includes printing extra spaces, such as printf("Lucky Chef\n"), printf(" LuckyChef\n"), printf("LuckyChef \n"), which is normally not tolerated (note that some judges accept trailing spaces/new lines, but it won't hurt to be really careful!). Also, don't do printf("\nLuckyChef")!
    • Printing a blank line anywhere, e.g. in between inputs, or at the end.

The lesson is simply to be really careful about what you're printing. Also, there is a common mistake regarding new lines at the end of file. Normally, a "line" is terminated by a new line character '\n', including the last line. Some contestants intentionally omit the new line character at the last test case, which obfuscates/complicates the program a bit, and depending on the judge also incurs WA/PE. So when the problem says "print a line containing..." or "print ... in a line", always ensure that a trailing new line character '\n' is printed (certain print functions in some languages automatically does so, for example System.out.println).

  • Failing to allocate a large-enough array. For example, only allocating 10000 instead of 100000 by accident. This also includes some off-by-one errors if one uses 1-based indexing, such as in the following:
    
    import java.io.*;
    public class Main {
        public static void main(String args[]) throws Exception {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int T = Integer.parseInt(br.readLine());
            int P[] = new int[100000];
            int C[] = new int[100000];
            for (int cas = 1; cas <= T; cas++) {
                String[] parts = br.readLine().trim().split("\s+"); // split on whitespace
                int X = Integer.parseInt(parts[0]);
                int Y = Integer.parseInt(parts[1]);
                int K = Integer.parseInt(parts[2]);
                int N = Integer.parseInt(parts[3]);
                boolean found = false;
                for (int i = 1; i <= N; i++) {
                    parts = br.readLine().trim().split("\s+");
                    P[i] = Integer.parseInt(parts[0]);
                    C[i] = Integer.parseInt(parts[1]);
                }
                for (int i = 1; i <= N; i++) {
                    if (P[i] >= X - Y && C[i] <= K) {
                        found = true;
                        break;
                    }
                }
                System.out.println(found ? "LuckyChef" : "UnluckyChef");
            }
        }
    }
    This will run correctly in most inputs, but when N = 100000, this will give runtime error.

The lesson here is to learn to use 0-based indexing. It's also a good idea to allocate more than is needed, just to guard against these types of errors (see also defensive programming), for an example, see the first C++ code above. It's also a good idea to allocate the array as needed:

import java.io.*;
public class Main {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int cas = 1; cas <= T; cas++) {
            String[] parts = br.readLine().trim().split("\\s+"); // split on whitespace
            int X = Integer.parseInt(parts[0]);
            int Y = Integer.parseInt(parts[1]);
            int K = Integer.parseInt(parts[2]);
            int N = Integer.parseInt(parts[3]);
            // allocate only when needed
            // we're relying on the garbage collector to deallocate this.
            // some languages don't have garbage collection, so you need
            // to deallocate this manually if you don't want to waste memory.
            int P[] = new int[N];
            int C[] = new int[N];
            boolean found = false;
            for (int i = 0; i < N; i++) {
                parts = br.readLine().trim().split("\\s+");
                P[i] = Integer.parseInt(parts[0]);
                C[i] = Integer.parseInt(parts[1]);
            }
            for (int i = 0; i < N; i++) {
                if (P[i] >= X - Y && C[i] <= K) {
                    found = true;
                    break;
                }
            }
            System.out.println(found ? "LuckyChef" : "UnluckyChef");
        }
    }
}

(note however that this doesn't pass the time limit, so better use other techniques)

...or simply use structures that resize naturally, like the Python example above.

  • Taking input from a file/writing into a file! The input should be taken from the standard input (stdin) and the output should be written in the standard output (stdout).

  • Mistakenly using the same loop index in nested loops, e.g.

    #include <stdio.h>
    int main() {
        int T, i;
        scanf("%d", &T);
        for (i = 1; i <= T; i++) {
            int X, Y, K, N;
            scanf("%d%d%d%d", &X, &Y, &K, &N);
            bool found = false;
            for (i = 0; i < N; i++) {
                int P, C;
                scanf("%d%d", &P, &C);
                if (P >= X - Y && C <= K) {
                    found = true;
                }
            }
            printf(found ? "LuckyChef\n" : "UnluckyChef\n");
        }
    }
    Try running this program on the sample input and see what happens!

The lesson is to use different loop variables. Also, as a precaution, it is a good idea to declare the variable in the loop initializer itself, because some compilers can detect accidental reuse of loop indices.

Suggestions

Now that you've learned that many, many things can go wrong even for such a simple problem, how does one go about preventing it?

Well, for one, it is usually hard to write a completely correct code in the first try. Therefore one should always test the code before submitting it! For example, use the sample data. The sample data is provided for two reasons:

  • To ensure that you are following the input/output format correctly, and
  • To ensure that you at least get some small inputs correctly.

However, if you pass the sample input, it doesn't mean you'll pass the actual input! So it still lies upon the contestant to ensure that their program will pass whatever kind of test case the judge can give to it. So if the judge returns WA, try making some inputs yourself, until you find one where your program fails. Then start debugging from there. In other problems, it is sometimes useful to make random input generators.

Also, there is the occasional problem that tests how well you follow instructions and handle many tricky edge cases. In such problems, speed/minute optimizations are secondary to correctness, so things like readability/modularity more important, at the expense of efficiency. See the sample programs above as examples, which were written partly with readability in mind.

Time Complexity:

$O(N)$

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter
Tester

This question is marked "community wiki".

asked 15 Mar '15, 02:17

kevinsogo's gravatar image

7★kevinsogo
1.7k474137
accept rate: 11%

edited 04 Feb '16, 14:49

admin's gravatar image

0★admin ♦♦
17.4k347487515

1

@kevinsogo:

After the implementaion on C++ code, in the statement "Note that we used '\n' instead of endl, because endl forces a flush, " what is flush and when can we know flush occured in the program (or) not?

(16 Mar '15, 18:14) saiavinashiitr1★
1

Love your approach, multiple examples in multiple language !!!

(16 Mar '15, 22:21) mediocoder3★
1

@saiavinashiitr a link explaining "flush" has been added. The idea is that when you do cout << something, the something isn't necessarily immediately printed to the console/stdout. cout usually buffers them first, and then prints by batch, because printing something to the console is slow.

You call "flush" when you want it to be printed immediately (just like flushing a toilet). However, endl always forces a flush, causing unnecessary overhead in printing. By using '\n', there is no flush, so it's faster.

(17 Mar '15, 14:53) kevinsogo7★
1

@kevinsogo : Thank you, and your way of pointing out the common mistakes is nice and overall u made this editorial awesome :)

(17 Mar '15, 16:49) saiavinashiitr1★

good editorial.

link

answered 16 Mar '15, 16:26

v4_adi's gravatar image

2★v4_adi
11358
accept rate: 0%

great editorial :)

link

answered 16 Mar '15, 17:24

siddhartha4444's gravatar image

3★siddhartha4444
1547
accept rate: 0%

@kevinsogo

Great work my friend. :)

link

answered 16 Mar '15, 18:49

dracowane's gravatar image

6★dracowane
59315
accept rate: 48%

Python code, you say? Here's mine.

for _ in xrange(input()):
    X, Y, K, N = map(int, raw_input().split())
    print ["UnluckyChef", "LuckyChef"][min(1, len(filter(lambda b: b[0] <= 0 and b[1] >= 0, [[x - y for x, y in zip([X - Y, K], map(int, raw_input().split()))] for __ in xrange(N)])))]

I know it wasn't code golf or anything like that but boy it was fun to squeeze it into 3 lines. xD

link

answered 16 Mar '15, 19:31

grebnesieh's gravatar image

6★grebnesieh
707211
accept rate: 16%

1

Here's a more pythonic code golf:

for _ in xrange(input()):
    X, Y, K, N = map(int, raw_input().split())
    print ["UnluckyChef", "LuckyChef"][any(P >= X - Y and C <= K for P, C in [map(int, raw_input().strip().split()) for i in xrange(N)])]
(17 Mar '15, 21:09) kevinsogo7★

Awesome Editorial! keep it up. looking forward to more editorials :D

link

answered 16 Mar '15, 21:22

urdarinda's gravatar image

2★urdarinda
6115
accept rate: 0%

In this example, even if there is a better solution, it wouldn't be looked into. only the first solution that matches is taken. Is this the objective? obviously if there is a better combination of price and pages that satisfies the solution, but more optimised (in terms of price, say) then it wouldn't be printed. Maybe I assumed that the optimised should be printed. Thanks!

ps. Great Editorial with multi-language implementation.

link

answered 17 Mar '15, 20:26

njr07121977's gravatar image

3★njr07121977
211
accept rate: 0%

edited 17 Mar '15, 20:27

great explanation

link

answered 06 Sep '15, 00:55

idtemp2012's gravatar image

0★idtemp2012
11
accept rate: 0%

PYTHON

Code by ankitkhadria1

T=int(input())

for i in range(T): pr=[] co=[] X,Y,K,N=map(int,raw_input().split()) for j in range(int(N)): P,C=map(int,raw_input().split())

    if K>=C and P>=(X-Y):
        pr.append(1)

    else:
        pr.append(0)
pr.sort()

if pr[len(pr)-1]==1:
    print 'LuckyChef'
else:
    print 'UnluckyChef'
link

answered 16 Mar '15, 16:13

ankitkhadria1's gravatar image

2★ankitkhadria1
1
accept rate: 0%

When you post code, you should try indenting all your code four spaces, so that it renders properly as code.

(17 Mar '15, 21:11) kevinsogo7★

http://ideone.com/NL4Y3v

Can anybody tell me whats wrong with my code?

link

answered 16 Mar '15, 18:40

imanujagarwal's gravatar image

2★imanujagarwal
1
accept rate: 0%

I don't understand "it immediately breaks out of the loop, so it fails to read the next case properly". How breaking out would cause problem for the next case.

link

answered 17 Mar '15, 10:09

rc1c2's gravatar image

2★rc1c2
454
accept rate: 22%

1

There is a problem because you broke out of the loop too early while reading N pairs of integers (Pi, Ci). This means that the next Pi will be interpreted as the X of the next case, the Ci will be interpreted as the Y, and so on. Or if you are processing the input line by line, then you might get runtime error, because you were expecting four integers (X, Y, K, N) but only got two (Pi, Ci).

The explanation has been updated to explain this.

(17 Mar '15, 14:51) kevinsogo7★

Now I get it. Thanks !

(17 Mar '15, 19:54) rc1c22★
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:

×12,340
×1,155
×204
×62
×11

question asked: 15 Mar '15, 02:17

question was seen: 3,760 times

last updated: 04 Feb '16, 14:49