Google Kickstart Round D 2020
problem B Alien Piano
#kickstartroundd #kickstartroundd2020 #rounddkickstart
Link to problem:
Problem
An alien has just landed on Earth, and really likes our music. Lucky for us. The alien would like to bring home its favorite human songs, but it only has a very strange instrument to do it with: a piano with just 4 keys of different pitches. The alien converts a song by writing it down as a series of keys on the alien piano. Obviously, this piano will not be able to convert our songs completely, as our songs tend to have many more than 4 pitches. The alien will settle for converting our songs with the following rules instead: The first note in our song can be converted to any key on the alien piano. For every note after, if its pitch is higher than the previous note, it should be converted into a higher-pitched key than the previous note’s conversion; if lower, it should be converted into a lower-pitched key than the previous note’s conversion; if exactly identical, it should be converted into the same key as the previous note’s conversion. Note: two notes with the same pitch do not need to be converted into the same key if they are not adjacent. What the alien wants to know is: how often will it have to break its rules when converting a particular song? To elaborate, let us describe one of our songs as having K notes. The first note we describe as “note 1”, the second note “note 2”, and the last note “note K.” So note 2 comes immediately after note 1. Now if note 2 is lower than note 1 in our version of the song, yet converted to an equally-pitched or lower-pitched key (relative to note 2’s conversion) in the alien’s version of the song, then we consider that a single rule break. For each test case, return the minimum amount of times the alien must necessarily break one of its rules in converting that song. Input The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of two lines. The first line consists of a single integer, K. The second line consists of K space-separated integers, A1, A2 … AK, where Ai refers to the pitch of the i-th note for this test case. Output For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum number of times that particular test case will require the alien to break its own rules during the conversion process. Limits Memory limit: 1GB. 1 ≤ T ≤ 100. 1 ≤ Ai ≤ 106. Test set 1 Time limit: 20 seconds. 1 ≤ K ≤ 10. Test set 2 Time limit: 40 seconds. 1 ≤ K ≤ 104. Sample Input Output 2 5 1 5 100 500 1 8 2 3 4 5 6 7 8 9 Case #1: 0 Case #2: 1
tags:
kickstart round d,kickstart round d 2020,google kickstart round d,kickstart round d solutions,kickstart round d 2020 solution,kickstart round d explanation,kickstart round d 2020 codeforces,kickstart round d 2020 solutions,google kickstart round d 2020 solutions,google kickstart 2020,google kickstart solutions,google kickstart preparation,google kickstart in hindi,google kickstart,coding shark,alien piano solution,kickstart round d alien piano
