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

×

RKABOL03 - Editorial

PROBLEM LINK:

Practice
Contest

Author: ravikiran0606
Editorialist: ravikiran0606

DIFFICULTY:

MEDIUM

PREREQUISITES:

DP,MATH,BINARY SEARCH

PROBLEM:

In this problem, we have N + 1 bus stops in a straight line. All of them are numbered with integers from 0 to N in the order in which they follow from RK's college. There are M buses running between the college and the beach: the i-th bus goes from stop si to ti (si < ti), visiting all the intermediate stops in the order in which they follow on the segment. RK can get on the i-th bus on any stop numbered from si to ti - 1 inclusive, but he can get off the i-th bus only on the bus stop ti. We need to find the number of ways RK can go from college to beach.

EXPLANATION:

In this question, for every stop from 0 to N lets calculate kx - number of ways come to them. Consider the i-th bus, number of ways come to stop ti supplied i-th bus is equal to number of ways to embus to i-th bus. One can embus to i-th bus on the stops si, si + 1, ..., ti - 1. Thus number of ways come to stop ti in the i bus is equal to sum ksi + ksi + 1 + ... + kti - 1. Finally, lets note that overall number of ways to come to stop ti is the sum of numbers of ways to come to stop ti on every bus.

It's remained two problems.

First problem: 0 ≤ n ≤ 109. Therefore all kx not climb in memory limit. But we need to know only non-zero kx. For instance, one can gripe coordinates: create list of all occured stops (and also stops 0 and n), sort this list, delete the repeated stops and replace all numbers of stops they indexes in this list. After this operations all number of stops not exceed 200001, and all kx are climb to the memory.

Second problem: If we will use loop "for" for counting sum ksi + ksi + 1 + ... + kti - 1, asymptotic of time of working will be O(m^2). There is an easy way to solve this problem: one can create and update array sum[], such that sum[i] = k[0] + k[1] + ... + k[i - 1], by another words, sum[0] = 0, sum[i + 1] = sum[i] + k[i]. Then number of ways to come to stop ti using bus i is equal to sum[ti] - sum[si]. So time complexity is O(m logm) , memory complexity is O(m).

AUTHOR'S SOLUTION:

Author's solution can be found here

asked 14 Mar, 00:07

ravikiran0606's gravatar image

4★ravikiran0606
41
accept rate: 0%

edited 15 Mar, 13:37

admin's gravatar image

0★admin ♦♦
19.3k348495534

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,005
×2,472
×1,875
×783
×19
×19
×19

question asked: 14 Mar, 00:07

question was seen: 151 times

last updated: 15 Mar, 13:37