geniucos's blog

Info(1) Cup 2019 (In memory of Mihai Patrascu)
By geniucos, history, 6 years ago, In English

Hi!

3rd edition of Info(1) Cup will take place this weekend. More information on the site. I'll make this post shorter than usual, if you want extra details, you can just check one of the posts from last years (here or here).

This year, we'll have official teams from 27 countries taking part to make this contest memorable. We dedicate this edition in the honor of Mihai Patrascu, one of the greatest Romanian Computer Scientists.

We hope that this edition will be even more fun and challenging than the previous ones. You can practice on past problems on oj.uz. This should give a good idea of the kind of level you could expect from the contest although we try harder and harder to make up more interesting and challenging tasks.

We invite you all to join the online mirror of either of the rounds (the national round, approximately div2 level, and/or the international round — CEOI/BOI/APIO level)

I invite you all to discuss ideas for the problems and give feedback after the ending of the online mirrors.

Good luck, should you choose to compete!

The online mirror is now over. Let's discuss the problems! Please, give us some feedback

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

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

Where can we find the solutions for the tasks of previous editions?

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

    For those from 2017, you can find them on the site (they're on the right as you get to the tasks section of the competition (to get to the right year, choose the year from the past editions section, at the right of the top menu). For 2018, only the solution to the hardest problem is posted:( . None of us has had time to upload them, there are some sketches though in the comments section of last year's post. If you find anything unclear, I can try to answer some questions about them. I hope we'll eventually post the solutions to last year's problems as well as to this year's ones.

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

geniucos Is it possible to register now ?

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

    For the online mirror? Not yet, it will be soon. I'll update the post with the link to the online mirror, but you can count on it starting just after the contest. As for official participation, your country has already registered, we're open to new countries generally, although we're already getting pretty close to the contest itself, so it'd be a bit difficult to sign up a new country for the official version in such short notice (yet doable).

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

      I am about official participation , my country wants to register the second team . Is it possible to do now ?

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

        Hi! Unfortunately, we make exceptions of letting several teams from a country compete only in case they are unable to make a relevant objective selection of 4 people (for example in Iran the number of students they have selected so far for potentially competing in IOI is 8). In your case, the IOI team was already selected as far as I know. We'd normally accept more teams, but for now (and I'm not sure it'll ever get any better) we only have one main server and it's pretty difficult to guarantee there's not going to be any judging queue, so we need to constraint the number of contestants as much as possible. Therefore, unless you have a pretty good argument for which we'd want a second team from Azerbaijan, I'm afraid we won't accept one. If you do, PM me, and we'll do our best to make it happen

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

scuze

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

Do we have unlimited number of submissions available?

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

    Nope, that's also unfortunately the reason for which we couldn't afford accepting several unjustified teams from a country. We only have one server and want the feedback system to go smoothly so we had to constraint it. The limits are usually around 20 submissions per problem and we've increased them in the beginning in the past when we made sure that it wouldn't negatively affect the judging queue. We're trying to maximize it without the expense of a not-working system. The maximum number of submissions appears on CMS on the submissions tab of a problem and may vary from a problem to another (mainly based on its TL)

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

geniucos The server keeps crashing and I can't submit, will the contest be extended?

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

    Sorry for the late reply (you definitely got answered back by now), but yes it will. Something's wrong for some reason. We'll make it work for tomorrow. Sorry for the inconvenience, I hope you can still partially enjoy the round.

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

      Yeah, I finished the round and I hope the conditions will be fine tomorrow!

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

According to the schedule in the site we will have results by the middle of the contest. Is it a bug? :)

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

    Surely, the contest was scheduled for 9 AM Romanian time initially and at some point they moved it to 1 PM Romanian time. So they must have forgotten to shift the results, too :D

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

Am I the only one who can't get the site to load?

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

I can't join the contest, it says 502 Server error

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

Can you at least upload the statements of the contest not to lose time?

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

I just hope it gets fixed within 45 minutes because my boi Magnus gonna stream some blitz against Svidler and I'll have to leave :D BTW why didn't csacademy host it?

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

I managed to download two of the tasks, Consul and CostinLand.

https://drive.google.com/open?id=1WtkpJFKKes83INc2p2jdF4ToK86bzMYT

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

    Ah so the server wouldn't load for 30 minutes but they still keep the tasks there so that the lucky somebody could download them and have some advantage. Thanks for sharing :)

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

The task statements loaded for me, I uploaded them to google drive:

https://drive.google.com/open?id=1idtXscAMW2BoVpibuPBq9PFeZTHUj98Z

If I'm not supposed to share these please tell me, and I'll remove them

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

It's been working properly since around past 30, so we've extended it by 30 mins. We're very sorry for the inconvenience, and hope that you'll be able to enjoy the contest for the rest of its duration. Good luck everybody!

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

geniucos On the site, there is specified that the ranking should have already been published about 40 minutes ago. Will it be eventually be published before end of the contest or it will be published after the end of the contest?

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

Hope that 157.75 will be bronze

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

Will submissions that weren't judged before the end be judged and considered in the results?

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

    Yes, they will (your last submission was a 0, the one before it a 13, and all the 3 before that also 0s)

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

      clearly desperate...

      anyway, when is the expected time for the results?

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

Got 192.5, let's share the scores.

Hope for silver XD

upd: standings

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

    I gave my soul for my 100-71.5-0-34 and then two of my teammates hit me with 100-100-100-33 and 100-100-100-87 :D Still haven't heard from the third one and I think I don't want to.

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

    Didn't even try the third problem and thought about the last one almost all the contest :D That strategy produces noob looking 162 xD

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

    My prediction
    Gold : 273 and above
    Silver : 200 to 204.59
    Bronze : 140.5 to 200

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

      Gold will more likely be above somewhere between 290 and 300.

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

If I had to hate only two things in the world that would be interactive and constructive problems.

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

    I love interactive problems. Most of the times they are out-of-the-box and they are really cool to think about, even sitting somewhere in the comfortable chair.

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

      Well it is true that there are some quite interesting interactive problems. But what I absolutely hate is when you have to spend hours to reduce the numbers of queries by a little. And I don't like that it is hard to test your solution and think of test cases. Thinking about interactive problems always ends up bring boring, but I see the possible appeal in them.

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

    Why you don't like constructive problems?

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

So it's official. I'm the first silver medalist and my teammate is the first bronze medalist .. rip

PS: the first non-medalist in IOI16 is from Egypt, so it's some sort of legacy.

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

The contest is running.

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

    Hi! The online mirror is still running so we'll post the solutions afterwards. Hopefully (although I'd say unlikely) we'll have them written nicely and published on our site. If not, then you'll find them in comments explained by either us, or some other participants

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

How to solve B,C,D from international round?

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

    B

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

      I don't understand what you have written, can you explain a bit?

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

        Hint : You want to construct F2n on the diagonals, where Fn denote the Fibonacci numbers. In the process you will produce all fibonacci numbers up to that elsewhere, and you want to write your target answer as the sum of fibonacci numbers, then use them as building blocks. In the cells I have marked with an arrow, you may choose between the two symbols depending on whether you want that Fibonacci number in your sum, for example r blocks the even-numbered Fibonacci numbers from appearing in your sum etc. There might be some technical details but they are quite easy to fix.

        My code

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

    C Cat: (without proof)

    • Make the permutation zero-based.
    • If there is some i with p[i] + p[n - 1 - i] ≠ n - 1, then the answer is  - 1. The multiset of values {p[i] + p[n - 1 - 1]} is invariant under the double-swap operation and at the end it should be all n - 1.
    • After this, we only need to worry about indices , the other values will be automatically correct as p[n - 1 - i] = n - 1 - p[i].
    • While there is some i with p[i] ≠ i and p[n] ≠ n - 1 - i, do a double-swap with i and p[i]. (Similar to what you would to to sort a permutation with the minimal number of single swaps.)
    • Now for every index i, either p[i] = i or p[i] = n - 1 - i.
    • If p[i] = n - 1 - i and p[j] = n - 1 - j and i ≠ j, i ≠ n - 1 - j, then we can do a double-swap with i and j followed by a double swap with i and n - 1 - j to get p[i] = i and p[j] = j.
    • If three is a single pair (i, n - 1 - i) with p[i] = n - 1 - i, then we print -1. Otherwise print all double-swaps made.

    D Mouse: (I don't know how you get 100, but you can get 90 with the following randomized idea).

    • We keep a n × n table C that keeps track if p[i] can be j for all pairs (i, j).
    • If at any point we have n ones in our table, then we know the answer.
    • If we query q and get 0 as a response, then we can set C[i][q[i]]) to zero for all i. We will ignore all non-zero responses.
    • Just asking random queries already scores some points, but we can do better if we weight queries based on our current information, try 50 - 300 queries and pick the one with the highest weight.
    • In my weight function, I included an approximate probability for the query to give me a zero and how many ones I can cross off if that happens (with a higher weight for ones in a row with few ones).
    • As a final optimization, if we determine that p[i] = A, then we cross off (j, A) for all j ≠ i. To make this happen more often, we do the following: If there is some i with at most 6 values of i, then we try to do a query to narrow down the possible values of p[i] and only weight those queries with the probability to get zero as a response.
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      D solution :

      Firstly, query a few random permutations to get a derangement.

      Denote f(i, j) as the answer to the query after we swap the i-th and j-th element of the derangement. The key observation is that there are at most n pairs such that f(i, j) > 0.

      Now, we are almost done. Consider a round-robin tournament on the n elements. In the i-th "round", we swap each pair of elements that are paired in the current round (if an element is unpaired we just leave it untouched), and query the permutation. This way, we get the sum of f(i, j) over some disjoint pairs. After O(n) queries each pair of elements appear in at least one of the queries. Now, we can just binary search to find each pair (i, j) where f(i, j) > 0 by simply searching within each query (amortized queries), and after we get this information we can reconstruct the permutation easily.

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

        This was the official solution as well. There were several ways of groupings but the main observation was that information is being lost if querying on only one swap, so why not try more at the same time? Then there are several nice ways of grouping the pairs (one of which you've mentioned). I'd be interested to hear more about the very diverse randomized solutions that scored a lot of points. Fortunately, the official solution was still better. You could get below 1500 queries with a high probability (we've noticed this practically as we didn't manage to cope with the model to get a formal proof for its certainty) by doing the next 2 tricks: when considering several pairs, disconsider those that contain a position that already appears in 2 of the already found pairs. And, the trick from IOI 2017 Prize: instead of doing sequential binary searches, simulate a segment tree and stop when the sum is 0. There is also a nice proven d&c approach that's much more randomized than this one and gets O(NlogN) queries, but about twice as big constant.

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

          I think I got the D&C solution.

          First, try to identify the position of a match. Send random permutations until you get a positive answer. Let's try to narrow down the position of the match to one of the halves. Let's do the following alternatively on the halves: random shuffle that half .. if the answer increases, there must be a match in this half in the new permutation, so you can narrow it down .. if the answer decreases, there must be a match in that half in the original permutation, so you can also narrow it down .. I don't think the answer will remain the same for long, especially if you try the halves alternatively. After you identify a match, remove that index from the permutation and solve the same problem for length $$$n-1$$$. I couldn't submit the solution. ojuz, will you add this year like the previous years please?

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

            I'm going to email them as soon as we retrieve all the relevant information (probably just upload it on the site) so that they don't have to code everything from scratch. I would've done that earlier but I was caught up with uni-related work. What you're saying sounds pretty similar to what we had. Hopefully you'll be able to submit it not long from now. Thanks for the interest in the contest and its problems!

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

    Another solution to B ( https://ideone.com/4EZfS7 ), which I think is easier:

    The grid

    XXd
XXd
rr.

    the number at the end is 6 times the number in the top-left.

    We can "stack" these "blocks" to easily create powers of 6

    XXd....
XXd....
rrXXd..
..XXd..
..rrXXd
....XXd
....rr.

    We can change the 'r's and the 'd's into 'X's to change the coefficients of the powers of 6. There's also a separate case for the last "block".

    This will have a maximum n of ceil(log_6(10^8))+1, which just happens to be 49.

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

      This was the official solution as well, so it doesn't just happen to be 49:)) We were suriprised by the number of different solutions. Still I find it quite interesting that choosing a base like 6 can be a good solution (better than 2 for example)

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

When can we upsolve / obtain the test data?

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

    They should be uploaded on the site pretty soon. We also hope to send them to oj.uz in the near future

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

      thanks geniositycos

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

      2 month pass, was test data eventually uploaded? I can't find in website. Thanks.

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

ojuz Can you please upload the problems? I want to submit them. The testdata is available now.

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

You can submit all problems here: https://oj.uz/problems/source/438

→ Reply