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

×

# Can anyone help me with Pro Chef And Katana from LoC June 2018 ?

 1 Hello friends can someone tell me how to approach this problem ? I am getting WA. Here is my latest submission. If it's too messy, here is the approach I used : n =readInt() arr = readInts() count = 0 for i in range(len(arr)): count+=1 f =0 minus = arr[i] for j in range(len(arr)): arr[j]-=minus for j in range(len(arr)): if arr[j]>0: f =1 if f==0: break print(count)  asked 09 Jul, 07:54 227●10 accept rate: 2% At least make sure arr[i] > 0 before subtracting it from the whole array. (09 Jul, 08:36)

One Answer:
 1 You'll need to subtract the MINIMUM element of the segment from each element of the segment. By segment I mean, a contiguous range, surrounded by a 0 at both sides. Eg. 1, 4, 7, 0, 4, 0, 7, 8 has three segments; 1 is minimum of the first segment, 4 of the second and 7 of the third segment. Try the simple test: 2 2 1  Your code gives 1 as answer, but you need atleast 2 cuts. answered 09 Jul, 08:33 791●1●14 accept rate: 39% n =readInt() arr = readInts() count = 0 for i in range(len(arr)): count+=1 f =0 minus = arr[i] if minus <0: continue for j in range(i,len(arr)): arr[j]-=minus for j in range(i,len(arr)): if arr[j]>0: f =1 if f==0: break  print(count) @sarthakmanna here is the approach where am I missing. Also for 100 points I feel it's too slow. (09 Jul, 11:15) 1 I was trying to explain this approach: https://www.codechef.com/viewsolution/19150087 For 100pts, you can use a stack or priority queue like this: https://www.codechef.com/viewsolution/19011529 The 100pt solution is written in Java. I hope you'll have no problem in understanding it. However, if you have any, feel free to ask. (10 Jul, 00:43) thanks man I got it now. Let me code it out using stack :) (10 Jul, 06:07)
 toggle preview community wiki:
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:

×2,507
×2,094
×135
×66

question asked: 09 Jul, 07:54

question was seen: 179 times

last updated: 10 Jul, 06:30