May 26, 2014 at 08:58We held the Kotlin Challenge: what's in the finals?
Monday morning? It’s a 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 absentia passed training tours and quarter-finals, in February 2014 the semi-finals, and finally ...
April 29, 2014 23 finalists met in our office for the final. The final was in-person, everyone was accommodated in the conference room and set about solving problems.
There were only five tasks, two hours were allotted for the solution. None of the participants managed to solve all the problems, however, at least someone solved each problem, so the complexity of the tasks should be recognized as acceptable.
Among the participants of the final there were both very famous people in the Olympiad programming, and less eminent. Among the figures that may be familiar to each reader of the Sports Programming hub, it is worth noting Gennady Korotkevich, Pyotr Mitrichev, Roman Elizarov, Mikhail Mirzayanov. Programmers with different backgrounds, both students and already graduated developers, reached the finals. One of the finalists, for example, works on Facebook, the other two are known as organizers of programming competitions 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 MIPT: as many as two students from this university came from Dolgoprudny. Special thanks to those of the finalists who brought good weather to St. Petersburg on April 29!
After a tense struggle, winners were determined: the first place was won by Gennady Korotkevich. Gennady had already become the 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 won the TopCoder Open twice, once the Google Code Jam, and in 2003 won the ACM ICPC gold medal. Yes, yes, this is the same Pyotr Mitrichev, about whom there were legends on Habré back in 2008 .
In third place is Boris Minaev, winner of the Google Code Jam qualification in 2013.
Some participants were in a hurry for the following events, but most managed to take a photo for memory on the roof of the JetBrains:
After the solemn part, the Kotlin Challenge finalists met with Andrei Breslav, inspirer and project manager of Kotlin at JetBrains , asked questions about the language, about plans for its development, offered their ideas.
Note that interest in the Kotlin language is growing in different areas: it is studied not so much for sports programming as for industrial development. For example, Kotlin was used in the development of the Telegram messenger and a web service for creating Prezi presentations.
For the JetBrains, the Kotlin Challenge is an unusual project, and its most pleasant result is that 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 also perfect for sports programming.
Watch the video report from the finals on our website if you want to live it with the finalists in 3.5 minutes.
And - the promised analysis of one of the objectives of the finale.
Idea: Anna Malova.
Implementation: Anna Malova.
Analysis: Pavel Krotkov.
Time limit: 2 seconds
Memory limit: 256 megabytes
Task condition:
Ben Gunn found Flint's treasures in the cave. Since Flint was a very cunning pirate, he placed 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: treasures lie in a chest with a higher number, treasures lie in a chest with a lower number, treasures lie in this chest. Flint was also an illiterate pirate, so the inscriptions may not correspond to reality. 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 corresponded to reality.
Ben Gunn decided to choose a chest so that the number of inscriptions that need to be fixed was minimal. Help Ben Gann find the minimum number of corrections that he will have to make.
The input contains several test cases. The first line contains the number T - the number of test sets (1 ≤ T ≤ 100). Next are the test suites in the following format.
The first line of each set contains one natural number 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 on the chest number i it is written 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 on the i-th chest it is written that the treasure lies in it.
The total number of all chests in one input does not exceed 100,000.
Output format:
For each test set, in the order in which they appear in the input, output one number - the minimum number of labels that Ben needs to correct.
Examples:
Let's go through the number of the chest in which we put the treasure. In order to calculate the number of inscriptions that we will have to change by putting the treasure in this chest, we need to know the number of numbers not equal to one to the left of this chest, and the number of numbers 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 you need to add a unit if not zero is written on this chest.
The restrictions on the input data in the problem do not give us the opportunity to count the required values each time, because this may require about 1010 operations for one test. However, note that for the first chest, the first value is always zero, and we can calculate the second in advance for linear time. After that, during a sequential search of the chest number from left to right, we can increase the current first value by one if there is not one written on the crawled chest, and decrease the current second value by one if not minus one is written on it. This technique is very similar to the calculation of partial sums and helps us to correctly solve this problem in linear time.
The source code for the solution described below.
Program with sports fun!
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 absentia passed training tours and quarter-finals, in February 2014 the semi-finals, and finally ...
April 29, 2014 23 finalists met in our office for the final. The final was in-person, everyone was accommodated in the conference room and set about solving problems.
There were only five tasks, two hours were allotted for the solution. None of the participants managed to solve all the problems, however, at least someone solved each problem, so the complexity of the tasks should be recognized as acceptable.
Among the participants of the final there were both very famous people in the Olympiad programming, and less eminent. Among the figures that may be familiar to each reader of the Sports Programming hub, it is worth noting Gennady Korotkevich, Pyotr Mitrichev, Roman Elizarov, Mikhail Mirzayanov. Programmers with different backgrounds, both students and already graduated developers, reached the finals. One of the finalists, for example, works on Facebook, the other two are known as organizers of programming competitions 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 MIPT: as many as two students from this university came from Dolgoprudny. Special thanks to those of the finalists who brought good weather to St. Petersburg on April 29!
After a tense struggle, winners were determined: the first place was won by Gennady Korotkevich. Gennady had already become the 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 won the TopCoder Open twice, once the Google Code Jam, and in 2003 won the ACM ICPC gold medal. Yes, yes, this is the same Pyotr Mitrichev, about whom there were legends on Habré back in 2008 .
In third place is Boris Minaev, winner of the Google Code Jam qualification in 2013.
Some participants were in a hurry for the following events, but most managed to take a photo for memory on the roof of the JetBrains:
After the solemn part, the Kotlin Challenge finalists met with Andrei Breslav, inspirer and project manager of Kotlin at JetBrains , asked questions about the language, about plans for its development, offered their ideas.
Note that interest in the Kotlin language is growing in different areas: it is studied not so much for sports programming as for industrial development. For example, Kotlin was used in the development of the Telegram messenger and a web service for creating Prezi presentations.
For the JetBrains, the Kotlin Challenge is an unusual project, and its most pleasant result is that 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 also perfect for sports programming.
Watch the video report from the finals on our website if you want to live it with the finalists in 3.5 minutes.
And - the promised analysis of one of the objectives of the finale.
Case Study A: Treasure
Idea: Anna Malova.
Implementation: Anna Malova.
Analysis: Pavel Krotkov.
Time limit: 2 seconds
Memory limit: 256 megabytes
Task condition:
Ben Gunn found Flint's treasures in the cave. Since Flint was a very cunning pirate, he placed 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: treasures lie in a chest with a higher number, treasures lie in a chest with a lower number, treasures lie in this chest. Flint was also an illiterate pirate, so the inscriptions may not correspond to reality. 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 corresponded to reality.
Ben Gunn decided to choose a chest so that the number of inscriptions that need to be fixed was minimal. Help Ben Gann find the minimum number of corrections that he will have to make.
Input Format:
The input contains several test cases. The first line contains the number T - the number of test sets (1 ≤ T ≤ 100). Next are the test suites in the following format.
The first line of each set contains one natural number 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 on the chest number i it is written 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 on the i-th chest it is written that the treasure lies in it.
The total number of all chests in one input does not exceed 100,000.
Output format:
For each test set, in the order in which they appear in the input, output one number - the minimum number of labels that Ben needs to correct.
Examples:
| Input data | Output |
|---|---|
| 2 | 4 |
| 5 | 0 |
| -1 -1 0 1 1 | |
| 5 | |
| 1 1 0 -1 -1 |
Let's go through the number of the chest in which we put the treasure. In order to calculate the number of inscriptions that we will have to change by putting the treasure in this chest, we need to know the number of numbers not equal to one to the left of this chest, and the number of numbers 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 you need to add a unit if not zero is written on this chest.
The restrictions on the input data in the problem do not give us the opportunity to count the required values each time, because this may require about 1010 operations for one test. However, note that for the first chest, the first value is always zero, and we can calculate the second in advance for linear time. After that, during a sequential search of the chest number from left to right, we can increase the current first value by one if there is not one written on the crawled chest, and decrease the current second value by one if not minus one is written on it. This technique is very similar to the calculation of partial sums and helps us to correctly solve this problem in linear time.
The source code for the solution described 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 sports fun!