Codechef LOC-Noob Chef And Katana Problem
Can anybody tell me what this question what to say?I read it 2-3 times,but did not able to understand properly what we have to do exactly?
Chef likes to play with his katana. So he decides to play a game with N sticks each having a particular height, his aim is to finish all the sticks he has. Now he does this in a particular way! He selects the largest continuous subsegment of sticks in which every stick has non zero height and then selects a non zero height and then swing the katana in the selected segment and removes the lower cut part and the leftover upper part comes down with reduced height. He does this until no sticks are left. Now as Chef is a NOOB he is allowed to rearrange the sticks!
This reduced height can be zero for example if you have only one stick of length 5 then you swing the katana at height 5 then remove the lower part which is the entire stick and then nothing is left
Also the height you select should not be greater than the smallest stick in the subsegment you selected!
Since Chef wants to reduce the number of swings because he has to build the cupboard also!
He asks you to calculate the minimum number of swings needed to finish all the sticks so he can come back later and finish the task quickly!
Input:
First line will contain N, number of Sticks.
Next line contains N integers representing the height of each stick and also in the order in which they are placed.
Output:
For each testcase, output in a single line the minimum steps needed.
Constraints
1≤N≤106
1≤Height≤104
Sample Input:
5
1 2 3 2 1
Sample Output:
3
EXPLANATION:
Swing 1: Segment(1,5) and height(1)
The sticks now look like 0 1 2 1 0
Swing 1: Segment(2,4) and height(1)
The sticks now look like 0 0 1 0 0
Swing 1: Segment(3,3) and height(1)
The sticks now look like 0 0 0 0 0
In the given sample case there are other ways in which he can finish the sticks, but the minimum answer is 3 steps.
Chef likes to play with his katana. So he decides to play a game with N sticks each having a particular height, his aim is to finish all the sticks he has. Now he does this in a particular way! He selects the largest continuous subsegment of sticks in which every stick has non zero height and then selects a non zero height and then swing the katana in the selected segment and removes the lower cut part and the leftover upper part comes down with reduced height. He does this until no sticks are left. Now as Chef is a NOOB he is allowed to rearrange the sticks!
This reduced height can be zero for example if you have only one stick of length 5 then you swing the katana at height 5 then remove the lower part which is the entire stick and then nothing is left
Also the height you select should not be greater than the smallest stick in the subsegment you selected!
Since Chef wants to reduce the number of swings because he has to build the cupboard also!
He asks you to calculate the minimum number of swings needed to finish all the sticks so he can come back later and finish the task quickly!
Input:
First line will contain N, number of Sticks.
Next line contains N integers representing the height of each stick and also in the order in which they are placed.
Output:
For each testcase, output in a single line the minimum steps needed.
Constraints
1≤N≤106
1≤Height≤104
Sample Input:
5
1 2 3 2 1
Sample Output:
3
EXPLANATION:
Swing 1: Segment(1,5) and height(1)
The sticks now look like 0 1 2 1 0
Swing 1: Segment(2,4) and height(1)
The sticks now look like 0 0 1 0 0
Swing 1: Segment(3,3) and height(1)
The sticks now look like 0 0 0 0 0
In the given sample case there are other ways in which he can finish the sticks, but the minimum answer is 3 steps.
The question was written by a moron, but I believe it can be paraphrased like this:
You are given an array of N integers (N from 1 to 1000000, integers from 1 to 10000).
You can rearrange them however you want.
Select the largest continuous subsequence of non-zero values, choose an integer, and subtract that integer from all of those values. Call this a operation a "reduction". The chosen integer cannot be larger than the smallest value in the subsequence.
What is the fewest number of "reductions" that are needed to reduce all the values to 0?
You are given an array of N integers (N from 1 to 1000000, integers from 1 to 10000).
You can rearrange them however you want.
Select the largest continuous subsequence of non-zero values, choose an integer, and subtract that integer from all of those values. Call this a operation a "reduction". The chosen integer cannot be larger than the smallest value in the subsequence.
What is the fewest number of "reductions" that are needed to reduce all the values to 0?
Last edited on
Thank You for the reply @tpb.
Can you tell how to solve this problem other than brute-force?
Can you tell how to solve this problem other than brute-force?
I don't know. I'm not even sure I understand it properly. It seems that you can rearrange the numbers before every reduction, and the only thing that defines the subsequences is the positions of the zeroes. And you have to pick the largest one. I'm not sure it that makes sense.
Can you give the link to the problem on codechef?
Can you give the link to the problem on codechef?
Topic archived. No new replies allowed.