CCC '14 S3 - The Geneva Confection - DMOJ: Modern Online Judge

CCC '14 S3 - The Geneva Confection

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 3.0s

Memory limit: 256M

Problem type

Canadian Computing Competition: 2014 Stage 1, Senior #3

In order to ensure peace and prosperity for future generations, the United Nations is creating the world's largest candy. The ingredients must be taken in railway cars from the top of a mountain and poured into Lake Geneva. The railway system goes steeply from the mountaintop down to the lake, with a T-shaped branch in the middle as shown below.

$\text{[math]}$

Right now, each of the $N$ $N$ ingredients is in its own railway car. Each railway car is assigned a positive integer from $1$ $1$ to $N$ $N$ . The ingredients must be poured into the lake in the order $1, 2, \dots, N$ $1, 2, \dots, N$ but the railway cars are lined up in some random order. The difficulty is that, because of the especially heavy gravity today, you can only move cars downhill to the lake, or sideways on the branch line. Is it still possible to pour the ingredients into the lake in the order $1, 2, \dots, N$ $1, 2, \dots, N$ ?

For example, if the cars were in the order $2, 3, 1, 4$ $2, 3, 1, 4$ , we can slide these into the lake in order as described below:

$\text{[math]}$

Slide car 4 out to the branch
Slide car 1 into the lake
Slide car 3 out to the branch
Slide car 2 into the lake
Slide car 3 from the branch into the lake
Slide car 4 from the branch into the lake

Input Specification

The first line will contain the number $T$ $T$ $(1 \le T \le 10)$ $(1 \leq T \leq 10)$ which is the number of different tests that will be run. Each test has the form of an integer $N$ $N$ $(1 \le N \le 100\,000)$ $(1 \leq N \leq 100 000)$ on the first line of the test, followed by a list of the $N$ $N$ cars listed from top to bottom. The cars will always use the numbers from $1$ $1$ to $N$ $N$ in some order.

Due to the official test data being weak, an additional test case worth 1 mark has been added that was constructed to break solutions that are incorrect but AC on the official test data. Data are provided by August_Chen08.

Output Specification

For each test, output one line which will contain either Y (for "yum") if the recipe can be completed, and N otherwise.

Sample Input

Copy

Output for Sample Input

Copy

Y
N

Comments

-1

maxcruickshanks commented 78 days ago

Since the original data were weak, an additional test case worth 1 point was added, and all submissions were rejudged. Data were provied by August_Chen08.

13

HisMonDon commented on March 16, 2024, 10:28 p.m. ← edited →

what the heck is "heavy gravity"💀

4

Hiccup172 commented on Nov. 5, 2024, 5:45 a.m.

gravity++

2

crispo513 commented on Feb. 12, 2024, 7:40 p.m.

I love this question sm

16

98765432123456789 commented on Dec. 8, 2023, 8:29 a.m.

i saw this and almost jumped off a cliff cause i thought it was graph theory but turns out it wasnt so im happy now