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?
Well, I made a short announcement a few weeks ago, but the more reminders people have, the better.
misof just wants contribution!
Ssh, you're going to bring kostka here...
Someone called me?
o shit
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.
how to use python generator ... UPD:pycharm worked
I haven't tried past problems, but I think it was extremely hard for me.
Contest starts in 20 minutes!
For J2, does 8*8 work or something better?
7x7 is optimal.
Something better.
Interesting, different possible configurations.
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.
Can we construct using some technique or just brainstorming ?
Some backtracking is able to locate a solution more or less instantly.
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.
How to solve G hard? I tried running
git ls-tree -r --name-only origin/hard | ../calc
. The code processed700'000'000
file names, but that wasn't all.Also how many files are there in G hard?
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.
This explains why my Linux in a virtual machine died... At least I didn't need to reboot my main OS.
Current (not entirely final) version of the solutions booklet is here: https://ipsc.ksp.sk/2018/real/solutions/booklet.pdf
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).
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
e4 e5 2. Ke2 Ke7 3. Ke3 Ke6 4. Qh5 Qh4 5. Qg5 Qg4 6. Bd3 Bd6 7. Bc4#
b3 b6 2. Bb2 Bb7 3. Bxg7 Bxg2 4. e4 e5 5. f4 f5 6. Be2 Be7 7. Bh5#
Just concentrate on the screen for only 180 minutes, you can easily solve 2 problems.
Will there be IPSC 2019?
Short answer: yes.
Long answer: yes, but we don't know exactly when yet; also, private messages > necrobumping.
Here necrobumping > private messages because community gets to know about answer as well :)
Hi, what about IPSC 2020?
Uh, the plans are that it should be. The plans were that IPSC 2019 should've also been, but that didn't work out.
Hey, what is the current status?
Any updates?
There was an attempt to organise it, but it fell through thanks to a lack of people/motivation. Shit happens.