We had the Kotlin Challenge: what is the final?
Monday morning? Great time to remember that good things have already happened to start the week with good news!
In the fall of 2013, we started the Kotlin Challenge , a programming competition for those who were ready to try Kotlin, a new programming language for the Java platform. Several hundred people signed up, in the fall passed absentee training tours and quarterfinals, in February 2014 - the semi-finals, and finally ...
On April 29, 2014, 23 finalists met in our office at the final. The final was full-time, everyone housed in the conference room and began to solve problems.
')
There were only five tasks, two hours were assigned to the solution. None of the participants managed to solve all the problems, but every task was solved by anyone, so the complexity of the tasks should be considered acceptable.
Among the participants of the final were both very famous people in the Olympiad programming and less eminent ones. Among the figures that can be well known to every reader of the hub “Sports Programming”, it is worth noting Gennady Korotkevich, Peter Mitrichev, Roman Elizarov, Mikhail Mirzayanov. Programmers with different experience passed to the final - both students and graduated developers. One of the finalists, for example, works on Facebook, the other two are known as organizers of programming contests in their regions.
Participants came from four different countries (Belarus, Germany, Russia, USA), less than half were from St. Petersburg. I was pleased with the result of the Moscow Institute of Physics and Technology: two students from this university came from Dolgoprudny. To those of the finalists who brought good weather to St. Petersburg on April 29 - special thanks!
After an intense struggle, the winners were determined: Gennady Korotkevich won the first place. Gennady had already become world champion at ACM ICPC in 2013, reached the TopCoder Open final in the same 2013, and in 2014 won the Facebook Hacker Cup.
The second place went to Peter Mitrichev, who twice won the TopCoder Open, once Google Code Jam, and in 2003 won the ACM ICPC gold medal. Yes, yes, this is the same Peter Mitrichev, about which back in 2008, legends were on Habré .
In third place is Boris Minaev, the winner of the Google Code Jam qualification in 2013.
Some participants rushed to the following events, but most managed to take a picture of themselves on the roof of the JetBrains:
After the official part, the finalists of the Kotlin Challenge met with Andrei Breslav, the inspirer and leader of the Kotlin project at JetBrains, asked questions about the language, plans for its development, offered their ideas.
Note that interest in the Kotlin language is growing in different areas: it is studied not only for sports programming, but for industrial development. For example, Kotlin was used in the development of Telegram messenger and a web service for creating Prezi presentations.
For the JetBrains Kotlin Challenge - an unusual project, and its most pleasant result - we brought together many talented people who were interested in solving problems, and the language we developed to increase the productivity of developers in the industry was excellent for sports programming.
Watch the video report from the final on our website , if you want to live it in 3.5 minutes with the finalists.
And - the promised analysis of one of the tasks of the final.
Idea: Anna Malova.
Realization: Anna Malova.
Parsing: Pavel Krotkov.
Time limit: 2 seconds
Memory limit: 256 megabytes
The task:
Ben Gunn found Flint's treasure in the cave. Since Flint was a very tricky pirate, he put him in one of the many chests, standing in a row and numbered in order from 1 to n. Each chest has one of three inscriptions: the treasures lie in the chest with a large number, the treasures lie in the chest with a smaller number, the treasures lie in this chest. Flint was also an illiterate pirate, so the inscriptions may not be true. Ben Gunn quickly found the treasures and decided to put them in one of the chests and correct some of the inscriptions so that they all correspond to reality.
Ben Gunn decided to choose such a chest so that the number of inscriptions to be corrected was minimal. Help Ben Gunn find the minimum number of corrections he will have to make.
The input contains several test cases. The first line contains the number T - the number of test cases (1 ≤ T ≤ 100). Next come test suites in the following format.
The first line of each set contains one positive integer n - the number of chests. The second line contains a description of the inscriptions on the chests. If the i-th number is -1 or 1, it means that the number i on the chest says that the treasure lies in the chest with a number smaller or larger than i, respectively. If the i-th number is 0, this means that it is written on the i-th chest that the treasure lies in it.
The total number of chests in one input data does not exceed 100,000.
Output Format:
For each test case in the order of appearance in the input data, print one number - the minimum number of inscriptions that Ben needs to correct.
Examples:
Let's go through the number of the chest, in which we put the treasure. In order to count the number of inscriptions that we will have to change, putting treasure in this chest, we need to know the number of numbers that are not equal to one to the left of this chest, and the number of numbers that are not equal to minus one, to the right of this chest. The desired value will be the sum of the two values ​​mentioned above, to which it is necessary to add one in case there is not a zero written on this chest.
Restrictions on the input data in the task do not give us the opportunity to calculate the required values ​​each time, because this may require about 1010 operations for one test. However, we note that for the first chest the first value is always zero, and the second we can calculate in advance for linear time. After that, during the sequential iteration of the chest number from left to right, we can increase the current first value by one if the unit being written is not one, and decrease the current second value by one if it is written with a minus one. This technique is very similar to the calculation of partial sums and helps us to solve this problem in linear time.
The source code for the solution described is shown below.
Program with sporting pleasure!
In the fall of 2013, we started the Kotlin Challenge , a programming competition for those who were ready to try Kotlin, a new programming language for the Java platform. Several hundred people signed up, in the fall passed absentee training tours and quarterfinals, in February 2014 - the semi-finals, and finally ...
On April 29, 2014, 23 finalists met in our office at the final. The final was full-time, everyone housed in the conference room and began to solve problems.
')
There were only five tasks, two hours were assigned to the solution. None of the participants managed to solve all the problems, but every task was solved by anyone, so the complexity of the tasks should be considered acceptable.
Among the participants of the final were both very famous people in the Olympiad programming and less eminent ones. Among the figures that can be well known to every reader of the hub “Sports Programming”, it is worth noting Gennady Korotkevich, Peter Mitrichev, Roman Elizarov, Mikhail Mirzayanov. Programmers with different experience passed to the final - both students and graduated developers. One of the finalists, for example, works on Facebook, the other two are known as organizers of programming contests in their regions.
Participants came from four different countries (Belarus, Germany, Russia, USA), less than half were from St. Petersburg. I was pleased with the result of the Moscow Institute of Physics and Technology: two students from this university came from Dolgoprudny. To those of the finalists who brought good weather to St. Petersburg on April 29 - special thanks!
After an intense struggle, the winners were determined: Gennady Korotkevich won the first place. Gennady had already become world champion at ACM ICPC in 2013, reached the TopCoder Open final in the same 2013, and in 2014 won the Facebook Hacker Cup.
The second place went to Peter Mitrichev, who twice won the TopCoder Open, once Google Code Jam, and in 2003 won the ACM ICPC gold medal. Yes, yes, this is the same Peter Mitrichev, about which back in 2008, legends were on Habré .
In third place is Boris Minaev, the winner of the Google Code Jam qualification in 2013.
Some participants rushed to the following events, but most managed to take a picture of themselves on the roof of the JetBrains:
After the official part, the finalists of the Kotlin Challenge met with Andrei Breslav, the inspirer and leader of the Kotlin project at JetBrains, asked questions about the language, plans for its development, offered their ideas.
Note that interest in the Kotlin language is growing in different areas: it is studied not only for sports programming, but for industrial development. For example, Kotlin was used in the development of Telegram messenger and a web service for creating Prezi presentations.
For the JetBrains Kotlin Challenge - an unusual project, and its most pleasant result - we brought together many talented people who were interested in solving problems, and the language we developed to increase the productivity of developers in the industry was excellent for sports programming.
Watch the video report from the final on our website , if you want to live it in 3.5 minutes with the finalists.
And - the promised analysis of one of the tasks of the final.
Parsing task A: Treasure
Idea: Anna Malova.
Realization: Anna Malova.
Parsing: Pavel Krotkov.
Time limit: 2 seconds
Memory limit: 256 megabytes
The task:
Ben Gunn found Flint's treasure in the cave. Since Flint was a very tricky pirate, he put him in one of the many chests, standing in a row and numbered in order from 1 to n. Each chest has one of three inscriptions: the treasures lie in the chest with a large number, the treasures lie in the chest with a smaller number, the treasures lie in this chest. Flint was also an illiterate pirate, so the inscriptions may not be true. Ben Gunn quickly found the treasures and decided to put them in one of the chests and correct some of the inscriptions so that they all correspond to reality.
Ben Gunn decided to choose such a chest so that the number of inscriptions to be corrected was minimal. Help Ben Gunn find the minimum number of corrections he will have to make.
Input format:
The input contains several test cases. The first line contains the number T - the number of test cases (1 ≤ T ≤ 100). Next come test suites in the following format.
The first line of each set contains one positive integer n - the number of chests. The second line contains a description of the inscriptions on the chests. If the i-th number is -1 or 1, it means that the number i on the chest says that the treasure lies in the chest with a number smaller or larger than i, respectively. If the i-th number is 0, this means that it is written on the i-th chest that the treasure lies in it.
The total number of chests in one input data does not exceed 100,000.
Output Format:
For each test case in the order of appearance in the input data, print one number - the minimum number of inscriptions that Ben needs to correct.
Examples:
| Input data | Output |
|---|---|
| 2 | four |
| five | 0 |
| -1 -1 0 1 1 | |
| five | |
| 1 1 0 -1 -1 |
Let's go through the number of the chest, in which we put the treasure. In order to count the number of inscriptions that we will have to change, putting treasure in this chest, we need to know the number of numbers that are not equal to one to the left of this chest, and the number of numbers that are not equal to minus one, to the right of this chest. The desired value will be the sum of the two values ​​mentioned above, to which it is necessary to add one in case there is not a zero written on this chest.
Restrictions on the input data in the task do not give us the opportunity to calculate the required values ​​each time, because this may require about 1010 operations for one test. However, we note that for the first chest the first value is always zero, and the second we can calculate in advance for linear time. After that, during the sequential iteration of the chest number from left to right, we can increase the current first value by one if the unit being written is not one, and decrease the current second value by one if it is written with a minus one. This technique is very similar to the calculation of partial sums and helps us to solve this problem in linear time.
The source code for the solution described is shown below.
import java.util.Scanner fun main(args: Array) { val input = Scanner(System.`in`) val T = input.nextInt() for (i in 1..T) { val n = input.nextInt() val a = IntArray(n + 1) var cntL = 0 var cntR = 0 for (j in 0..n - 1) { a[j] = input.nextInt() if (j > 0 && a[j] != -1) cntR++ } var ans = n + 1 for (j in 0..n - 1) { ans = Math.min(ans, cntL + cntR + (if (a[j] == 0) 0 else 1)) if (a[j] != 1) cntL++ if (j < n - 1 && a[j + 1] != -1) cntR-- } println(ans) } } Program with sporting pleasure!
Source: https://habr.com/ru/post/222693/
All Articles