Request for simple explanation for MARRAYS problem.

general
,
1

Can someone please give a simple explanation to the MARRAYS problem of Oct’17 long challenge.I tried to understand it from the editorial but i’m unable to understand all the mathematical language there.
Thanks in advance.

2

You may refer the my editorial at following link.

Another editorial at https://discuss.codechef.com/questions/114547/unoffcial-editorials-oct17

Feel free to ask anything…

1 Like
3

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

This is my solution but it is giving me WA. Basically what I’m doing is storing the min & max value for each of the N arrays and then going into the recursion and storing the found results in a DP table.
Can you please tell me what’s wrong in my approach ?

4

Your code fails at this type of cases-

Input
1
3
1 50
8 50 1 50 50 100 50 90 90
1 50
Your Output
150
Expected Output
120

Okay, I expected that your code will give 100 and undercount, but your code is yielding an answer greater than the expected one.

1 Like
5

In your test case expected output should be 120 not 150.

1 Like
6

Misprint lol. That happens when you;re focussing on too many things at a time XD

1 Like
7

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

This solution by ceilks is so fast. Are you able to understand his approach ?

8

Intended algorithm, iterative version, takes around 0.16 seconds to compute. The reason why his solution is faster is due to very fast I/O methods. Time to copy someone’s template X) :smiley:

This much difference in runtime usually doesnt actually have much significance (assuming you werent using slow I/O methods in first place-else it matters a lot). The O({N}^{2}) algorithm which took 10 seconds will now take ~9.8seconds.

But sometimes clever brute force can use it to get accepted, it all depends on TC, luck and your code altogether (but nonetheless happens and is a nice giddy feeling :3).

But 1 thing, do read about the downsides of getchar unlocked. You wouldnt want to ruin your chances at some job interview after all! Its expected and is a must to know the working and functioning of things (and languages) you use, so before using it in your code do go through the downsides of get_char method. (Eg- It locks the screen while taking input, is thread unsafe etc.)

1 Like
9

But still his actual algorithm is shortest in terms of lines of code I’ve seen in any solution for this problem.

10

his code is fast not just because of the fast io but also because he is not looping unnecessarily. Number of statements executed in his code is lesser than many other submissions.

  1. https://ideone.com/T3mii3 this code implement the same logic but has more loops

read this code then understanding the ceilks’s code will be easier

11

Thanks for mentioning mine , but sadly I didn’t do it . So I have the editorials for only the first five problems .

12

Nope… still not able to get the approach :-\

13

I had checked out some of the low time taking codes. I feel that at this point of curve, fast I/O does play a significant role, along with choice of data structures used. Did you try running his code using scanf and printf?

14

I have posted another editorial dedicated only to this problem which you may refer at following link after reading my editorial at above mentioned link

2 Likes
15

Oops. I thought u solved MARRAYS and didn’t solve Chef and cycles. I knew u solved 5 problems but forgot which ones… :smiley: