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

27 Likes

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'

good editorial.

1 Like

great editorial :slight_smile:

1 Like

Can anybody tell me whats wrong with my code?

@kevinsogo

Great work my friend. :slight_smile:

1 Like

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

3 Likes

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

1 Like

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.

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.

1 Like

great explanation

1 Like

My solution is getting WA for Sub-task 2, Task#4, can anyone suggest any edits?

t = int(input())
for i in range(t):
    x, y, k, n = map(int, input().split())
    l = [0]*n
    cost = [1000]*n
    j=0
    for j in range(n):
    	l = list(map(int, input().split()))
    	if l[0]>=(x-y):
    		cost[j] = l[1]
    if min(cost)<=k:
    	print("LuckyChef")
    else:
    	print("UnluckyChef")

When I am running my code on ideone compiler ,the output is coming correct.But on running through it shows wrong answer.Can someone explain how to do subtasks?I made variable N and T long int still my answer is not getting accepted

How to solve it, if we are allowed to buy multiple notebooks instead of just one? Do we need to need to use Knapsack DP?

package easyLevel;

import java.util.Scanner;

public class ChefNNotebooks_CNOTE {

public static void main(String args[]){
	
	Scanner sc = new Scanner(System.in);
	
	int T = sc.nextInt();
	
	while(T > 0){
		
		String result = "UnluckyChef";
		int X = sc.nextInt();
		int Y = sc.nextInt();
		int K = sc.nextInt();
		int N = sc.nextInt();
		
		while(N > 0){
			
			int P = sc.nextInt();
			int C = sc.nextInt();
			
			if(C <= K && P >= X-Y){
				result = "LuckyChef";
				break;
			}
			
			N--;
		}
		
		System.out.println(result);
		T--;
	}
}

}

gettinh WA, not sure why

@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?

1 Like

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

1 Like

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.

4 Likes

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

3 Likes

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

1 Like