misof's blog

IPSC 2018
By misof, history, 6 years ago, In English

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?

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

»
6 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

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

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.

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it -32 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it -51 Vote: I do not like it

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

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

Contest starts in 20 minutes!

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

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

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

    7x7 is optimal.

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

    Something better.

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

      Interesting, different possible configurations.

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

        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.

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

      Can we construct using some technique or just brainstorming ?

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

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

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

        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.

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

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?

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

    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.

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

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

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

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

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

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

    → Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it +38 Vote: I do not like it

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
→ Reply
»
6 years ago, # |
  Vote: I like it +56 Vote: I do not like it

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

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

Will there be IPSC 2019?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -22 Vote: I do not like it

    Short answer: yes.

    Long answer: yes, but we don't know exactly when yet; also, private messages > necrobumping.

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

      Here necrobumping > private messages because community gets to know about answer as well :)

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

      Hi, what about IPSC 2020?

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

        Uh, the plans are that it should be. The plans were that IPSC 2019 should've also been, but that didn't work out.

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

          Hey, what is the current status?

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

          Any updates?

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

            There was an attempt to organise it, but it fell through thanks to a lack of people/motivation. Shit happens.

            → Reply