E869120's blog

By E869120, 4 weeks ago, In English

Hello everyone!

JOI Open Contest 2024 will be held from Sunday, June 16, 04:00 UTC to Monday, June 17, 04:00 UTC.

The duration of the contest is 5 hours, but you can start any time in the 24-hour window. Note that if you start competing after 23:00 UTC, the contest automatically ends at 04:00 UTC and you cannot compete 5 full hours. For example, if you start competing at 03:45 UTC, the contest will be shortened to 15 minutes.


The contest information is as follows. Details are available in contest page.

  • Number of Tasks: 3 Tasks
  • Max Score for Each task: 100pts
  • Style: IOI Style (There may be some partial scores)
  • Problem Statement: Japanese & English
  • There may be some unusual task (e.g. output-only task, communication task) like IOI

Note that from this year, you can submit with C++20.


The registration page will be announced 30 minutes before the contest starting time. Good luck and have fun!

UPD1: The contest will start in 24 hours.
UPD2: Now the contest is started, so good luck and have fun. Note that you can start any time in 24-hour window.
UPD3: The contest is ended. Thank you for your participation.

Tags joi, ioi
  • Vote: I like it
  • +172
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

Saturday is June 15th, right? The link says so, indicating the start day is actually Sunday.

»
4 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

HYPE!

»
4 weeks ago, # |
  Vote: I like it -41 Vote: I do not like it

i think will be hard contest because its 3 tasks on 5 hours

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Wait, didn't it say the contest was on Saturday?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for a great contest!

How to solve the third problem ?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    You can find the solutions to all the problems at the contest page

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +15 Vote: I do not like it

    It seems they have a deterministic solution. I, however, have a non-deterministic solution which I still find interesting and would like to share:

    Random
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    bound of 5000 queries kindly suggests some O(N log N) queries solutions. Let's think of one such

    First thought is binary search, but it's not clear how to apply it here, so we'll return to it later.

    Recall what is the smallest number of swapt to "sort" the permutation? It is equal to N - number of components in graph (i -> p[i]). We don't have to sort the permutation, but we can actually create a permutation of indices and sort it, so the problem stays same.

    Described above is called decomposing permutation in cycles, and it has the next property: if we swap two elements that belong to same component, number of components increases by 1; otherwise it decreases by 1. Respectively after any swap we can track whether those two elements belonged to same component (and respectively this "swap" should be kept) or not.

    O(n^2) queries solution would be: for each j from 2 to N, try to swap it with each 1<=i<j and see whether it improves the cost or not. If it does, swap it and proceed with next j.

    Obvious way to optimize it is binary search. Let's see how to apply it: if we could check with 1 query whether one of first X indices belongs to same component as index J, we'd be able to find the index we have to swap j with in log(n) queries.

    Take a look at swap process — it not only changes the number of components, but splits one component in two or merges two in one. So actually we can recreate described above: "merge" first X indices into one component and check whether swapping J with any increases number of components. If it does, the index we search for lies there. Merging them would simply be cyclically shifting them to left or right. After finding the required index, swap it with j in your code and proceed to j+1. Note that it works since at any step, all of first (j-1) indices belong to different components (thanks to that swap).

    Bonus: it actually solves problem in under 4000 queries =)

»
4 weeks ago, # |
  Vote: I like it +46 Vote: I do not like it

Its funny to see you guys are still "upset" regarding the venue choices :P. Story of P2, I mean

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This is my code for 2nd subtask in problem A:

Spoiler

I don't think it should have passed. I think a test case with no | operations and a bunch of () can make it tle. Can you hack it?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It fails on [2]^[2]^....[2] (repeated 250000 times)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

pretty sus how library appeared on POI 3 months ago with the exact same constraints...

»
10 days ago, # |
  Vote: I like it +5 Vote: I do not like it

oj.uz when will the tasks be uploaded to oj.uz?