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

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

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.

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

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

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 лет назад, # ^ |
      Проголосовать: нравится +143 Проголосовать: не нравится
    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 лет назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      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 лет назад, # ^ |
          Проголосовать: нравится +28 Проголосовать: не нравится

        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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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

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

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

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

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 лет назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

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

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

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

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

    I have just 7 lines solution

    Spoiler
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +30 Проголосовать: не нравится

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

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

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

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

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

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

      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 лет назад, # |
  Проголосовать: нравится +96 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

      Any updates? :)

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

        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 лет назад, # ^ |
      Проголосовать: нравится +33 Проголосовать: не нравится

    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.