UASEQ - Editorial

editorial
, , ,
1

Problem link : Contest Practice

Difficulty : Easy

Pre-requisites : basic language data structures

Solution:

The key thing is to note that K is not greater than 10. So, we can easily brute-force the first and the last term of the sequence that won’t change. There won’t be more than K2 variants, but actually this number is even smaller. So, let’s fix some integers L and R - the leftmost and the rightmost number in the sequence that won’t change. I’d like to point out that according to the statement L < R condition will always be held. That helps to avoid some exceptional or ambiguous situations.

And now, it’s easy to see that we can uniquely recover an arithmetic progression from this data. The difference D between the adjacent numbers in this AP will be equal to (aR - aL) / (R - L), and the first term of the progression will be equal to aL - D * (L - 1), in case we use 1-indexation. Here aK is basically the K-th element of the given array. Let’s call the progression with the correspondent first element and difference a candidate.

Now it is clear that the answer is one of the candidate sequences. Let’s try all of them. For each one, it is possible to calculate the number of mismatching elements in the array in O(N) time. If this number is not greater than K, we can compare this sequence to the current best one in terms, described in the problem and possibly, update the current best sequence. The whole process doesn’t require any clever or tricky implementation. Here, the straightforward solution will have the complexity of O(N * K2) that will easily pass, because the maximal value of K is relatively small.

Setter’s solution: link

Tester’s solution: link

5 Likes
2

Please fix Setter’s and Tester’s solutions link not able to see them showing an XML error

2 Likes
3

i kept thinking that there exists some DP solution for it until yesterday i saw that k is quite small and then i got the answer.

1 Like
4

Could anyone please elaborate on the brute force technique

5

“Access Denied” while accessing solutions.

2 Likes
6

I tried this problem one day before contest end. My solution is O(n) and one more this it does not depend on K because of very week test cases. Even my solution was unable to pass the sample test case But AC because of small value of K. I never used K in my solution.
Explanation of my algorithm -->it finds the longest contiguous AP sequence with start and end index in O(n) and the two loops one is from start to 0 and other is end to n.
link to my solution http://www.codechef.com/viewplaintext/4822024

3 Likes
7

How to determine L and R

8

LMAO dude, even I thought of such a hack but I was implementing it the longer way around. Damn!

9

I even wrote a mail, commented on a forum post that the test cases are weak you should rejudge and all but they did not. i guess they got too lazy this time. For everyone thinking why the test cases are weak. you should try this:

3 1

1 4 5

Ans should be 1 3 5(common diff = 2) but every one whose output is 1 4 7 are wrong as common difference is 3 in the latter case. Acc to statement we were supposed to minimze ‘d’ if ‘a’(lowest) is same.

5 Likes
10

Can someone please explain the brute force method mentioned in the editorial?

11

good work @dcod , I think the problem tester needs to look into this matter. @xcwgf666

12

About “weaker test cases”.

The problem is simple and the solution is very simple as well. If you go longer way and think on some overcomplicated ideas and spend extra time instead of just write the obvious thing, you make things harder only for you, not for anybody else. It is not you, who is getting benefited by the “weakness” of the test data, on the contrary, by putting some irrelevant effort, you make things harder that they can be.

We can’t add any test case that doesn’t work well in your solution. There are actually infinite number of solutions that are wrong ones. Should we add the test cases against all of them? That looks like the infinite number of test cases. Quite exaggerated example: if you put a special condition of the form “if n=4568 then write -1 -1 -1 and halt”, your correct solution will surely pass all the test cases. Should we add this case with n=4568 to break your solution on purpose?

The question that puzzles me more is: why do you send wrong solutions to the simple problem if it doesn’t give anything to you? T-Shirt? Country prize? You should do much more to get a T-Shirt or a country prize. Instead of learning something new and exercising your mind, you just spoile all the fun and joy for yourself, deprive yourself of the experience and send a wrong (and a harder that the intended one, in the general case) solution. Maybe it will pass, but we can’t consider anything, you should understand this. Of course, if the problem would be one of the hardest ones, we would have rejudged the solutions on the updated test data set immediately. But this problem is just for giving fun for the beginning programmers. So, by sending a wrong solution that gives you AC, you hurt only yourself.

When I read things like “I have submitted a wrong solution on purpose”, I just can’t understand, why. Does it really gives the advantage to you? You don’t hurt anybody but yourself doing so. Moreover, if you get an AC with the solution that is harder than the very-very-easy intended one, this is not the reason to say that the test cases are weak - you’ve overcomplicated the things for yourself then.

Adding a new test case is a mess. Especially, if there are a lot of AC solutions already. We can’t add any test case that will fail O(1) solutions for satisfying every single person, this is not this kind of a problem. There could also be some problems with the testing queue stuck.

Of course, a lot won’t agree with my words and will downvote this comment. But at the end, you should mind that our preparation team is about ten persons, and the participants’ count is a few thousand. The participants are obviously in a majority, so they can find something that the team couldn’t find. But before blaming admins and saying things like “they are sleeping/irresponsible”, you should just estimate: how critical the situation is, won’t it make troubles or mess to change something, does it really necessary and worth of it? At the end, nobody prevents you from joining the testers’/setters’ side. It is always really great to see a variety of writers and new persons at all. You can always give your problems with any prefferences you want.

PS: @dcod does failing your solution or O(1) solutions is worth of calling the admins “sleeping/irresponsive/too lazy” in all these topics? We honestly process all the queries, but admins might have their own opinion, based on something to consider.

9 Likes
13

Can anyone tell why there can be only K^2 variations in the candidate AP’s and not N^N ?

2 Likes
14

same story --^–

15

My Intention was not to send the wrong solution , But I was just submitted my code to check what distribution of K in this problem, I was also expecting WA but I got AC this is also not my fault. If I have done this intentionally I never mention that I got AC with wrong solution. I was just a bit Lucky that I got AC with some AD-HOC solution.

With
Love

3 Likes
16

this problem is really buggy, @lakshman1988 exploited it. Surprised to see that solution doesn’t depend on the value of K.
“a solution which can not pass the sample test case, gets AC?” cant stop laughing :smiley:

3 Likes
17

I assume you are from the admin team for this question and I expected you guys to respectfully take some responsibility for weak test cases and bad question and everything would have been cool and dandy. On the contrary you come up with a wall of text scolding people. Definitely, there are some users who reacted really badly by calling admins “slow/unresponsive”. So let me break it down for you to understand properly.

“The problem is simple and the solution is very simple as well. If you go longer way and think on some overcomplicated ideas and spend extra time instead of just write the obvious thing, you make things harder only for you, not for anybody else”-

Setter of a problem should not be worried about how someone solves a problem. I can use basic arithmetic or I can use quantum mechanics. Should not be a setter’s as long as codechef supports it and solution runs within constraints.

The question that puzzles me more is: why do you send wrong solutions to the simple problem if it doesn’t give anything to you? T-Shirt? Country prize? You should do much more to get a T-Shirt or a country prize. Instead of learning something new and exercising your mind, you just spoile all the fun and joy for yourself, deprive yourself of the experience and send a wrong (and a harder that the intended one, in the general case) solution. Maybe it will pass, but we can’t consider anything, you should understand this. Of course, if the problem would be one of the hardest ones, we would have rejudged the solutions on the updated test data set immediately. But this problem is just for giving fun for the beginning programmers. So, by sending a wrong solution that gives you AC, you hurt only yourself.

So explain to me exactly how do people learn when they write wrong code, get accepted and walk away in pride thinking that they have cracked a codechef problem, which obviously they haven’t solved correctly?. But then bad things happen, we all commit mistakes in production. What do we do then? take responsibility of it and try to improve OR come out shouting like un-mannered men? Are you trying to say that codechef is some sort of charity that you guys are running and people should take away whatever they can and just sit back without uttering a word? Thats not how COMMUNITIES work.

When I read things like “I have submitted a wrong solution on purpose”, I just can’t understand, why. Does it really gives the advantage to you? You don’t hurt anybody but yourself doing so. Moreover, if you get an AC with the solution that is harder than the very-very-easy intended one, this is not the reason to say that the test cases are weak - you’ve overcomplicated the things for yourself then.

Algorithmic questions in most of the coding competitions are defined by their constraints and definitions. If people CAN break them they WILL break them. Ofcourse, I mean who wouldn’t be on cloud9 after realizing that they have actually CRACKED OPEN a codechef question just by guessing test data.

Of course, a lot won’t agree with my words and will downvote this comment. But at the end, you should mind that our preparation team is about ten persons, and the participants’ count is a few thousand. The participants are obviously in a majority, so they can find something that the team couldn’t find. But before blaming admins and saying things like “they are sleeping/irresponsible”, you should just estimate: how critical the situation is, won’t it make troubles or mess to change something, does it really necessary and worth of it? At the end, nobody prevents you from joining the testers’/setters’ side. It is always really great to see a variety of writers and new persons at all. You can always give your problems with any prefferences you want.

Will definitely give props to you guys on this. Its a tough job no doubt. But interfacing well with users is extremely important as well. And in my opinion, this question should have been sacked totally OR at least admins should have released an announcement on this during the competition. Unresponsive admins is frustrating. Bugged test cases/questions are not!

PS:

  1. Test cases were weak because they failed to differentiate wrong submissions from the correct ones. And if it takes infinite test cases to judge a solution then it means that the problem itself needs re evaluation.
  2. Production is tough!
  3. Keep up the good,tough work on codechef
10 Likes
18

I still can’t understand the solution. Can someone please explain it, preferably with an example?

5 Likes
19

If I brute force first and last element of sequence which will not change, won’t there be O(N*N) variants?

20

Since we cannot change more than ‘k’ elements the last element(read maximum) has to be one of the last ‘k’ (read maximum ‘k’ elements of the list). Same holds true for first element.