### geniucos's blog

By geniucos, history, 5 weeks ago, ,

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
•

 » 5 weeks ago, # |   0 Where can we find the solutions for the tasks of previous editions?
•  » » 5 weeks ago, # ^ | ← 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.
 » 4 weeks ago, # | ← Rev. 2 →   +4 geniucos Is it possible to register now ?
•  » » 4 weeks ago, # ^ |   +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).
•  » » » 4 weeks ago, # ^ |   0 I am about official participation , my country wants to register the second team . Is it possible to do now ?
•  » » » » 4 weeks ago, # ^ |   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
 » 4 weeks ago, # | ← Rev. 2 →   -28 scuze
 » 4 weeks ago, # |   +10 Do we have unlimited number of submissions available?
•  » » 4 weeks ago, # ^ |   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 base on its TL)
 » 4 weeks ago, # |   +10 geniucos The server keeps crashing and I can't submit, will the contest be extended?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   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 works for tomorrow. Sorry for the inconvenience, I hope you can still partially enjoy the round.
•  » » » 4 weeks ago, # ^ |   0 Yeah, I finished the round and I hope the conditions will be fine tomorrow!
 » 4 weeks ago, # |   +40 According to the schedule in the site we will have results by the middle of the contest. Is it a bug? :)
•  » » 4 weeks ago, # ^ |   +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
 » 4 weeks ago, # |   +56 Am I the only one who can't get the site to load?
•  » » 4 weeks ago, # ^ |   +41 me too
•  » » 4 weeks ago, # ^ |   +24 Same here
•  » » 4 weeks ago, # ^ |   +9 Same here.
•  » » 4 weeks ago, # ^ |   +11 I guess everyone has the same problem :(
 » 4 weeks ago, # |   +26 I can't join the contest, it says 502 Server error
 » 4 weeks ago, # |   +8 Can you at least upload the statements of the contest not to lose time?
•  » » 4 weeks ago, # ^ |   +2 They will probably extend the contest.
•  » » 4 weeks ago, # ^ |   +3 It worked for a second. Error is back again :(
 » 4 weeks ago, # |   +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?
•  » » 4 weeks ago, # ^ |   +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 :)
 » 4 weeks ago, # |   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!
 » 4 weeks ago, # |   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?
 » 4 weeks ago, # |   0 Hope that 157.75 will be bronze
 » 4 weeks ago, # |   0 Will submissions that weren't judged before the end be judged and considered in the results?
•  » » 4 weeks ago, # ^ |   0 Yes, they will (your last submission was a 0, the one before it a 13, and all the 3 before that also 0s)
•  » » » 4 weeks ago, # ^ |   0 clearly desperate...anyway, when is the expected time for the results?
 » 4 weeks ago, # | ← Rev. 3 →   0 Got 192.5, let's share the scores.Hope for silver XDupd: standings
•  » » 4 weeks ago, # ^ |   +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.
•  » » 4 weeks ago, # ^ |   -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
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 My predictionGold : 273 and aboveSilver : 200 to 204.59Bronze : 140.5 to 200
•  » » » 4 weeks ago, # ^ |   +5 Gold will more likely be above somewhere between 290 and 300.
 » 4 weeks ago, # |   +13 If I had to hate only two things in the world that would be interactive and constructive problems.
•  » » 4 weeks ago, # ^ |   +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.
•  » » » 4 weeks ago, # ^ |   +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.
•  » » 4 weeks ago, # ^ |   0 Why you don't like constructive problems?
 » 4 weeks ago, # |   +26 So it's official. I'm the first silver medalist and my teammate is the first bronze medalist .. ripPS: the first non-medalist in IOI16 is from Egypt, so it's some sort of legacy.
 » 3 weeks ago, # | ← Rev. 2 →   0 The contest is running.
•  » » 3 weeks ago, # ^ |   +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
 » 3 weeks ago, # |   0 How to solve B,C,D from international round?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +10 B
•  » » » 3 weeks ago, # ^ |   0 I don't understand what you have written, can you explain a bit?
•  » » » » 3 weeks ago, # ^ |   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
•  » » 3 weeks ago, # ^ |   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.
•  » » » 3 weeks ago, # ^ |   +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.
•  » » » » 2 weeks ago, # ^ |   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.
•  » » 3 weeks ago, # ^ |   +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.
•  » » » 2 weeks ago, # ^ |   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)
 » 2 weeks ago, # |   +14 When can we upsolve / obtain the test data?
•  » » 2 weeks ago, # ^ |   +10 They should be uploaded on the site pretty soon. We also hope to send them to oj.uz in the near future
•  » » » 2 weeks ago, # ^ |   +10 thanks geniositycos