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**

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

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.

geniucos Is it possible to register now ?

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

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

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

scuze

Do we have unlimited number of submissions available?

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)

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

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.

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

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

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

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

me too

Same here

Same here.

I guess everyone has the same problem :(

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

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

They will probably extend the contest.

It worked for a second. Error is back again :(

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?

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

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

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

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

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!

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?

Hope that 157.75 will be bronze

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

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

clearly desperate...

anyway, when is the expected time for the results?

Got 192.5, let's share the scores.

Hope for silver XD

upd:standingsI 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.

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

My prediction

Gold : 273 and above

Silver : 200 to 204.59

Bronze : 140.5 to 200

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

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

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.

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.

Why you don't like constructive problems?

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.

The contest is running.

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

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

B

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

Hint : You want to construct

F_{2n}on the diagonals, whereF_{n}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

C Cat: (without proof)

iwithp[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 alln- 1.p[n- 1 -i] =n- 1 -p[i].iwithp[i] ≠iandp[n] ≠n- 1 -i, do a double-swap withiandp[i]. (Similar to what you would to to sort a permutation with the minimal number of single swaps.)i, eitherp[i] =iorp[i] =n- 1 -i.p[i] =n- 1 -iandp[j] =n- 1 -jandi≠j,i≠n- 1 -j, then we can do a double-swap withiandjfollowed by a double swap withiandn- 1 -jto getp[i] =iandp[j] =j.i,n- 1 -i) withp[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).

n×ntableCthat keeps track ifp[i] can bejfor all pairs (i,j).nones in our table, then we know the answer.qand get 0 as a response, then we can setC[i][q[i]]) to zero for alli. We will ignore all non-zero responses.p[i] =A, then we cross off (j,A) for allj≠i. To make this happen more often, we do the following: If there is someiwith at most 6 values ofi, then we try to do a query to narrow down the possible values ofp[i] and only weight those queries with the probability to get zero as a response.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 thei-th andj-th element of the derangement. The key observation is that there are at mostnpairs such thatf(i,j) > 0.Now, we are almost done. Consider a round-robin tournament on the

nelements. In thei-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 off(i,j) over some disjoint pairs. AfterO(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) wheref(i,j) > 0 by simply searching within each query (amortized queries), and after we get this information we can reconstruct the permutation easily.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.

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?

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!

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

The grid

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

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.

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)

When can we upsolve / obtain the test data?

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

thanks geniositycos

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

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