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

×

KTTABLE - Editorial

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

This question is marked "community wiki".

asked 28 May '16, 16:41

kevinsogo's gravatar image

7★kevinsogo
1.7k586142
accept rate: 11%

edited 06 Jun '16, 13:52

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 26 Jan '18, 18:49

jvjplus's gravatar image

2★jvjplus
815
accept rate: 0%

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

link

answered 31 May '16, 22:18

aijajkhan's gravatar image

3★aijajkhan
233
accept rate: 0%

edited 31 May '16, 23:43

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

link

answered 02 Jun '16, 19:06

programminghak's gravatar image

0★programminghak
1
accept rate: 0%

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

link

answered 03 Jun '16, 15:39

adityaprakash's gravatar image

1★adityaprakash
1
accept rate: 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 """

link

answered 22 Jul '16, 09:38

gsumk's gravatar image

0★gsumk
1
accept rate: 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 """

link

answered 22 Jul '16, 09:39

gsumk's gravatar image

0★gsumk
1
accept rate: 0%

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:

×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