snarknews's blog

New Year Contests from SnarkNews
By snarknews, history, 7 years ago, translation, In English

Traditionally, SnarkNews runs two New Year Contests.

The New Year Blitz Contest (Multiple Language Round) will start at 18:00 31.12.2017 and ends at 06:00 01.01.2018 Moscow Time. Contest consists of 12 problems. Some of those problems are based on problems, used at official or training contests in 2017. Contest rules are based on the ACM system with two important modifications.

  1. Penalty time is calculated as distance between time of first successful submit for the contestant on this problem and 0:00:00 01.01.2018, i.e. successful submissions at 23:50:00 31.12.2017 and at 0:10:00 01.01.2018 will both have penalty time 10 minutes (600 seconds).

  2. Multiple Language Round rule: If for the first successful submit for the contestant on the some problem was used the programming language, which was never used by this contestant in his previous first successful submits on other problems, contestant receives language bonus: his summary penalty time is decreased by 100 minutes (6000 seconds). Note that different implementations of the same language are counting as same language, i.e. Java 6 and Java 7 are both counted as Java, C++ 32 bit and C++11 64 bit both as C++. Additionally, C and C++ are counted as same programming language.

Contest will be running on Yandex.Contest system. Link for registration and participation.

14'th Prime New Year Contest will start at 0:00 30.12.2017 and finish at 23:59 10.01.2018 Moscow time. Traditionally, Prime New Year Contest consists of problems, which were presented at team programming contests in 2017 and never solved on the contest. For the Prime New Year contest plain ACM rules are used.

Idea of Prime Contest was first implemented by Andrey Lopatin and Nick Dourov at Summer Petrozavodsk training camp at 2003; in Russian word "Prostoj" used in meanings "prime" and "easy", so, contest was called "Prostoj contest" but was composed of extremelly hard problems, numbered with prime numbers (2,3,5 etc). Since then such a numeration is traditionally used for contests, consisting of very hard problems only.

Contest will be running on Yandex.Contest system. Link for registration and participation.

Both contests have English statements. Registration is open till the end of the contest.

  • Vote: I like it
  • +76
  • Vote: I do not like it

Comments Comments (31)
| Write comment?
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +41 Vote: I do not like it

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

    What's our prize? =)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

      Specifically, we did 23, not 19.

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Great job! Please PM me your mail address so that I can send you something. =)

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Check the special standings (link at the upper menu)

    → Reply
»
7 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Problem L be like

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve H (hardcore sequence)?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Just print n random values from 1 to 1000000000 (and watch out for integer overflow).

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Thx, I did just that, I guess I had overflow :p

      → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    I've submitted somewhat uniformly distributed integers in range [0, 10^9]:

    int x = 0;
cout << 0;
for (int i = 1; i < n; ++i) {
    x += i + n * 9;
    cout << ' ' << x;
}
    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Also this

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it +20 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                  Vote: I like it +8 Vote: I do not like it

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

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 years ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  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.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 years ago, # ^ |
                    Vote: I like it +8 Vote: I do not like it

                  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.

                  → Reply