Блог пользователя snarknews

Автор snarknews, история, 6 лет назад, По-русски

Традиционно проект SnarkNews проводит голосование "Итоги года".

Цель голосования — отметить лидеров спортивного программирования прошедшего года — как участников, так и тренеров, а также наиболее удачные проекты и наиболее удачные публикации в прессе.

В настоящий момент проходит первый этап — выдвижение номинантов. Первый этап проходит до 13:00 31 декабря. Желающие опубликовать своё предложение по номинантам (и подискутировать по этому поводу) могут сделать это в комментариях к данному сообщению.

В этом году голосование вновь проходит на базе системы Яндекс.Контест. Соответственно, предложить номинантов может любой, кто имеет логин в этой системе. При входе в систему описаны правила; для перехода к конкретным номинациям и выдвижению номинантов перейдите в раздел "Задачи"; справа появится список номинаций. По каждой номинации принимается не более двух вариантов; каждый вариант задаётся в отдельной строке в соответствии с правилами номинации (которые находятся на том же экране, что и форма отправки).

UPD: Первый этап голосования завершён; в начале января эксперты объявят списки для второго этапа голосования (который пройдёт по той же схеме, что и в прошлом году). Благодарим всех за активное участие!

Кроме того, Простой Новогодний Контест и Новогодний Блиц-Контест в этом году также пройдут на базе системы Яндекс.Контест; по сравнению с прошлым годом особых изменений в правилах не ожидается.

Открыта регистрация на Простой Новогодний Контест.

Простой Новогодний Контест — начался 30 декабря в 0:00, завершится 10 января в 23:59. Состоит из задач, предлагавшихся на различных командных соревнованиях по программированию в 2017 году, но так и не решённых в основное время.

Зарегистрироваться можно в любой момент до окончания контеста.

Новогодний MLR Блиц-Контест проходил с 31 декабря в 18:00 до 6:00 1 января по правилам Multiple Language Round (то есть за каждую задачу, успешно сданную на языке программирования, на котором участник ещё не сдал ни одной задачи, начисляется бонус -100 минут от штрафного времени) и по правилам Новогоднего Блиц-контеста (отличие от системы ACM в том, что время отсчитывается не от начала, а от 0:00 1 января по времени сервера, то есть и успешная сдача в 23:55, и успешная сдача в 0:05 дают штрафное время 5 минут).

Победителем Новогоднего Блиц-Контеста стал Endagorion, решивший все 13 предложенных задач и использовавший при этом 12 различных языков программирования. На втором месте Golovanov399, также решивший все 13 предложенных задач и использовавший 10 различных языков программирования, на третьем — pwild, решивший 13 задачи и использовавший 5 различных языков программирования. Поздравления победителям!

Итоговые результаты

Задачи для Новогоднего Блиц-Контеста были взяты с российских школьных олимпиад, а также российских и зарубежных командных региональных соревнований.

  • Проголосовать: нравится
  • +76
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Yes, Prime Contest is announced, now I can sleep peacefully :).

»
6 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

I am willing to offer special prizes to first solvers of problems 19 and 23 (because I set them). =)

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +41 Проголосовать: не нравится

    Hello, desert97 and ksun48 were able to crack this one. (submitted under handle snoweverwyhere) Took us quite a long time.

    What's our prize? =)

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Isn't the problem 23 from Winning Ways for Your Mathematical Plays?

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      It could be! I didn't read the entirety of WWFYMP and didn't see this problem there. There is a similar problem in ONAG (Conway's On Numbers and Games) with triminoes instead of dominoes. The triminoes game is kinda complex, but happily the dominoes game can be analysed with relatively simple tools.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Huh, it seems that you set 2 out of 3 hardest problems from this New Year xD (where I mean, hardest to do during contest). Third one was in my opinion 11 "Boring Game", which I consider hardest problem in whole problemset if we exclude possibility of using Google. Coming up with these formulas for multiplication of nim is literally impossible, but on New Year we may google something what explains a few ACs.

    I am kinda sad that I chose to google 23 as well. After few hours of experimenting I had literally everything, needed only a wrapup of all my thoughts, but chose to give up :(. As soon as I saw this problem I thought about assigning some  ± 2 - k values to every strip of contiguous dots. I noted a period of 6 if borders are fixed in results of form "WHITE/BLACK/FIRST/SECOND" and correctly classified all games where there is only one segment of dots. I noted that FIRST and SECOND are basically positions of value zero and that we can reduce SECOND completely and just count the parity of FIRST parts which will determine result of game if nonzero parts sum to zero. I noted that B..BW.....WW.....W (or B2BW5W5W) is in fact game of value zero (what can be a hint that value is divided by two every three dots). But as I noted that my backtrack on long longs fails to properly process game B2BW5W5WB2BW5W5W I decided to gave up xddd. After that it took me I think more than hour to get WWFYMP and find a place where it is described. Just to find out I basically got everything figured out by myself...

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Btw will there be editorials to the problems after the end of the contest? (I'm curious about the Prime contest)

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Now the new year contest standings don't look like it counts from (in both directions) the midnight, is it supposed to be this way during the contest?

»
6 лет назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

Problem L be like

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve G and J (from New Year Blitz Contest)?

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

How to solve H (hardcore sequence)?

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

It seems that tests to "17. Cat and Mouse" are not as strong as they can be. I submitted three codes that got OK. First one is fine, second one has first bug, third one has second bug. Third code fails on a case

1
18 2
6 2
14 9
12 11
2 1
4 3
18 15
10 2
13 5
17 15
8 2
9 8
5 4
16 15
15 13
7 2
11 6
3 2

and second one fails on a case

1
11 9
2 1
3 2
10 9
11 7
9 6
7 4
4 3
6 5
5 3
8 3

I have not done these bugs on purpose after getting OK, I discovered them during local stresstests. They were appearing very rarely, maybe once per 10000 small random cases each of them. It would be very hard to create tests against them by hand, one would need to know my exact algorithm and thought of specific bugs I could have done, but it was very easy to create tests against them using stresstests. This problem had testcases, so it was very easy to do something like (T<=1e5, but sum of n's <=5e6) instead of (T<=100, n<=5e4) and if I would be given 1e5 random testcases with n=20 I would have surely failed them using second or third code.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Lolwut xDDD. In "Line Tracing" problem I struggled a lot and couldn't make my robot work on 10th test (this problem has open tests, but there's not really a way to use this). Just for fun and for sanity check I pass small tests I submitted my code to Yandex that don't pass it (it hasn't passed it at any point of its life) and expected WA on test 10. Imagine my surprise when I got "Verdict: OK, Status: Full solution" result xDDD. After this I tried few random seeds and it worked for something like 6th of them. However Marek claims that my code with his checker worked 7 out of 10 times on this test.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    As the author of this problem, I'd be very happy if you share your approach and thoughts about the problem after the contest end (like, did you like the problem at all). Random pass/not-pass is somewhat expected (it definitely happens "in real life"), but I'm still curious.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      Hello :). So as I imagined such robot following rom real life, I imagined that it should go more or less straight and make corrections to his direction on the fly. After mnbvmar explained his approach to me, I realized I was not very creative, because his was substantially different and obviously better, but it looks like mine also can be made to kinda work.

      I think that seeing my code may help understanding what I did, so here it is: https://ideone.com/yenxK5 Relevant part starts from line 894 (xD) (disclaimer: my comments may be kinda misleading). Let me firstly decribe how I made it to follow simple straight line. I made three modes of work: "go straight", "return with one wheel to track" and "while on track but rotated significantly, fix it".

      1) If sum of two sensors is big (>1.8) then I simply go straight.

      2) If it isn't, but one of sensor's reading is big then I try to fix position of that wheel which is out of track by doing either Go(0, 0.5) or Go(0.5, 0).

      3) If both sensor readings are small then both wheels are on track but whole robot is significantly rotated from its desired direction. Assuming my sensor readings are accurate I may determine angle by which it is rotated, but I can't determine whether it is rotated left or right. In order to determine this I go little back and forth (Go(-0.3, -0.3) and Go(0.3, 0.3)) and see which sensor reading decreased and which increased which helps me to determine this. Btw sometimes if I'm unlucky these perturbations may significantly broke this part, but I can validate if what I got is sane and it it isn't, I repeat this step. After that I try use few calls of form Go(x, x) to put center of my robot to polyline and then rotate it by appropriate angle that I already know.

      For polyline which is a straight segment this already works really well and uses small number of steps (~10000 for segment of length 4000). However turns are really troublesome to that approach. If my robot is in one of first two modes it is still fine for him to perform corresponding moves, but as it is right now it can go crazy in third mode. I understood that main problem is that part with determining angle of rotation where I use Go(-0.3, -0.3) and Go(0.3, 0.3) because being close to next turn may significantly lower one of my readings which will make my computations rubbish. If there's no turn blose to me I expect that Go(-0.3, -0.3) will increase add correspondingly x and -x to my sensor readings. for some significant x (either positive or negative, but not very close to zero). If I see that this is not the case then I conclude that I am close to turn and turned in more or less good direction, so I do Go(1, 1) in that case (lines 926-930).

      Best what I got locally was something like never passing 10th test (but able to sometimes pass ~150 out of 300 points), sometimes passing 9th sometimes not and passing all the rest. But with really tiny change to this code and seed it was passing 8 points on both 9th and 10th test xd.

      mnbvmar's approach was much better. He basically was standing still with one wheel and dragging second one along halfcircle. In other words, alternately doing groups of Go(1, 0) and groups of Go(0, 1) moves. Within every group he was doing it until that moving wheel falls on track again. He said that his approach was very robust in a meaning that once he coded it correctly it immediately passed all tests, but just with a little bit too many steps (~20500), so he was doing something like Go(0.05, 1) instead of Go(0, 1).

      Regarding my thoughts about this problem. They are kinda mixed. It is really an unconventional one and kinda fun, but once everything is more or less fine there is a big possibility of drowning into small details, investigating what went wrong in our 10th attempt etc which may be a black hole of suffering. When sitting at home coding New Year contest it can be tolerated, but on ACM, one of possibly most annoying things is hearing your teammate saying for the 10th time "allow me to code, just one more fix and it will surely work!" — in this problem it would be kinda unavoidable. I really felt relieved when I completely unexpectedly got random OK :P. Nice experience to have it once, but solving such on regular basis would be tiring. But maybe this was just my punishment for taking a wrong approach to it instead of much clearer one that Marek came up with.

      Btw I was also kinda annoyed that having a visualisation to this problem would really help, but I was unable to make it because I couldn't have spent as much time on this problem as it would require in my case. Getting to know what went wrong would be much easier. I think it could be a good idea if there would be a dedicated tool for this prepared in advance by organizers.

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

        Do you have any ideas on how to distribute such a visualization tool? The problem is that we cannot assume that any of Java, C++ compiler or Python are installed or even can be installed—people use Windows on their university machines without admin rights. The best we were able to come up with is an HTML with some JS (everyone has a browser to submit solutions, right?), but then we have to somehow transfer data from the solution to the visualizer.

        Btw, the official solution is 19 lines with all includes.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          University machines in computer science faculties without Python? I'm surprised.

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится

            Well, "computer science faculty" is a pretty posh thing to have. Who needs Python when you only teach PascalABC or Matlab?

            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Huh? Who is your target? Wasn't competition where it was posed held at some university or somewhere where all competitors have same workstations? Or do you mean that you can't assume a student taking part in New Year have C++ or Java and his only possible workstation is university machine with prehistoric software?

              I think that providing a tool that gets as input two broken lines in format "n x1 y1 ... xn yn" and draws two of them after some given line that needs to be executed that either runs some C++ or Java program locally would be fine.

              • »
                »
                »
                »
                »
                »
                »
                »
                6 лет назад, # ^ |
                  Проголосовать: нравится +8 Проголосовать: не нравится

                There are two primary targets: SPb SU championship (where there is indeed some standard software) and OpenCup Grand Prix where sectors can be held by random universities and there are very little guarantees about the software (if any).

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 лет назад, # ^ |
                  Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                  So, how do these random universities compete if all they have is Pascal and Matlab? If something wouldn't require installing some new packages or upgrading Java, I wouldn't care and assume that everybody has some not brand new version of g++ compiler and I hope it is sufficient to create such a tool using only this. Maybe it would not be ideal solution, but I think having visualiser for teams that would actually try doing this problem (probably only few teams from top) would help more than one random university not having g++ complaining would hurt.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 лет назад, # ^ |
                    Проголосовать: нравится +8 Проголосовать: не нравится

                  Well, Pascal is good enough for a lot of problems. I would not expect g++ in Russian universities at all, something like Visual Studio 2003 is much more expected.

                  for teams that would actually try doing this problem

                  That's a good point, but I don't know any good way of estimating difficulty of an unusual problem, and definitely don't want to disqualify teams merely on the fact that they don't have some obscure software installed (e.g. gcc newer than 3.4.5, Java >= 7 or Python >= 2.5). Moreover, if we write in C++/Java only, it definitely disqualifies teams which do not know the other language.

                  I think the way to go in the future would be to provide a web-based tool with no useful stuff inside and a bunch of generic formulas/functions in all languages supported by OpenCup. I believe it shouldn't be a problem to generate a bunch of C-style functions like go(double motorLeft, double motorRight) which assume that there are some global variables which hold the state.