Find the product of the two highest speeds

Question

I wrote the EGE on computer science, today the results became known. For some reason, in C4 I was given only 1 point out of 4, although the task is the simplest. Unfortunately, I do not have the exact wording of the task, so I will write from memory. First, the number N (the number of particles) is entered, then the N velocities of the particles (according to the condition from -10000 to 10000). It is necessary to derive the product of the two highest speeds. And it needs to be done effectively in memory and calculations. Here is my code (right from my work):

#include <iostream> using namespace std; int main() { int N; cin >> N; int m[2]={-10000, -10000}; for(int i=0; i<N; i++) { int mi=(m[1]<m[0]); int v; cin >> v; m[mi]=(m[mi]<v)? v: m[mi]; } cout << m[0]*m[1]; return 0; }

I checked it on my computer, everything works fine. The program is effective because it does not add all the numbers to the array, but counts everything as you enter numbers. If you do not find an error in the algorithm, I will go on appeal. Either I misunderstood the condition of the problem (here you certainly will not help me), or the verifiers did not like the smiley (m[1]<m[0]) , or they didn’t check my additional answer form on which the second half was written solutions.

Update

I have other suspicions here. It is possible that my code was not checked at all, because the organizer in the PES incorrectly wrote the additional form number and boldly corrected the number 7 to 3. It is possible that the computer accepted this number as 8 and because of this checked only part of the task on the first form, where Algorithm written in Russian language. This is confirmed by the fact that in the evaluation criteria it is written that one point is given if “according to the given text of the decision it is clear that the subject understands what stages the problem should be solved”. Just the fact that I downloaded all my forms on the Internet contradicts this.

Update 2

Everything, found an error (see my answer). Everything cleared up, I will not go on appeal.

northerner

The algorithm is very bad. Really bad. Just 1 point. And yes, I am an expert exam.

Is that better?

 #include <iostream> using namespace std; int main() { int N; cin >> N; int m[2]={-10000, -10000}; int n[2]={10000, 10000}; for(int i=0; i<N; i++) { int mi=(m[1]<m[0]), ni=(n[1]>n[0]); int v; cin >> v; if(m[mi]<v) m[mi]=v; if(n[ni]>v) n[ni]=v; } cout << max(m[0]*m[1], n[0]*n[1]); return 0; }

At first glance, if the input is normal and N> 1, then it is correct.
She is most likely checked by Aunt Tanya, who has nothing to fumble with in programming, she has a response sheet, it is written there, while the letters do not match, there is no bubble for her in the envelope, hence instead of 4 - 1
Apparently it did not coincide with the answers :) In my opinion, everything is correct, if you do not take into account the extra assignment of m [mi] to yourself in the event that not a large number has come.
Excellent code, the creators of the exam on this is not apparently calculated.
@sercxjo, if you are talking about a specific code m [mi] = (m [mi] <v)?

Accepted Answer · 2012-06-07T15:33:27

The author incorrectly wrote the condition of the problem in the subject; it is necessary to find the maximum of the products of all velocity pairs, and not the product of the two highest velocities. The criteria for scoring one point clearly states:

Only a partially correct solution algorithm has been proposed: the program searches for the values of only maximal elements.

There was an unhealthy discussion about the fact that, they say, school teachers do not understand anything in programming, so the work was stabbed to death. So, I mean, in this case, everything is completely wrong, one point is set fairly.

northerner

3,978 eleven 15

2
> An unhealthy discussion took place here that, supposedly, school teachers do not understand anything in programming. Actually, I had such a teacher at school in my school. In diagnostic works, only parts A and B checked the answers, but C did not even look. He gave the specification and said to check for yourself. True to becoming an expert, he did not pretend. - gammaker
This is true, it happens. The expert commission of the USE is formed by 50 to 50 of school teachers and university professors. It is interesting how your teacher acted from the last statgrad training work, where the correct answers were mixed between the options. To the question of @avp (the limit of comments ended there): it depends on the context, I would write something like that on solving the olympiad server, I would avoid it in a serious project and would not recommend it to other team members. - northerner
one
M ... But is the product of the two highest speeds not equal to the maximum product of all the pairs of speeds? - oleg_ismaylov
@oleg_ismaylov -10000 * -10000 - Costantino Rupert
one
@oleg_ismaylov - No one has yet canceled the projection of vectors. - If you really want to continue this conversation, then the speed as a vector quantity cannot be positive , since in this context only the positivity / negativity of any R1 metric entered for the vectors makes sense. - And yes, if we talk about speed as a vector quantity, how do you imagine the product of speeds in the context of this problem ? - Costantino Rupert

|

Costantino Rupert Costantino Rupert 22.6k one 28 52 · Answer 2 · 2012-06-07T12:56:31

It seems to me that if you would write a program similar to yours, but not doing Code golf'ом , you would get 4/4 (if, of course, conditions like N >= 2 really figure in the task) . Potentially, it was still possible to check input for correctness.

 #include <iostream> #include <cassert> int main(int argc, char* argv[]) { static const int MIN_VALUE = -10000; static const int MAX_VALUE = 10000; int n; std::cin >> n; assert(n >= 2); int firstMaximum = MIN_VALUE; int secondMaximum = MIN_VALUE; for (int i = 0; i < n; ++i) { int velocity; std::cin >> velocity; assert(velocity >= MIN_VALUE && velocity <= MAX_VALUE); if (velocity > firstMaximum) { secondMaximum = firstMaximum; firstMaximum = velocity; } else if (velocity > secondMaximum) { secondMaximum = velocity; } } std::cout << firstMaximum * secondMaximum; return 0; }

> but not doing Code golf. For me, this construction is familiar, I use it for a long time, and I do not see anything complicated in it.
It takes me less time to invent and write it than to write these big ifs.
@GLmonster Only you forget that you are not writing code for yourself, but for other people :)
Competent, understandable, effective, easily modified ... Just a sample for different exams.
Ideally, the whole code should be clear to whom it can be transmitted.
Sometimes it takes too much time to understand, and it becomes scary to add something already
And alas, we cannot know those who are checking the exam, (if one of us would check, we would most likely get 4/4 :))

gammaker gammaker 4,938 14 27 · Answer 3 · 2012-06-07T14:07:53

Something learned on the Internet. It turns out that I did not take into account the fact that the product of two large in magnitude negative numbers can be more than positive, and by condition it was necessary to specify the largest product, and not the product of the largest numbers. Darn...

gammaker

4,938 14 27

Well, that makes it all clear :) - KoVadim
Sorry, so much discussed, and the program solves the wrong puzzle ... - avp
one
But not one point! The criteria for task C4 (albeit different) says: "Three points are also set if there is one mistake in an effective program that meets the criteria for scoring 4 points, as a result of which the program works incorrectly on some sets of atypical input data." > It’s a pity, we’ve been discussing so much, and the program is solving the wrong puzzle ... And what a pity for me ... I don’t even know if I can appeal now. Okay, I'll go anyway, probably. - gammaker 2:21 pm
2
I think it's worth pointing out in the question text - Specter
2
No, there is obviously one point. One to one by the criteria. I actually sympathize with the author, because this year every primary C4 point is worth three points in the 100 point scale, therefore, losing 3 primary points you lose 9 at once - and this is somehow too tough, but, alas, you can't do anything. - northerner

|

avp avp 37.3k 3 35 90 · Answer 4 · 2012-06-07T11:48:02

@ Kitty , mi = (m [1] <m [0]) this is correct ( hacker ).

The use of boundary values for the algorithm is quite in the spirit of, say, D. Knuth.

But to N <2 you can really find fault. But if you do not find fault, then IMHO super. I would go on appeal.

I don’t think that someone needs the famous “hacking” , KR-like way to code something, etc.
But to write code that Aunt Tanya and Uncle Vasya will understand is also an art.

jmu jmu 6,042 ten 21 · Answer 5 · 2012-06-07T12:53:02

it is likely that while writing the exam, you missed some important detail that you considered insignificant. and since you reproduced the task from memory, the probability that you missed it during reproduction is even higher ...

any consideration of the code does not make sense until the exact ToR is presented.

> it is likely that at the time of writing the exam, you missed some important detail that you thought were insignificant. I admit that I could have misunderstood the condition, but I don’t have it.
But the source code is exactly the same, I rewrote it from the scan of the work sheet.
> any consideration of the code does not make sense until the exact TZ is presented. Unfortunately, it will not.
@GLmonster, try to search for similar tasks in nete - they say, some variants of tasks can be found, maybe yours will meet among them

Answer 6 · 2012-06-07T12:03:00

Algorithm Pts. good. Really good. Especially like the expression mi=(m[1]<m[0]) - this deserves a separate praise for coding half-forgotten Kernighan-Ritchie calm. We must go on appeal.

Update

@Northener wrote:

The author incorrectly wrote the condition of the problem in the subject; it is necessary to find the maximum of the products of all velocity pairs, and not the product of the two highest velocities.

It certainly changes everything. In this case, the algorithm does not work correctly, alas. But the author is still well done - I got aesthetic pleasure from the proposed algorithm.

And then you evaluate the students, and we then give them work.
@northerner And how do you put things like mi=(m[1]<m[0]) when setting the total score?
@ Kotik_khohet_kusat, used designs and style do not play a role.
Good or bad is another question, the fact that the criteria explicitly define the rules of the game.
True, for this, each job is checked by two people separately, with a difference of one point a large score is put, with a larger difference a third expert is included, and an appeal is foreseen.
But still I recommend to write humanly - the probability of cutting off the right decision is lower.

KoVadim KoVadim 85.4k four 66 126 · Answer 7 · 2012-06-07T12:23:45

Something I did not see, what would someone wrote about negative speeds. If we leave aside the fact that we need another direction vector, then the negative speed is just movement in the opposite direction. In the source code, I would correct the initial values by int m[2]={0, 0}; and when entering the speed would take on the module.

But I would not write the expression mi=(m[1]<m[0]) on the USE. When interviewing - it is possible (and sometimes even necessary), for the exam - not worth it.

KoVadim

85.4k four 66 126

one
and I do not claim that it will return only 0 or 1. I did not find such an assertion in the standard. Therefore, the exam and should not do so. But at the interview, when we can choose a compiler, it is possible to use it, it will be easier to explain there. - KoVadim
3
The classic problem is that we either write three lines right away and get a good ball, or we write one, then we go, we prove. As for me - the first is significantly effective. So the topstarter solved the problem is not optimal. expression (m[1]<[m[0])? 1: 0 (m[1]<[m[0])? 1: 0 - more beautiful. But in general, the task is written in c, not c ++. - KoVadim
2
@GLmonster - there is no fundamental difference between if and mi = (m [1] <[m [0]), and there and there most likely a code will be generated that will subtract one number from another and check the flags, only the second option strongly depends on the hardware and the compiler versions and settings without introducing an understanding of the code, whereas the if option will give the code more easy to understand without losing the quality of the generated executable code. - Chad
2
@KoVadim, I found such input data when the code does not solve the task I checked on your example, and also when all numbers are equal - not everything works (the program is correct). - avp
3
@KoVadim Zero speed is greater than negative. If, of course, the module did not appear in the task. - Costantino Rupert

|

Answer 8 · 2012-06-07T14:53:28

I do not share the enthusiasm about the hacker-Kernigan code.

 int mi=(m[1]<m[0])

Think about what type of data the rvalue returns and what type you declare for the lvalue , considering that we are talking about crosses , and not about Ritchie’s bearded times.

What answers can be, if in programming of results - millions?

About the correct (manually checked!) Answers to a specific test data set. Do you know how unit tests work?

In general, as already noted by previous speakers, not remembering the exact assignment, it makes no sense to evaluate the correctness of the implementation, and it remains only to assess the style, which, as it was also noted, is probably good for the codegolf, but not for reading by a person who is more critical and on which the assessment of work depends.

karmadro4

2,142 one eleven 15

2
> Consider what type of data the rvalue returns and what type you declare for the lvalue. Apparently, bool, which is converted to an int. > Further, by the way, you have a potential exit from the array. true - 1, false - 0. How could it be different? > we are talking about crosses, and not about the Ritchie-bears' cowardly. But what about backward compatibility? Is it not even in such trifles that backward compatibility is preserved? - gammaker
one
@ karmadro4, in g ++ the code works. Most importantly, the author demonstrated a non-trivial approach to finding 2 maximal elements, i.e. creative thinking, as well as the ability to write compact code in the face of time pressure (exam). @GLmonster, very interesting, but how many programs should I have written and for how long? - In these conditions it is 5+. Another question is if the code solves the wrong task. Then, from automated tests, only compilation and execution with a return code of 0 will pass. - avp
2
@GLmonster Programming in C++ , based on backward compatibility with C , is the worst thing you can do. From here, a rake is born with millions of new / delete in the code, things like operator bool , and from here grows the use of int to store the value of the Boolean expression and the C-style caste, breaking the use of vfptr and vcbl . If you really want to write in C++ , use bool to store boolean values. - Costantino Rupert
one
@GLmonster - The statement about the implementation-specific bool, seems to be incorrect, or I incorrectly interpret clause [ 4.7 - Integral Conversions ] [1] of the C++ . If it is converted to zero, it is converted to one. [1]: open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf#page=98 - Costantino Rupert
one
@ karmadro4 I was just recently shocked that I had [this page here] [1] hit the top 16 chrome tabs :) [1]: hashcode.ru/users/6679/karmadro4/recent - Costantino Rupert

|

Find the product of the two highest speeds

Update

Update 2

8 answers 8

More articles: