KTTABLE - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest
Practice

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

DIFFICULTY:

Cakewalk

PREREQUISITES:

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:

Setter
Tester
Editorialist

1 Like
2

I did it by taking another array which stored the differences(memoizing) and achieved a faster running time.

3

I compiled successfully and the result is the same as sample testcase.But when I submitted, it’s wrong.I dont know why?

4

@programminghak did u submit the output values after taking all the input values or you submitted them together one by one?

5

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
“””

6

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
“””

7

Thnx for the Implementation notes! That’s were unknown to me before! Cheers!!!

1 Like