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

×

# KTTABLE - Editorial

Author: Sergey Kulik
Testers: Kevin Atienza and Vasya Antoniuk
Translators: Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza

Cakewalk

Loops, Arrays

# PROBLEM:

There are $N$ students. Only one student can use the dormitory kitchen at at time. The head came up with a timetable for the kitchen's usage to avoid conflicts:

• The first student starts to use the kitchen at the time $0$ and should finish the cooking not later than at the time $A_1$.
• The second student starts to use the kitchen at the time $A_1$ and should finish the cooking not later than at the time $A_2$.
• And so on.

The $i$th student needs $B_i$ units of time to cook. How many students will be able to cook without violating the schedule?

# EXPLANATION:

The $i$th student has at most $A_i - A_{i-1}$ units of time to cook, so he/she can cook if and only if $B_i \le A_i - A_{i-1}$. So the answer is simply the number of indices $i$ such that $B_i \le A_i - A_{i-1}$. For simplicity of implementation, we can just define $A_0 = 0$.

The following are implementations in some popular languages.

C++:

#include <iostream>
using namespace std;

int a[10011];

int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
a[0] = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int ans = 0;
for (int i = 1; i <= n; i++) {
int bi;
cin >> bi;
if (bi <= a[i] - a[i-1]) {
ans++;
}
}
cout << ans << endl;
}
}


Java:

import java.util.Scanner;

public class Main {
public static void main (String args[]) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
int a[] = new int[10011];
for (int cas = 0; cas < t; cas++) {
int n = sc.nextInt();
for (int i = 1; i <= n; i++) {
a[i] = sc.nextInt();
}
int ans = 0;
for (int i = 1; i <= n; i++) {
int bi = sc.nextInt();
if (bi <= a[i] - a[i-1]) {
ans++;
}
}
System.out.println(ans);
}
}
}


Python:

for cas in xrange(input()):
n = input()
a = [0] + map(int, raw_input().strip().split())
b = map(int, raw_input().strip().split())
print sum(b[i] <= a[i+1] - a[i] for i in xrange(n))


Implementation notes:

• In C++ and Java, the array $A$ was allocated before processing any test case. This allows us to reuse the same array for multiple test cases which is faster than allocating new arrays every time. And actually, we allocated more than necessary. This is to preempt out-of-bounds errors.
• In C++ and Java, we didn't collect the $B$ values in an array. We just computed them on the fly and then threw them away immediately. Even though we saved some memory by not needing another array, there's no big need in doing this. But in some problems, you'll occasionally find yourself nearing the memory limit, so keep in mind such techniques because they are useful.
• In Java, we used java.util.Scanner, but take note that Scanner is slow, so in some problems with really large input, this approach will exceed the time limit just from taking the input. In those cases, use java.io.BufferedReader instead.
• Similarly, in C++, cin and cout is slow. The recommended way is to use printf and scanf, i.e., the "C way".
• In Python, we used the list comprehension sum(b[i] <= a[i+1] - a[i] for i in xrange(n)) to compute the answer in one line. This takes advantage of the fact that in Python, True == 1 and False == 0. A much intuitive version would be sum(1 for i in xrange(n) if b[i] <= a[i+1] - a[i]).

# Time Complexity:

$O(N)$

# AUTHOR'S AND TESTER'S SOLUTIONS:

This question is marked "community wiki".

asked 28 May '16, 16:41

1.7k586142
accept rate: 11%

19.8k350498541

 1 Thnx for the Implementation notes! That's were unknown to me before! Cheers!!! answered 26 Jan '18, 18:49 2★jvjplus 81●5 accept rate: 0%
 0 I did it by taking another array which stored the differences(memoizing) and achieved a faster running time. answered 31 May '16, 22:18 23●3 accept rate: 0%
 0 I compiled successfully and the result is the same as sample testcase.But when I submitted, it's wrong.I dont know why? answered 02 Jun '16, 19:06 1 accept rate: 0%
 0 @programminghak did u submit the output values after taking all the input values or you submitted them together one by one? answered 03 Jun '16, 15:39 1 accept rate: 0%
 0 def main(): testCase = input() people = [] timeDict = {} while int(testCase) > len(people): noOfPeople = input() timeOne = input() givenTime = input() timeDict[timeOne] = givenTime people.append(noOfPeople) for el in timeDict: ans = 0 takenTime = el.split() givenTime = timeDict[el].split() for items in takenTime: indx = takenTime.index(items) if indx!= 0: realTime = int(takenTime[indx]) - int(takenTime[indx - 1])  if realTime <= int(givenTime[indx]): ans+=1 else: if int(takenTime[indx]) <= int(givenTime[indx]): ans+=1 print(ans)  if name == "main": main() """This has run time error """ answered 22 Jul '16, 09:38 0★gsumk 1 accept rate: 0%
 0 def main(): testCase = input() people = [] timeDict = {} while int(testCase) > len(people): noOfPeople = input() timeOne = input() givenTime = input() timeDict[timeOne] = givenTime people.append(noOfPeople) for el in timeDict: ans = 0 takenTime = el.split() givenTime = timeDict[el].split() for items in takenTime: indx = takenTime.index(items) if indx!= 0: realTime = int(takenTime[indx]) - int(takenTime[indx - 1])  if realTime <= int(givenTime[indx]): ans+=1 else: if int(takenTime[indx]) <= int(givenTime[indx]): ans+=1 print(ans)  if name == "main": main() """This has run time error """ answered 22 Jul '16, 09:39 0★gsumk 1 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,680
×1,652
×847
×55
×45

question asked: 28 May '16, 16:41

question was seen: 3,919 times

last updated: 26 Jan '18, 18:49