INOI 2016 Discussion

general
,
21

Will O(n^3) pass?

22

INOI cutoff is the same for everyone.

23

I assumed it to be negative instead of 0. Didn’t pass for me. Could that possibly be the reason?

24

Okay. What’s going to be the expected cutoff according to you and what was the cutoff last year?

25

can anyone post the sample inputs for both the questions

26

I think so, yeah. Also what were you printing if there was no correct bracket subsequence?

27

aah I didn’t quite think about that. my program would print -10^8 :stuck_out_tongue:

28

Passed the pretests for me. (same recursion)

29

I sort of did this, in a very untidy way, but it didn’t pass…:confused:

30

The cutoff has been 100 for a couple of years now. No idea about this one. P1 was too easy, I think. I would say 140 or 200.

31

I think system testing might be a problem there, but then again, no one has a better solution right?

32

mbrc was trying to code a O(n^2*k) solution, but apparently couldn’t do it in time.

33

For the 2nd problem, I assumed the first case if all v[I]s are negative. For e.g.
6 3

-5 -4 0 -3 -6 -5

1 3 4 2 5 6

My code was printing -5. And for no bracket subsequence, I printed a huge negative quantity.

34

Wait for system testing. I had used a lot of my time trying to figure out how strong the test data was. And it wasn’t very strong. Keeping fingers crossed!

35

Looks like 140 to me. 200 would be way to high and problem 2 certainly was tough. (I didn’t even realize there was a DP solution to it). And how did you do the brute force for subtask 1? My brute force gave 3 correct answers and 2 incorrect for subtask 1. I tried possibly every test case I could think of and got the expected output. Also the description was a bit ambiguous. I remember in the explanation that the numbers at index 2, 4, 5, 6 were said to be (don’t remember the exact term). But the indexes 2,6 and 4,5 were not mentioned. So is it to have gaps greater than 2 between the numbers?

36

@siddharth2000

IIRC the sample input for the first one was-
4 5 10 6 12 2 -1 4 2

1 Like
37

thanks a lot but do you remember the 2nd question’s sample input as well

38

6 3

4 5 -2 1 1 6

1 3 4 2 5 6

39

@animesh_f, how did you try to figure out the test cases? Only the first two test input and output were shown on my system (and both gave correct results in Brackets, subtask 1). They should have displayed the input which gave incorrect results.

40

@geekpradd My code initially gave the same 3 out of 5. But after I tried it with this test case I found out my mistake. Values 1 2 3 4 1 2 3 4, and bracket sequence 1 2 4 5 1 4 2 5. K=3 N= 8 Expected output is 16.