Italian Olympiad in Informatics (OII) 2022 — Online Contest

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

For the seventh time, the Italian national contest (valid for the selection of the Italian IOI team) will be mirrored into an online contest. The contest is primarily intended for high school contestants, but everyone is welcome to participate! There are both easy subtasks (div2A) and very hard ones (div1D+), so it can be enjoyable both for newcomers and for very high rated contestants.

The problem statements will be available in both English and Italian.
Tasks will be IOI-like (with graders and subtasks) and you will have 5 hours to solve them.
The only language allowed is C++.
The time window for the practice contest (featuring original problems) will start on 2022 September 13th, 00:01 CET and will end on 2022 September 17th, 23:59 CET.
The time window for the main contest will start on 2022 September 23th, 10:00 CET and will end on 2022 September 24th, 15:00 CET.

The contests' timing will be USACO-like: you can decide when to start your 5-hours time window (after the login), but the contest will end at the given time regardless of your time window.

If you want to participate, you must:

Visit the contest website: https://mirror.oii.olinfo.it
Click the link "register", fill out the form and then click on the register button and then "back to login"
You can now log in with the same username and password you used to sign up
If the login is successful you will be ready to participate, just wait for the contest to start! (And maybe save the page in your bookmarks, so that you can quickly get back to it when the contest begins)
When the contest starts, you will see a red button. Click it when you want to start your 5 hour time window!
Good luck and have fun!

Ranking: The ranking of the online contest will be available at https://mirror.oii.olinfo.it/ranking when the contest starts.

Upsolving: After the end of the contest, tasks will be uploaded in the Italian training website https://training.olinfo.it (localised also in English), section "task & quiz archive", where they will be available for online evaluation (after registering to the website).

Комментарии (36)

Показать архивные | Написать комментарий?

TheScrasse

2 года назад, # |

+45

The time window for the practice contest has started.

→ Ответить

lbm364dl

2 года назад, # ^ |

Page is down right?

Yes, there is a problem with hardware right now. The page should be back soon.

+19

Now the page is up.

giothun

Where I can find official results for Italian high schoolers?

Official ranking (it's the practice, so don't take results seriously).

Kaey

The official results will be uploaded to this website , where you can all the results of recent OIIs.

NaplesLover

+37

How to A???? I tried a treap of dfus of ffts but it just wont pass the last tc Someone told me to find the diameter so i just did float d = ((float)N-1f)/atan(1) but from there im stuck. Maybe i need to find the modular form of the elliptic curve of the graph but i dont know how to do it. asked for an hint and the staff replied: “sei meravigliosa come una ragazza gotica” idk what that means, mabye some italian ds

alls

lol

AlesL0

+48

as a wise man once said,

/*
if there were a little good in the world
and everyone considered each other as brothers
there would be less worries and less pain
and the world would be a lot better
*/

now I don't know where I'm going with this, but what I'm sure of is that franfill will win this year's OII

lorenzoferrari

+10

pre-oii doesn't lie: AlesL0 is going to win.

franfill

It actually says that lorenzoferrari is going to win.

Tutis

I will win

Alenygam will win.

Alenygam

+15

I didn't win but I got silver. I'm happy enough.

I won't disappoint next year ;-)

Nurss

← Rev. 2 →

How to solve statue and sets? TheScrasse

yh11

← Rev. 5 →

-8

Triplets

Its easy to see that all three statues should be placed at the leaves. Then all you need to do is find a non-leaf node with (upto) 3 farthest leaf nodes.

You can do the above using brute force if you dfs from all inner nodes. But the brute force solution will TLE. So you need to solve this using dp + dfs.

Use DFS1 to store the distance to the farthest leaf node.
Use DFS2 to get the farthest leaf node from the parent and then combine it with farthest leaf nodes from children to get 3 farthest leaf nodes. 2 * (sum of distances) is the contribution of this particular node to the answer. Just max all the contributions to get the final answer.

Sets

My solution for this problem was only partially correct. :(

Step 1: Find the maximum number of numbers that can be removed in one pass. This can be solved using dp.

Keep repeating Step 1, as long as you can remove some numbers. (You have > 2 values and number of numbers removed was > 0).

You first solution is not for statues, it is for triplets. Also, by my questions I meant to know full solutions

right

feecIe6418

+26

I have no idea whether my solution to sets is right, but it did get 100 points.

First $$$O(n^3)$$$ dp is trivial: let $$$f(l,r)$$$ be whether you can erase everything in range $$$[l,r]$$$.

Note that

only when the xor sum of $$$[l,r]$$$ is 0, $$$f(l,r)$$$ might be 1.
The transitions look like enumerate $$$k$$$ and then check if both $$$[l,k],[k+1,r]$$$ can be erased. When doing so, use an array to store all $$$k$$$ such that $$$f(l,k)=1$$$ and only try those $$$k$$$-s.
if now $$$f(l,r)=1$$$, break; immediately.

With the two optimizations, it passes $$$n=10^4$$$ in 0.3 seconds.