UASEQ - Editorial

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

9 Likes

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

Could anyone please elaborate on the brute force technique

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

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.

6 Likes

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

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.

13 Likes

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

2 Likes

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
11 Likes

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

5 Likes

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

You say that we should fix L and R, but in the example we change L. Why isn’t that a contradiction?

Also, what implies that L < R?

And also, can’t I make an example with a result with infinities? (if K >= N - 1)?

Well I dont think that writing tough test cases is a big problem. When you sit in a group of 10 people, you try to read the problem and try to think that what are all the different ways in which the problem can be misunderstood and give an appropriate counter-example.

Then, even if some ‘wrong’ solutions getting AC are reported, then you should not hesitate from adding tougher test cases, as no one would like a wrong solution be considered as accepted.

In the past few contests I have observed this weak tests problem a lot. I think we would get nowhere if we just solve the problem the way we like and you give AC and make us feel happy. Further it is a ten day long contest and no one should mind the addition of tough test cases as you are still left with considerable time to retry (compare 2 or 5 hour contests).

Also it should be a duty of testers to frequently go through the accepted solutions and try to challenge/hack them and add those cases for all solutions (and you may call the system as Dynamic Solution Testing System) and rejudge all at the end.

At the end of the day, correct solutions will pass all the test cases, no matter how they (solutions as well as cases) are generated.

2 Likes

What has happened here is unfortunate.

We, as admins, admit that there were mistakes in the problem that could and should have been avoided or corrected when brought to the fore. This is an undesirable situation. We have spoken to our problem setting panel and there is no disagreement on this any more. What has happened in the contest cannot be undone and we regret that. We have requested the problem setter and the tester to fix the test data by adding many more test cases and make the test cases stronger in the practice section.

However, we must understand and appreciate the effort and the pain it takes to make a problem and to test it, especially since the panel members have other academic/professional commitments as well.

We will also try and make sure that the communication from our end to the panel happens clearly and there is no ambiguity on this any more. This should not happen again. We apologise for this incident.

1 Like

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

2 Likes

“Access Denied” while accessing solutions.

3 Likes

How to determine L and R

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

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

same story --^–