LRQUER Subtask 2.

Are there no max-tests in LRQUER 2nd subtask? The most naive O(NQ) solutions passed on it. See this, for example.

@admin @vijju123

1 Like

I dont think so @meooow . Dont exactly remember but I think I passed that Q much earlier :stuck_out_tongue: .

@bazsi700 , True, it did not have any constraint. But possibly the setter kept it a bit weaker than final sub task. They do it at times so that people can avail partial marking. I mean, it really makes no sense to keep another sub task where just the array values are small :confused: . It wont make any difference in ranking. But if we fill it with large random case, or intentionally weak case (which is large), then it can make a difference. I think it was intentional. Meaning they took ~K*{10}^{8} to {10}^{9} operations.

Its not yet added to practice session, so I cannot verify if they are maximal or not. But they are large, thats for sure. Anything else where I can help? :slight_smile:

Go and see announcement section in November lunchtime.
They have mentioned that due to increasing queue, some test files have been deleted from LRQUER. Submissions made till now will be rejudged on these files only, after the contest has ended.
During the transition, the subtasks configuration was wrong, and hence a few submissions would have been evaluated with a file in a wrong subtask. This will also be fixed after the contest. We apologize for the inconvenience.
@bazsi700 @vijju123

Anyway this time the lunchtime was much smoother that previous few short challenges.

This O(NQ) solution got 100 points.
Link: https://www.codechef.com/viewsolution/16369986

2 Likes

I was wondering the same…Even my solution passed

Mine too!!

My first solution too, I was pretty surprised during the contest.

Your soln got TLE in final subtask. Whats the discrepancy?

@vijju123 Second subtask has no constrain neither on N nor on Q. My (and others’) solution should TLE on second subtask too.

1 Like

From the announcements:
"21:01 IST: Due to increasing queue, some test files have been deleted from the problem LRQUER. Submissions made till now will be rejudged on these files only, after the contest has ended. "

This may be the reason.

Here is a possible solution for second subtask which doesn’t work for final:
Store a Fenwick tree for each number’s frequency. It takes up 10^2*10^5=10^7 memory, which fits in limit.

At each query we can check all numbers up to 10^2, if they occour, thus resulting in O(\log{N}*10^2) which also fits.

At updating you simply update Fenwick tree which is O(\log{N})

It’s a solution worth 30 more points, but definitely not the last subtask, and it does so.

I don’t think the most naive solution is intended to get half score, on a problem solved by less than 60 people during the contest.

I get your point. But thing is, what can we do about it? And I dont even know if setter made that TC weak intentionally or not. Thats something only he knows, despite what we may predict :frowning:

Actually, another thing in support of ur point- lr queries was probably supposed to be p3 in my opinion ( p3 dont have weak data except for first subtask), and became p2 because…welll…the original p2 just went over brains of people like me XD

How is this possible. Constraints are violated brutally.

JAVA…Its magic sometimes. :slight_smile:

Exactly.I doubt whether the solutions have been rejudged.
See this @vijju123

https://www.codechef.com/viewsolution/16378208 @vijju123 mind taking a look at this? i believe my solution for the same problem is O(QLogn^2) still time out :\

I dont think they meant that all problems will be rejudged on those big files later. It creates issues. Format of lunchtime is not like CF rounds, where your code has to later pass the systest.

One can come forward and say “Had I known it will TLE, I would have given this Q more time to code and think over” &etc.

Things wont be fair if their rejudge. I think what they meant was “After the contest, codes will be rejudged on LEFTOVER files only for verdict and points”

@divyansh_gaba7 - Let me have a look at it.

@vijju123 - Thanks!