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

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

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

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

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

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

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

    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.

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

geniucos Is it possible to register now ?

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

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

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

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

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

        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

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

scuze

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

Do we have unlimited number of submissions available?

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

    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)

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

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

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

    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.

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

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

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

    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

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

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

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

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

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

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

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

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?

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

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

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

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

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

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

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

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

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!

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

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?

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

Hope that 157.75 will be bronze

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

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

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

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

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

Got 192.5, let's share the scores.

Hope for silver XD

upd: standings

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

    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.

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

    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

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

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

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

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

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

    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.

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

      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.

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

    Why you don't like constructive problems?

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

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.

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

The contest is running.

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

    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

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

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

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

    B

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

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

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

        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

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

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

      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.

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

        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.

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

          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?

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

            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!

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

    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.

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

      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)

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

When can we upsolve / obtain the test data?

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

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

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

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