ariel.nowik's blog

By ariel.nowik, history, 9 years ago, In English

As everybody should know, last friday the Wunder Fund round has taken place here. I had unbelievable bad luck because that day I needed to travel 400 km to another city in Argentina to some holidays so I was forced to do the round... on a mobile?? I managed to solve that way only the easiest problem 1 using android c++ application while I was in the bus, luckily the first task was a typical procedural problem were the solution was pretty easy. At first I though it was very similar to the popular 2048 game, but in this case only 1D and not only 4 numbers. However being using my mobile phone I was confused about some details and then I realised... it was not the sum but the value of the combining numbers plus 1, so I switched from doing an intelligent binary transformation solution to a mere live simulation of the procedure with a vector. I managed that way to get accepted and switched to second problem that was not so easier, but easy to figure out the solution because the solution ramification has a nice property, that is every path make you to complete a valid sequence that follow the rules, so you can easily first find any good chance for first number, then for second (of course it can not be same as first), third and until N always choosing the first available number that makes the table valid. Of course I couldn't realize that when using the mobile so I only submitted it by the time contest finished. I also give a try to third problem, and because of my lack of experience in computational geometry I used the techniques I learnt on the problem of google code jam round 1A 2015 logging, where the solution was to sort the points by their angle relative to other point. In this case it was somewait similar. To form an empty triangle you could sort angles of points relative to some point (I my case I decided the center to be point 1), then find to consecutive points in this sorted list that are nearer than 180 degrees (I consider a change the combination of last number of the list and first number of it like a circle list), and then to avoid points to be inside the triangles of that points, if any of those two points has more points with the same angle but smaller distance, replace by the one more nearer. I got sick getting tons of wrong answers and I think one time limit, because of the CRAZY epsilon used to compare if long doubles were equal, * * plus * * in the end I realized that I needed to change atan2() function (used to get easily the angle relative to one point) to atan2l() and by the way get more precision. Then I get even more crazy. If I added too many zeroes to the EPSILON then case 20 failed, but If I kept to little then case 51 failed. I don't know way but there was a point between them in which I get accepted. The lemma? Doubles are definitely horrible, now I understand IOI syllabus. I will try to code the version that does not use angle calculations, because in a real contest you can not be dealing with such precision issues, that cost you lots of wrong answers submissions, which here, in codeforces, are unacceptable. Good luck guys, I will see if I get time to compete in the next round, maybe I will do it in my car with the mobile 4G because I am traveling again at that time....... bad luck again :( hehe will be funny though

  • Vote: I like it
  • -21
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ariel.nowik (previous revision, new revision, compare).