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

Автор misof, история, 6 лет назад, По-английски

Wow, time does fly when you're having fun. I'd swear it was just a few years ago when... but well, the numbers don't lie. This year it's the 20th edition of the IPSC, a programming contest with a twist (or two, or five, depending on the year). If you haven't yet had the pleasure to take part in the contest, click through to our website and check out the section "What makes IPSC different?". And if you already did, this is your reminder to register :)

The contest itself starts on October 6th at 15:00 UTC.

If you already did take part in some of the past years, which was your favorite problem, one that you still remember?

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

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

Well, I made a short announcement a few weeks ago, but the more reminders people have, the better.

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

Wow, such hard questions. I am participating since 2013, so I glance through editorials of 5 last contests to remind myself most interesting problems :)

2013 P (Plus one). Yep, the problem from practice tour. Actually, my teammate was solving the practice tour, and then he told us about that problem. That's how I understood that it will be an evil but awesome contest :)

2013 F (Feeling lucky?). That was the problem that I was solving. I was kinda stupid at the time, so I used almost the same approaches for easy and hard. The editorial said that it was nearly impossible to get AC with that simple approach in hard, but I did it first try. Also, I did everything by hand. I just like weighting puzzles, and it was first not-easy IPSC problem solved by me, so I remember it well (this one I remember without looking through editorials).

2014 J (Judging programs). Oh, I like problems about investigating code. Please do more! Also, cool trick with pseudorandom generator which is binary counter.

2014 L (Let there be sound). I didn't like the problem, but I remember it very well because it introduced me the song about badgers, mushrooms and snakes which then was on my playlist for a long time.

2015 M (Make*me-an+[integer!]). This problem killed about half a contest for both my teammates, so basically, I was on my own for two or three hours.

2016 K (Kill switch). Another cool problem about investigating code.

2016 M (Mana troubles). When you participate in ACM contests, problems with statement longer than 2 pages usually about stupid translation of this statement into code. Not this time. EIGHT pages of elaborate rules, and problem turned out to be min-cost-max-flow. My last hour of the contest was very tense: I had to translate input to convenient form, not forget any corner cases, and also write correct MCMF. I got AC on easy in 4:54, but didn't get AC on hard, though I thought that my solution will work for both.
Problemsetter: Michal ‘miˇsof’ Foriˇsek
Task preparation: Michal ‘miˇsof’ Foriˇsek
Quality assurance: true men need no stinkin’ quality assurance

2017 G (Gunfight). Remember not in a good way. After 2015I in order to solve the problem I looked in a generator and come up with easy solution without hard data structures, but author's solution worked for all inputs. That made me sad (also that I didn't get AC for unknown reasons).

Honorable mention goes to 2013C. Yet another beautiful problem about investigating code, but in 2013 I was stupid and couldn't appreciate it.

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

how to use python generator ... UPD:pycharm worked

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

I haven't tried past problems, but I think it was extremely hard for me.

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

Contest starts in 20 minutes!

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

For J2, does 8*8 work or something better?

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

    7x7 is optimal.

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

    Something better.

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

      Interesting, different possible configurations.

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

        There should be several hundreds of different 7x7 mazes that work. They can all be generated using brute force, the code will be available in the archive soon.

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

      Can we construct using some technique or just brainstorming ?

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

        Some backtracking is able to locate a solution more or less instantly.

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

        Yes. The optimum maze contains just a single path of length 8. Just try 8! permutations of all directions. In order to choose the length of the path edges, choose the first cell which is not reachable by any shortest path. I also tried to choose either the first or the second cell in each direction (2^8 times more cases) but by program didn't find any smaller solution.

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

How to solve G hard? I tried running git ls-tree -r --name-only origin/hard | ../calc. The code processed 700'000'000 file names, but that wasn't all.

Also how many files are there in G hard?

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

    Short answer: There are probably more files than the atoms in the universe.

    Long answer: The content of a git repository is DAG, so one needs to understand its structure and use DP.

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

      This explains why my Linux in a virtual machine died... At least I didn't need to reboot my main OS.

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

Current (not entirely final) version of the solutions booklet is here: https://ipsc.ksp.sk/2018/real/solutions/booklet.pdf

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

    BTW, I solved both R1 and R2 using browser console. There is a little known Chrome devtools feature "Network conditions" that allows to change user agent (found it with google search).

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

Spent all yesterday's evening trying to find better solutions for chess problem by hand, found a lot of 7-moves bishop solutions, and finally believed that 6 moves is impossible.

The most funny are 1) where the king is mated on e6 and 2) that starts with b3

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

Just concentrate on the screen for only 180 minutes, you can easily solve 2 problems.

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

Will there be IPSC 2019?