PROBLEM LINK:
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
ifcondition incorrectly. Here are a few examples (they are all wrong!):P > X - Y && C <= KP >= X - Y && C < KP >= X - Y || C <= KP >= X + Y && C <= KP >= Y - X && C <= KP - 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
falsewill 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 ofprintf("LuckyChef\n")(orputs("LuckyChef")), and in Java, wrongly usingSystem.out.printinstead ofSystem.out.println. - Wrong capitalization:
printf("luckyChef\n") - Printing extra characters:
printf("LuckyChef!\n"). This includes printing extra spaces, such asprintf("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 doprintf("\nLuckyChef")! - Printing a blank line anywhere, e.g. in between inputs, or at the end.
- Failing to print newlines, e.g. in C++, wrongly using
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)
