Dec Course Selection 2020 Editorials

I’m sorry people

Testers’ scores

All testers had full score.

​

Thanks to Rui Yuan, Ashley, Jamie and Damian for helping to test :)

Key changes:

Damian scam tc on conversations

Ryan scam tc on naptime

Statistics

Statistics

Top 5 Scores (as of 2020)

Jiahng (RI Y3) 600, 1h58 mins

Terry (HCI Y5) 600, 2h53 mins

Choo Ray (RI Y5) 600, 3h37mins

Yunrui (RI Y5) 600, 3h54mins

Chur Zhe (HCI Y2) 600, 4h24mins

​

First AC

1 - Chur Zhe (0:02)

2- Yiyang (0:09)

3 - Yiyang (0:13)

4 - Yunrui (0:33)

5 - Jia Hng (1:50)

6 - Jia Hng (1:58)

Tax Collection

Written and prepared by Wallaby

​

Tags: Syntax, Greedy

Story

Wallaby really farmed so many points on inequality that he wants to increase inequality by increasing tax!

​

Statistics

AC Count - 57

Abridged Statement

Given an array of N integers, reorder the positions of some of the integers in order to maximise the prefix sum from 1...i for every 1 <= i <= N

​

​

Subtask 1: Ai = 1

Since Ai is the same, no matter how we order the towns on the list, the final answer will be the same.

answer = 1 + 2 + 3 +...+ N

= (N * (N+1))/2

Subtask 2: Order of all towns can be changed

A[1] is taken the most times!

Followed by A[2], A[3]... A[N]

Subtask 2: Order of all towns can be changed

Since we want to maximise total people taxed,

just greedily put the towns with the most people in the earlier positions!

Subtask 2: Order of all towns can be changed

Solution:

Push all A[i] into a vector

Sort the vector from greatest to lowest value

​

Iterate through each town while keeping a running sum to store the prefix sum.

​

Then, add the prefix sum to the answer each time.

Subtask 3: No further constraints

Instead of pushing all the towns into the vector, only push towns that can be swapped.

Then, just sort these towns from greatest to smallest value.

Perform the same running prefix sum to calculate the answer.

Entropy

Written and prepared by Orange

Source: Singapore Zoo Contest Backup D2B

​

Tags: Greedy, Syntax

Story

Motivation: Entropy(S) of a system is a measure of the disorder of matter and energy in the system. The more ways matter in the system can be arranged,and the more ways energy in a system can be dispersed, the more disordered the system is and thee larger its entropy.

At first, no increasing condition, solution was Nlog^2 with monge and slope trick. But someone disproved the monge convexity :((

Entropy

Abridged: Change K values in a non-decreasing array to minimise sum of differences between adjacent values

​

AC Count: 34

​

Observation

No point changing intermediate values!

4 -> 6 -> 9 (5)

4 -> 4 -> 9 (5)

4 -> 9 -> 9 (5)

Changing a prefix and a suffix!

Observation

We are “removing” a prefix or a suffix, or both

4, 5, 7, 9, 100

Is effectively

4,5,7,7,7

Since increasing, ask(i,j) = A[j]-A[i]

Solution

Brute force all start and end points.

Complexity: O(N)

​

Conversation (Easy Version)

Written by Snake, prepared by Orange

Source: Singapore Zoo :P

​

Tag: Data Structure

Story

Conversation

Fulfill a bunch of queries

Motivation: Rui Yuan sleeps while zoo chats, so he always wakes up and asks what happened

Number of ACs: 32

Stack?

Stack can add conversation, remove latest conversation and query latest conversation.

But a stack can’t delete a conversation easily

Smack

Use a map or set to store deleted conversations. At any point in time, we check if the top element of the stack is inside the set.

For each delete query, we simply add into the set.

For each delete latest query, we delete the latest element from the stack, and keep deleting the top element if it is inside the set.

Complexity: O(N) or O(Nlg(N)), depending on unordered_set or set

Hard version

Hard version appearing at dec course!!!

ATB!!

Naptime

Written by Stuart, Prepared by Yi Kai

​

Tags: Greedy, Graph Theory

​

Inspiration

Stuart likes sleeping and misses naptime in kindergarten, so he dreamt up this problem :)

Abridged Problem Statement

N children will sleep in a R-by-C room with M ceiling fans.

You have the locations of the fans.

Each child wants to sleep a Manhattan distance between L_i and U_i inclusive from the nearest fan.

Find the maximum number of children that can be satisfied among all assignments of sleeping locations.

Statistics

ACs: 14

Main Idea

Break problem into 2 parts:

1. Find how many tiles are distance x away from the nearest fan for all x�
2. Assign tiles to the children

Part 1

How to get distance for each tile?

Multi-source Breadth-First Search (BFS)!

Same as normal BFS but all sources (fans) are in the queue before you start.

​

Time complexity: O(RC)

Part 2

How to assign tiles? - Greedy!

1. Process tiles in increasing distance
2. Iterate through all children who have not been picked
3. Among all children who will be satisfied with this tile, pick any with the smallest U_i
4. If no child will be satisfied, skip this tile

​

Why Greedy Works

“Among all children who will be satisfied with this tile, pick any with the smallest U_i”

If we pick a child with larger U_i, we risk not having more suitable tiles for the child with smaller U_i

It is not worse to pick the child with smaller U_i

​

​

TLE ??????? >:(((((

Time complexity: O(RCN)

​

AC !!!!!! :D :D :D

Sort children by increasing L_i (U_i does not matter)

Maintain a priority queue of children who will be satisfied with the current tile, smallest U_i first (L_i does not matter)

Pick the child at the front if possible

Time complexity: O(N log N + RC)

​

Interestring

Written and prepared by Stuart

​

Tags: Dynamic Programming, Combinatorics

​

Story

TFW you read a problem in AtCoder wrong so you set a problem instead

ABC167E - Colorful Blocks

Not Very Abridged Statement

The alphabet is cyclic and has size M.

A string T is bad if, for all ordered pairs of adjacent letters in T, the second letter is at most H letters after the first letter.

A string U is interesting if the length of the longest bad substring of U is at most K.

Find the number of interesting strings modulo 10⁹+7.

Statistics

ACs: 8

Important Observation

For each first letter p, there are always (H + 1) choices of second letters c such that the pair (p, c) is bad.

This is because the alphabet is cyclic.

Main Idea

An interesting string is constructed by concatenating one or more bad strings, each of length up to K.

Three cases to consider when adding a single letter c:

1. First letter: M choices of c
2. Extend a bad string: (H + 1) choices of c� dist(p → c) ≤ H
3. Begin a new bad string (excluding first): (M - H - 1) choices of c� dist(p → c) > H

How Many Bad Strings?

For a bad string of length x:

First bad string:

Free choice (first letter)

Extend bad string

How Many Bad Strings?

For a bad string of length x:

Subsequent bad strings (regardless of previous letter):

Begin new bad string and avoid interfering with previous bad string

Extend bad string

DP :>

Let S(i) represent the number of interesting strings of length i.

append a new bad substring of length x

the entire string of length i is bad

DP TLE?

Let S(i) represent the number of interesting strings of length i.

​

​

​

​

​

Time complexity: O(NK) :(((

Simplify!

If 1 ≤ i ≤ K:

​

​

This is because a string of length ≤ K cannot have a bad substring of length > K.

​

​

​

Simplify!

If i = K + 1:

​

​

​

All strings of length K + 1

Bad strings of length K + 1

Speedup!

If i > K + 1:

Expand the expression for S(i) to get this.

​

​

Significant overlap? :thinking:

Speedup!

If i > K + 1:

​

Multiply by (H + 1)

Remove

Add

Speedup!

​

​

Big brain math speedup :DDD

​

​

​

Speedup!

​

​

​

Precompute constant in O(K) or O(log K) if you’re extra

Transition time complexity: O(1)

Total time complexity: O(N + K)

Puttingstrings

Written and prepared by Ryan See

​

Tags: Constructive algorithms, Graphs

​

Abridge statement:

You can put a 0 and 1 at every position.

​

Find a valid placing satisfying all the conditions or output -1

Statistics

ACs: 7

Subtask 1 and 2

Subtask 1 is looping through all possible arrays (can use bitmasks) and checking against the conditions and output one valid array. Since N is small, you will not TLE. If none exist, output -1.

​

Subtask 2 requires “discretisation” or also known as “coordinate compression”. Notice that only an array position inside at least 1 condition matters. (the rest can all be 0.) Then loop through all possible combinations of these positions that “matters”.

Since the constraints of this subtask limits it such that at most 17 positions matter, you will not get TLE with this solution.

Subtask 3

Since the conditions do that intersect, if x is 1, you can just set any one of the positions between l to r to 1, and you will get a valid placing.

Subtask 4:

L_i = 1

Sort ranges in ascending order of r.

Settle them one by one.

Note: Output -1 if there are 2 r that are identical but their x is different.

​

​

Subtask 5

1 <= N, Q <= 2000

Observation:

Given some ranges that are:

(1, 3, 1)

(1, 5, 1)

(1, 7, 0)

Notice that you can split them into:

(1, 3, 1)

(4, 5, 0)

(4, 7, 1)

​

Subtask 5:

So basically do that for every start point in ascending order remember to change the x_i as per necessary.

After this every box would be like “mapped” to a range. (Becoz this process ensures only one range with start point = cur box)

Assign values in descending order (as whether or not you want to set your cur box to 1 or 0 may depend on future boxes.)

Output -1 if not possible.

​

Full Solution:

Prerequisites:

(A + B) % MOD = ((A % MOD) + (B % MOD)) % MOD

(A - B) % MOD = ((A % MOD) + MOD - (B % MOD)) % MOD

Full Solution:

Consider the prefix sum modulo 2. (or aka the xor sum(but not needed tbh))

psum[i] = (psum[i-1] + A[i]) % 2; (where A[i] is the number at that position)

Notice that if a condition l, r, x exists it means that:

(psum[r] + 2 - psum[l-1]) % 2 = x

Which implies that if x = 1, psum[r] != psum[l-1]

And if x = 0, psum[r] == psum[l-1]

Full Solution:

Since there are only two possible values for psum[i] (0 or 1, due to the % 2),

We can do graph modelling!

Connect node l-1 with node r, with the cost of x.

If x = 0, means they must be equal.

If x=1, means they must be different.

Output -1 should there be a contradiction. (as per statement)

Full Solution:

Now dfs or bfs to obtain the prefix sum.

After acquiring the prefix sum we can now find the array of values.

Basically just output (psum[i] != psum[i-1]) for all i (1<=i<=n)

Whats next?

16/23 Jan NOI Selection

Select top 5 for each category will be selected to represent ri/hci at noi.

We will release set of old problems by the setters so that you can prepare, as well as previous years’ contests

Please note that previous years contests have been set by different people (kappa, 4russians) and do not reflect the setting habits of 2021 selection (zoo)

NOI Predictions

Dec Course results announced tonight or tommorrow

​

If this had been NOI selection, these would be the teams:

NOI Predictions

RI: Jia Hng (600), [Evan (600)], Yiyang (530), Ryan Goh (448), Yiming (430)

RJ: Choo Ray (600), Yunrui (600), Yuxuan (600), Keyi (497), Mun Hin (471)

HCI: Chur Zhe (600),

HCJC: [Stuart, Yi Kai] Terry (600), Qirui (517), Zhongqi (405)