i think we are from same college COER …
am i right…
Find longest increasing subsequence of all prefix sums of the given array, if this length is greater than or equal to k, then answer is “YES” otherwise “NO”
2 Likes
Woah, such an elegant approach! Nicely thought 
1 Like
How was your experience ?
So removing the smallest from nr set doesn’t work and for it we need to check how much each element of nr set reduces the or value, which can be done in O(30 * sizeof(nr)) i.e O(30 * 30). But this solution resulted in TLE during the contest.
Our submission - Code
The one shared is the one with TLE. But the logic fails for case 97,154,196. I don’t think there exists a solution with the given constraints.
Is the correct ans for
1
3
97 154 196
673?
Order of 154, 97, 196 gives 680. Read this discussion thread Link. Everyone’s discussing this problem on codeforces.
Correct answer?
Since everyone is having their say on this and saying that rejudging would be fair. I’d also put my point of view as to why would it also be unfair to some teams like ours to rejudge this problem.
We had one hour remaining in the contest and 4 problems solved. The greater no. of ACs on this problem was the reason we decided to go for this problem instead of The Beautiful Partition one. I got this problem ACed 15 minutes before the end. Then, I decided to look at the Beautiful Partitions problems’ statement and got the idea in almost 5 minutes but couldn’t finish coding and debugging it in 10 minutes. Had those submissions for other teams on SUMOR already failed, we would’ve gone for the other problem instead and I’m sure we would’ve got it AC. I don’t know whether someone else had the same problem, but this is also an aspect that must be looked at as I believe that a majority of the teams who ACed the problem used that approach.
P.S.: LOL. I was always doubtful as to how can an icpc regional be conducted on codechef without any controversy.
13 Likes
How do you ensure that the first element of your LIS is positive while using the nlogn approach to find LIS?
But consider this: the testcases were wrong. What if someone wrote a correct solution but failed due to testcases being wrong? And after that spent a long time debugging it… It’s a very controversial situation…
Also, is the intended solution correct? Is the problem SUMOR even solvable? (INDIAN ICPC) - Codeforces . I think it would be highly unfair to ignore this fact…
1 Like
How about the Teams who thought the same solution and one of us comes with the same corner case and didnt code because we knew our method was wrong. Ofcourse the teams who solved this question by this method didn’t think clearly enough to get AC / Deserve AC.
5 Likes
I never said that the other way its fair. I just wanted to say that it’s unfair either way to some team or other.
4 Likes
That’s codechef!
Sorry but it isn’t unfair for the one who solved in this manner cause it’s wrong solution should get WA.
1 Like
Agreed. We tried a few cases and they all worked. We didn’t come up with this case. But the only motivation of trying this problem was more ACs than the other problems. And as I said in another comment, it’s somehow unfair in both ways as to whether it’s rejudged or not.
4 Likes
I want to try this problem right now but I can’t find any place to read and submit solutions for yesterday’s contest. Can anyone please provide me with the exact link as to where to get it?
How did u take care of printing the size of the partitions?
And could you please share your code?