When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Xellos's blog

By Xellos, history, 7 years ago, In English

As you may have noticed, this year's edition of IPSC will take place a month later than usual — 8.7. (time). The registration has been open for a while now. Don't forget to participate!

You can find details of the competition in my previous blog or on its website.

Contest is over.

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

»
7 years ago, # |
Rev. 2   Vote: I like it +53 Vote: I do not like it

Um_nik and kraskevich are looking for a teammate. The best variant if you are from Moscow and know at least one of us in person. But we are open for other possibilities including remote participation (it is easier when there is no restriction on number of computers). But still it will be better if you at least can speak Russian :)

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +143 Vote: I do not like it
    1. Join Um_nik's team.
    2. Participate in IPSC.
    3. Come up with an O(N * InverseAckermann(N)) solution.
    4. Um_nik has an O(N) solution.
    5. He says you have a weak mind.
    6. Kill yourself.
    7. ???
    8. Profit!
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +66 Vote: I do not like it

      Sounds fun! More reasons to join us!

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

    Actually there is a restriction on the number of computers. The IPSC rules say "Your team should use at most one computer per team member. Do not use larger clusters or clouds."

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

      Wow, thanks for reminding us that rule exists, haven't noticed before.

      I believe the rule is coined to counter some large scale distributed brute force solutions. But does one portable laptop + one cloud server count as "one computer"? This is arguably more affordable than building up a beefy desktop PC. I do understand that all tasks are designed to be solvable in a way that system performance does not matter much, but having additional cores (and memory) sometimes really helps.

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

        Yeah, the intent of the rule is to discourage large-scale distributed solutions.

        Whatever you feel comfortable calling "one computer" should be fine. As long as the total number of threads/processes you are running at any single time is <= a small constant, we are OK with that.

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

      It doesn't mean "Only one computer can use per one team", right?

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

        Quoting the rules, "Your team should use at most one computer per team member. Do not use larger clusters or clouds."

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by Xellos (previous revision, new revision, compare).

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

Auto comment: topic has been updated by Xellos (previous revision, new revision, compare).

»
7 years ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

What is the answer to E2? Our 30-minute code finished running 3 minutes after the contest ended and we want to feel bad if it would've been AC. Thanks! UPD: Got a PM with the answer, indeed feeling bad...

Once again, huge thanks to the organizers for another fun IPSC!

»
7 years ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

The contest is over. It was very interesting!

I managed to solve problem H-Hard (H2) before 12 minutes ending, but I think there is many solutions to H.
How did you solve problem H-hard?

I solved in this way:

Spoiler

In addition, thank you for IPSC!!! Thank you!

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

    I solved it by solving the sorted output first, and then introducing some extra commands that would be skipped in sorted version, and just rearranged all the commands such that it does the required things from both ends. Here is my version:

    Solution
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    I solved it by only using exactly one input and one print statement.

    solution
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    My solution

    BTW, really awesome problems, guys. Thanks to all organizers for so amazing contest.

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

    I have just 7 lines solution

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

      It's very simple and beautiful!!!
      In addition, thank you for everyone who replied my comment. Thank you!

      By the way, how long do you think you can write short program? (Number of lines)

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

After an hour of debugging my image tool I realized that I have a bug in a function which checked graph equivalence. ****.

Nice set, though I would say it is more "standard" compared with previous IPSC-s. First time participated as a single person team, and it feels much more pressurized when you don't have any support from the side.

What was the intended solution for K (random binary strings)? I calculated the conditional probability of digit i appearing after each block B of length 20 and replaced question marks according to which probability was higher, though it does not exploit that the generators are LCG-s (except for the fact they lack randomness, of course).

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

    There is a huge period, once you find it change all a[i]=2-s with a[i-period] or a[i+period]

»
7 years ago, # |
  Vote: I like it +98 Vote: I do not like it

Best 73 second of my life! After this we got 10th place.

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

    For you, [04:58:47, 5:00:00] is better than [04:57:40, 04:58:47]?

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

      Well, after getting AC in G2 I actually didn't expected more to come. I wasn't able to track zigui's progress as I was concentrating so much for solving G

»
7 years ago, # |
  Vote: I like it +96 Vote: I do not like it

Sorry guys, but I didn't like this year contest. It was well prepared and the problems were interesting, it could be one of the best ACM contest this year. Almost all the problems you can give on standard contest (maybe with lower limitations). And it wasn't so fun as it was past three years.

I even tried to solve G2 'IPSC-way': I read the generator, understood the structure of the graph and wrote very simple solution without any data structures. It works fast enough (about 1 minute) but somehow got WA (we still don't know what was the problem). And then I read the editorial and it says that the intended solution works for all graphs. I was absolutely sure that I was supposed to 'hack' the generator and it is sad that I was wrong.

I know that it is only my opinion that IPSC is all about thinking out of the box so do not take it to heart.

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

    Ha! Expecting to think outside the box can mean standard algorithmic problems are outside the box in a sense. You just weren't sufficiently thinking outside the box!

    Don't worry, we'll have you write a self-aware AI next year.

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

      Don't worry, we'll have you write a self-aware AI next year.

      Any updates? :)

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

        I don't know, ask your self-aware AI! ("Alexa, do you work for the CIA?")

        I guess the contest will be late this year. misof is the person to ask.

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

    I often advertise IPSC to other people as the contest with a wide range of tasks (algorithmic, system, thinking outside of the box etc.) and show a couple of examples from previous years. This year there was definitely a heavy bias towards algorithmic tasks. I still found it fun, but there would be only two tasks I'd remember from this year and one of them was at the practice round (Holy cow, Vim! & St. Ives). I can remember a lot of tasks from the previous 4 IPSCs even today.

    I sincerely hope that this year was an outlier and IPSC will not lose its identity, which definitely makes me look forward towards this competition every year.