CCC '14 S3 - The Geneva Confection

View as PDF
Submit solution
Points: 7 (partial)
Time limit: 3.0s
Memory limit: 64M
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.

Right now, each of the N ingredients is in its own railway car. Each railway car is assigned a positive integer from 1 to N. The ingredients must be poured into the lake in the order 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?

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

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

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

2
4
2
3
1
4
4
4
1
3
2

Output for Sample Input

Y
N

Comments


  • -3
    Blueblitz135  commented on Sept. 10, 2022, 6:40 p.m.

    Can someone take a look at why my code doesn't work? I get the first test case correct but not the other ones. Thank you.


  • -2
    noah3238  commented on Sept. 9, 2022, 5:54 p.m.

    Hi, can someone give me some suggestions to avoid TLE in python?


    • -2
      volcano  commented on Sept. 10, 2022, 4:34 p.m.

      Design a better algorithm, implement better strategies, use built-in functions...


  • -2
    Wueth  commented on May 10, 2022, 2:55 p.m.

    why is my code not working? Could anyone check? Im getting the 1st question right and got a couple of my own test cases correct but it's failing for 2, 3, 4, and a TLE for 5. Thanks


    • -1
      DSealey  commented on June 3, 2022, 3:24 p.m.

      You need to look at how you are changing starting_number. The below should return Y. (one test, four numbers) 1 4 4 3 1 2


  • -1
    lwale1  commented on May 5, 2022, 9:02 a.m.

    I’m getting WAs for the last four test cases. Can someone look at my code please?


  • 1
    justin_g_20  commented on Aug. 25, 2021, 8:33 a.m.

    Can someone please tell me why my code segmentation faults?


    • 2
      Badmode  commented on Aug. 25, 2021, 3:36 p.m.

      Your submission - https://dmoj.ca/src/3852849

      Line 27 - you are calling top() on an empty stack. Make sure to first check if the stack is empty.


      • 1
        justin_g_20  commented on Aug. 25, 2021, 9:18 p.m.

        Thanks, I didn’t realise.


  • 0
    Lindsay_x  commented on Nov. 7, 2019, 9:24 p.m.

    Can someone please check what is wrong my code and how can I fix it?


    • 0
      magicalsoup  commented on Nov. 7, 2019, 11:18 p.m. ← edited

      You should re-initialize your stack for each test-case, your code right now carries over the stack used for the previous test-case, which misses up your calculations.


  • 1
    Macster  commented on Aug. 26, 2018, 10:23 a.m.

    Can someone look over my code? I'm getting WA for all test cases except for the first one :/


    • 3
      mango8023  commented on Oct. 10, 2018, 5:19 a.m.

      I see your code, and find some mistakes. In fact, you cannot assume that the number which be put to the branch is the largest of the remaining numbers. You can try this data as an instance: 4 2 3 1 (one test case with four numbers from top to bottom). And you'll see that the number '4' will not be put to the branch, but put in the river immediately when it comes.


  • -2
    AlanL  commented on Jan. 5, 2018, 6:10 p.m.

    Kind of confused on what's wrong with my code... :(


    • 2
      max  commented on Jan. 5, 2018, 10:09 p.m.

      Your code looks like it would run just fine, except you need to make a slight change to line 10 (if you have changed your code around, it is the one where you loop "repeater" times)

      Good luck!


  • 1
    deepcpp  commented on Aug. 17, 2017, 1:47 p.m.

    This problem is exactly like this.