CHAHG: The Corner Test Case

general
,
1

In the problem statement of “Chef and his garden” from August Challenge 2016, it is clearly mentioned that,

Formally, the trees will be said to in Zig-zag sequence if one of the following two conditions holds:

h1 < h2 > h3 < h4 and so on…

h1 > h2 < h3 > h4 and so on…

Now, for n = 1 (the corner case), it seems clear that this scenario is not a zig-zag one as neither we can say (h1 > h2) or (h2 > h1). But after getting many WA, I changed it to an infinite zig-zag and it gets AC. Is there something I am missing here? Or is it an legitimate issue?

2 Likes
2

for n==1 trees will always be in zig-zag sequence because there is no another tree which can break zig-zag sequence , so for n==1 ans would be [0,Inf]

2 Likes
3

@yb4singh: The question is not about if any tree is able to break a zig-zag sequence. It’s about if we can find a pattern where the height is alternating. When n=1, that isn’t the case.

4

i had a same doubt for n==1, but changing it got AC, so didn’t give it a thought. Definitely looking forward for some justification.

5

Not an answer, would be grateful if somebody could point out what is wrong with this code. Lots of WA and could not finish it till the end. My submission:https://www.codechef.com/viewsolution/11175997

Approach:

  1. find intervals where (i-1)th tree is bigger that (i)th tree. If none such exists, set start and end to -3. If it (i-1)th tree is bigger till infinity, mark end as -2
  2. Invert the intervals accordingly. So for example if (i-1)th is bigger than (i)th in range (5, -2), it would be smaller in (0, 4) or (0, 3) depending on the initial height.
  3. Assume the configuration: h1 < h2 > h3 < h4 and so on… to be true. Try to calculate intersection of intervals as you parse the array which have valid sequence.
  4. Assume the other config to be true and do the same.

P.S.: I do not have the rep to ask a question and some recent activity didn’t get me any.

1 Like
6

Its the first time that editorials are not been published till now :frowning:

7

Can someone please tell me how to solve CHEFRRUN (tutorial/editorial), the link to the problem statement is https://www.codechef.com/AUG16/problems/CHEFRRUN . Please, I’ve been trying it but I haven’t been able to come up with a proper solution. I can’t ask a question because I don’t have sufficient Karma points. Thanks in advance

8

@roshandash411: Sorry for the misinterpretation there.

Here’s my approach to CHEFRRUN.

First start from the first box and go to the subsequent box, keeping a visited array. If you reach an already visited box, then just repeat traversing from the repeated box to the repeated box to get the length of the loop/cycle. Now add this length to answer.

Next do the above same thing with the boxes that are not visited.

The thing to notice here is that as there is one way to go from a box, there will never be a box in 2 different loops. Just find the length of all loops. The implementation was a bit difficult.

Here’s my overly complicated solution, with the above approach:-

https://www.codechef.com/viewsolution/11055959

But you will get the basic idea.

Complexity:- O(N)

9

can anyone plz upvote me so i could ask my doubt . I am facing Karma issue. Thanks in advance.

2 Likes
10

In this question if there is only one tree, its height will always be increasing or constant , as there is no other tree to compare, the n==1 case will always be considered as zigzag sequence because there are only two cases possible that all the trees will be in zigzag sequence or height of some tree changes in a pattern that the zigzag pattern can’t be formed which is not possible in this case