×

# INOI 2018 discussion

 3 For second one, The observation was that, we can take one path and calculate the total sum without a second path using dp[i][j][k] = min/max(dp[i-1][j][k], dp[i-1][j-1][k-1])+prefix_sum[i][j]. We calculate this two times, once for min and once for max and then we can use the prefix sum intuition to subtract min-dp from max-dp. It's not clear enough here, but you might get an essence. answered 07 Jan, 20:36 2.3k●4●19 accept rate: 20% Exactly I did the same one but I made a error in finding dp(i)(j) and I didn't have time to debug so I couldn't get get partial in this so my ioitc hopes are down ,I am in 10th standard (08 Jan, 09:30) There were two main insights: The intersection constraint will implicitly be handled, since the base points have to be at least $K + 1$ apart. You can represent a possible solution as the difference of two solutions which have the left region as the 0th column. (as you said, the prefix sum intuition) (09 Jan, 12:30)
 2 Oh boy , was the second problem hard to get a logic for then,in the center.Anyway I guess the first one was pretty easy ,just basic bfs (or if you prefer,DFS).The second one really took a lot of my time and still I could solve only the easiest subtast of it(the 3rd one only,k=0) and could actually also solve k=m-2 task if I had a little bit more time (enough to copy my code from ide to submit tab :( ) Anyway I don't think I would be able to qualify with a pretest score of 112 seeing these many people get more higher . Still hope the cutoff somehow comes out in my favour :P .(btw I thought in inoi they don't have scores based on class/grade in which the participants study in ,right?) answered 08 Jan, 17:57 1●2 accept rate: 0% You might qualify if you are in class 10 or below. (08 Jan, 23:31) I am in 11th ,btw you gave exam in Kolkata center,right? I hoped to see you :P ,your questions in ico prep contests were pretty great. (09 Jan, 09:46) 3 istapr0 is the codename (09 Jan, 10:24) My condition was similar. BTW am I the only one around here who use DSU on the first one? :P (12 Jan, 22:00)
 0 I got 127 ... First one was a very easy dfs I found the 2nd question hard and did 2 subtasks in it. answered 07 Jan, 18:02 100●1●8 accept rate: 14%
 0 Solved the road trip and museum one. 100. Simple dfs. Couldn't solve the second one though. You? answered 07 Jan, 18:02 2★prajneya 1 accept rate: 0% I got 200. (07 Jan, 18:20)
 0 anyone solved 1 with bfs?? answered 07 Jan, 18:25 1 accept rate: 0%
 0 What were the problems? answered 07 Jan, 18:30 2★amit94 66●2 accept rate: 25%
 0 I solved the first one using BFS and got 100... For the second one I used prefix sums and got 12 points... answered 07 Jan, 19:02 11●1 accept rate: 0%
 0 I kept getting Segmentation error and runtime error while solving the first question. When I decreased the changed the adj list from adj[1000005] to adj[1005], the code ran fine. Did anyone else have this problem ? Also, what was I doing wrong ? answered 07 Jan, 20:03 3★taksh001 0 accept rate: 0%
 0 can anyone tell how to do the second question two paths answered 07 Jan, 20:12 3★ssp547 307●7 accept rate: 26%
 0 so what would be the expected cutoff?? answered 07 Jan, 21:15 1 accept rate: 0% 148 for 11,12 and 100 for 10 and below i guess (08 Jan, 08:58) 1 I think it would be 112 for 10th and below else too many people would qualify. (08 Jan, 11:33) 116 overall. I dont think they should make separate cutoffs. (09 Jan, 10:25)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×355