Invitation to UWCOI 2020 Online Replay Contest - Rated for All

announcement
1

1582529221
15825292212416Ă—1148 286 KB

Hello all,

We would like to invite you to an online replay contest for UWCOI 2020. UWCOI is an OI-style contest hosted by UWCSEA Dover which was attended by multiple schools in Singapore. It was also used to select the UWCSEA Dover team for the Singapore National Olympiad in Informatics.

Here are some additional details:

  • The contest will be held at 21:00 IST, Tuesday 25 February (tomorrow).
  • 7 OI-style tasks (all tasks have subtasks) in 3 hours.
  • The questions are of a high quality and the contest will be rated for both Division 1 and Division 2.
  • There are also prizes, which are detailed under the contest page.
  • The writers are astoria, kimbj0709 and socho.
  • The technical committee also includes smjleo.
  • The contest is hosted at this link.
  • There is no time penalty for non-Accepted verdicts, however, time will be used as a tiebreak.
  • To ask questions, email uwcoi2020@gmail.com

Thanks,

The UWCOI committee.

EDIT:

Thank you for participating! We hope that you enjoyed the contest.

Editorials:
A: Peak Finding
B: Button Pairs
C: Mercury Poisoning
D: Base Plans
E: Escape
F: Blocks
G: Optimal Memory Address

11 Likes
2

looking forward to more rated contests,really excited for this:slightly_smiling_face:

3

can we expect proper oi type questions(usaco,ioi) or will the questions be like cc lunchtime oi style

4

Wow so many rated short contests this February :yum:

Hope to atleast remain 5* this contest

2 Likes
5

You can expect proper OI-type questions, overall. The contest was prepared to select a team for an OI contest so we felt it was very important to write questions that are also in OI style.

1 Like
6

What is the intended soln of “Escape” the last subtask?
Judging by memory taken 3 solns got AC using O((n*2^k+e)*log(n*2^k)) (which was intended be the soln of second subtask) including first 2 ACs on this problem.
Since I got AC using it I didn’t tried it again.

1s time limit was too tight on “Optimal Memory Address”. I had to use fast IO to reduce constant factor and get AC on it.

7

What was the solution of Blocks??

1 Like
8

First subtask was to check all factors of n.
Second subtask was to utilise the fact that if X is the minimum size of repeating block, then any factor of X is also a repeating block. So you can check n/(prime powers divisible by n) to find it.
Third subtask was to binary search on this prime power.

2 Likes
9

What is the approach for Base Plans @aryanc403

10

Use the fact that each row and column has only one tower square. Just check all pair of rows and distance between minimum and maximum column to check if there exists a plan between that row and column.

1 Like
11

What is the approach for Mercury Poisoning @aryanc403 .General dfs approach worked for only one task

12

My idea was to process queries offline and use union find. I just copied my soln of E. New Year Castle with 2-3 lines changes. You can read its editorial.

1 Like
13

Anyone mind telling me what was wrong in my submission (the actual code starts from line 200) for Optimal Memory Address.

The idea was to building a weighted trie on the prime factorization of the numbers and finding the node that minimizes the sum of distances to all the marked special nodes.

Edit: I found a few errors, the main one was when traversing the node to minimize distance I was incrementing by the number of all elements in parent’s subtree rather than the total number of elements, it still TLEs in one testcase but I should be able to figure that out.

14

Anyone please share a detailed approach of how to solve the problem Base Plans.

15

please do share the explanation behind the approach in Base Plans

16

How this accounts for checking for each possible square submatrix for appropriate base plan.

17

Edited. You should check all pair of rows. I missed all pair of.
Why this works is left as an exercise for readers.

1 Like
18

For every column, store the position of the tower.

Then, start extending the area of the tower base, up and down for a tower in any column.

For example,

1 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1

tower[0] = 0
tower[1] = 2
tower[2] = 1
tower[3] = 3

Now, you take into consideration the the towers from each column, and extend it both above and below.

If the difference between the above and below tower is same as indexes ( square base), you have got a base.

Code : here

Try pen paper to get a better understanding.

3 Likes
19

Understood !!! Seems to be such an easy solution:sweat_smile::sweat_smile:Thanks @aryanc403
@nuttela

1 Like
20

I believe that your solution (as well as the solution of mrho) are actually unintended and run in quadratic on an edge case, which you barely passed through constant factor tricks. Note that the Java submission of uwi runs in 0.24 seconds.