if any 3 segments having the same velocity have at least a common point(common part is in all 3 segments), then the answer will be a NO else it will be a YES. My team got WA with this idea. Is it wrong? @nik_84 @anon24665730 @vijju123. Any help is appreciated. Thank You.
1 Like
Has anyone got AC in the question Beautiful Segments(It was probably the 6th question) ?
I havenāt been able to solve it during the contest, but after the contest I have an approach to that problem. It goes something like this :
- Create a prefix array of the original array
- If sum of all elements of the array is not strictly positive, then the answer is NO
- Otherwise, we choose only positive numbers from the prefix array and find if there exists an increasing subsequence of size >= k
Can anyone please verify whether this approach will work or not ?
1 Like
Its correct
1 Like
Idea is correct. You must have made error in checking for overlap.
1 Like
When will the problems be open for practice?
Thanks for the verification. I havenāt even attempted the problem during the contest, just gave it a read. Actually our team got deceived by seeing this question to be the 6th question 
Do u got AC in this prob in the contest???
Yes, I didā¦
1 Like
You have to take care of one more condition. The increasing subsequence with size >= k should include the last prefix sum, otherwise you may get a wrong answer.
Basically then, is it same as reversing the array and finding LIS starting from index 0?
I think you meant LDS. Also, the LDS must comprise of strictly positive elements. The starting from index 0 is lalso really important. Otherwise, it would fail in something like dividing 1 2 3 4 5 -6 into 5 parts. The prefix sum array gives 1 3 6 10 15 9. The LIS of this is 5, using the first 5 elements, but we canāt divide it into 5 parts with positive sum.
Yeah, LDS 
But wonāt starting from index 0 be automatically taken care of since its a prefix sum? I think you meant to say that the first element of LIS should be positive?
Otherwise, it would fail in something like dividing 1 2 3 4 5 -6 into 5 parts. The prefix sum array gives 1 3 6 10 15 9. The LIS of this is 5, using the first 5 elements, but we canāt divide it into 5 parts with positive sum.
This example does not make sense to me because I do not know what K you assumed. I assume that you meant K=5, but then doesn;t this example highlight that LIS should end at last element instead of starting from index 1 ? I think you got mixed up in the convention.
Is this the final ranklist of ICPC ?
Yeah I mixed up your comment and the comment above. But I hope you get the idea.
One easy implementation to ensure all the conditions of the LIS are satisfied is to find LIS of only those prefix sums, who are positive and less than the last prefix sum. This way, we ensure that the last one is always included.
1 Like
We also did the same, But we used map of map and got AC in one submission.
Can someone please help me debug this solution for Question 3 which I made during contest. It gave runtime error but cannot find where is the problem.
anyone has any idea by when can we expect icpc results?
any rough guess?
6 Likes
@naman_bhalla Sir, I have seen your solution and understood your approach. But can you tell me how you really came up with the implementation?I felt it to be extremely hard. Did you do similar kind of problem elsewhere?
Thanks in advanceā¦