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.


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.


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; } 
  • 2
    At first glance, if the input is normal and N> 1, then it is correct. Maybe it should consider options with N <2? - avp
  • 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 - Gorets
  • 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. - sercxjo
  • 2
    Excellent code, the creators of the exam on this is not apparently calculated. - margosh
  • 2
    @sercxjo, if you are talking about a specific code m [mi] = (m [mi] <v)? v: m [mi]; instead of if (m [mi] <v) m [mi] = v; then you are right , and I got excited. The if option is better. - avp

8 answers 8

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.

  • 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
  • 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. - gammaker
  • 7
    @GLmonster Only you forget that you are not writing code for yourself, but for other people :) - Costantino Rupert
  • Well what can I say. Competent, understandable, effective, easily modified ... Just a sample for different exams. - avp pm
  • @ Kitten fiercely plus a code account for others. 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 - rasmisha
  • one
    @GLMonster nobody considers it difficult here. Only here you have 3 lines. And imagine when such a code at least 1000 lines. And alas, we cannot know those who are checking the exam, (if one of us would check, we would most likely get 4/4 :)) - rasmisha

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...

  • 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

@ 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.

  • 6
    I don’t think that someone needs the famous “hacking” , KR-like way to code something, etc. on the exam. But to write code that Aunt Tanya and Uncle Vasya will understand is also an art. Of course, as IMHO . - Costantino Rupert

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. Therefore, I try to exclude at least everything else. 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. Well, on the appeal I find out. - gammaker
  • 2
    @GLmonster, try to search for similar tasks in nete - they say, some variants of tasks can be found, maybe yours will meet among them - margosh

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.


@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.

  • 3
    > We must go on appeal. Tomorrow I'll go write a statement. - gammaker
  • four
    > Algorithm Pts. good. Really good. The algorithm is very bad. Real bad. Just 1 point. And yes, I am an expert exam. - northerner
  • @northerner, explain in detail. And then you evaluate the students, and we then give them work. Interestingly mismatched criteria. - avp
  • 2
    @northerner And how do you put things like mi=(m[1]<m[0]) when setting the total score? - Costantino Rupert
  • one
    @ 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. Another thing - the human factor. An expert may be mistaken. 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. - northerner

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.

  • 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

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.

  • 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