By Snezhok, 7 years ago, translation, In English

Hello everybody!

Congratulations to the platform Codeforces with an Anniversary 450th round!

We are glad to report that Codeforces Round #450 (Div.2) takes place on December 11 19:05 MSK. The round will be rated for Div.2 participants. Traditionally, we invite Div.1 participants to join out of competition. I hope stronger participants also will find interesting problems for themselves:)

The problems are created by me and Nikita slelaron Kostlivcev. We want to show our great appreciation to Nikolay KAN Kalinin for round coordination, mike_live and Arpa for testing the problems and of course Mike MikeMirzayanov Mirzayanov for great platforms Codeforces and Polygon.

You will have 5 problems to solve in 2 hours.

Scoring as usual: 500 — 1000 — 1500 — 2000 — 2500.

Good luck to all and enjoy the problems!

UPD: Contest is finished! I hope you enjoyed the round:)

UPD: Editorial. The problem E will be posted soon.

UPD: The problem E was posted.

Congratulations to the winners!!!

Div 1

  1. KrK

  2. zscc

  3. wwwwodddd

  4. uwi

  5. oversolver

  6. Shayan

  7. dreamoon_love_AA

  8. please_delete_account

  9. alexrcoleman

  10. guille

Div 2

  1. zeronumber

  2. Brightness

  3. UBICA

  4. Lyon_71

  5. mmkh

  6. I_Love_Adriana_Chechik

  7. Ant_Man

  8. yuvalsalant

  9. Natsume_Mio

  10. PuriceLoh420

Full text and comments »

  • Vote: I like it
  • +269
  • Vote: I do not like it

By MikeMirzayanov, history, 7 years ago, translation, In English

Hi, Codeforces!

This is not an ordinary post from me. This is not an announcement of new features or a championship, but I'm no less enthusiastic.

I am glad to inform you that from January 29 to February 16, 2018 I will be giving the course "Advanced Algorithms and Data Structures" in Harbour.Space University (Barcelona, Spain). The course will be in English. The students of this course will not only be students of Harbour.Space, but is open to all! Who wants to join?

This course isn't just for Harbour.Space students, it is also open to Codeforces participants, who will be offered a special price, 1000 EUR. The cost does not include travel or accommodation.

Register for the Course →

In my plans there is a detailed story about some algorithms and data structures, a lot of practical exercises and emphasis not only on the correctness, but also the beauty and structure of the code. My goal is to make useful and interesting classes for both those who want to understand the fundamental CS, and for those interested in programming competitions. And of course, we will have the opportunity to meet and talk. I'm happy to share stories about the history of Codeforces and development plans.

The course will consist of three weeks of training, 5 training days in each week. The program includes daily lectures and practical exercises. It will not be boring for sure!

Here is the expected course outline:

Week Day Topics
1 1 Heap data structure, heap properties and operations. HeapSort. Priority queue. Other heap applications. Mergeable heaps: binomial heap, pairing heap, randomised meldable heap.
1 2 Fenwick tree. Description and motivation. Implementation of Fenwick tree. Generalisation for higher dimensions. Skip list data structure. Implementation details. Indexable skiplist.
1 3 Segment trees. Top-down implementation. Bottom-up implementation. Segment trees applications. Persistent data structures. Persistent stack, persistent array. Persistent Fenwick and segment trees.
1 4 Cartesian trees, treap data structure. Merge and split operations. Treap implementation in detail. Treap applications.
1 5 Treaps with implicit keys. Ropes. Segment reverse operation. Examples of problems.
2 6 Introduction to strings. String searching (matching) problem. Pattern pre processings. Z-function, prefix-function. Their applications. Knuth–Morris–Pratt algorithm. Matching finite state machine.
2 7 Multiple pattern matching. Trie data structure. Aho-Corasick algorithm. Implementation details. Dynamic programming on a trie.
2 8 String hashing. Rabin-Karp algorithm. Fast substrings comparison with hashes. Suffix array. LCP array. Efficient construction algorithm. Applications.
2 9 Suffix tree. Ukkonen's algorithm. Suffix tree construction from LCP array. Suffix tree applications.
2 10 Suffix automaton. Size bounds. Linear Algorithm. Using suffix automata as an index for approximate string searches.
3 11 Introduction to automata theory. Formal languages. Context-free languages. Formal grammars. Context-free grammars. NFA, DFA, convert NFA to DFA. Build automaton by regular expression.
3 12 LL(1) parser. Arithmetic expressions parsing. Shunting-yard algorithm. Simplified Pascal language parsing and interpretation.
3 13 Algorithms for traversing a graph. DFS. Properties. DFS search tree. Edges classification. Linear bridge-finding algorithm. Linear articulation points finding algorithm. Strongly connected components. Tarjan's strongly connected components algorithm.
3 14 Tree problems. Bottom-up approach. LCA problem. LCA algorithms.
3 15 Bipartite graphs. König’s criterion. Problems: maximum matching, minimum edge cover, maximum independent vertex set, minimum vertex cover. Connection of the problems. Berge's lemma. Kuhn algorithm. Kuhn algorithm properties. Minimal vertex cover by maximum matching. Cover DAG by minimal number of paths.

Harbor.Space University is located in Barcelona (Spain). For users of Codeforces, Harbour.Space is known for active participation in the life of the community of sports programming (partnership with Codeforces in the framework of Educational Rounds). The main activity of the university is teaching (there are bachelor's and master's programs) in the following areas:

  • Maths as a Second Language
  • Computer Science
  • Data Science
  • Cyber Security
  • Interaction Design
  • Digital Marketing
  • High Tech Entrepreneurship
  • FinTech
  • BioTech
  • Aerospace Engineering
  • SuperCities UrbanTech

Register for my upcoming course here.

Mike Mirzayanov

Full text and comments »

  • Vote: I like it
  • +152
  • Vote: I do not like it

By NercNews, history, 7 years ago, In English

text

Let us introduce the new programming language in ICPC: Kotlin. It is modern and developing language created by our sponsor JetBrains. Kotlin is inspired by Java and as Java is named after the island. Currently, Kotlin programs are compiled into JVM bytecode, all Java written code can be used from Kotlin sources and Kotlin written code can be used from Java sources as well out of the box. Kotlin being developed now most of the standard libraries are Java library classes, making Kotlin a programing language that is already used in many projects being the main language of their development.

Comparing to Java language some Java disadvantages fixed and new features added. Some of them we will see in today's solution of ICPC World Finals 2016 problem C (101242C - Ceiling Function). Less boilerplate code and syntactic sugar added

  1. new operator omitted
  2. data classes implement hashCode, equals and toString methods depending on constructor parameters
  3. operator overloading
  4. with function, to implement a block of code, making captured value as this
  5. when operator providing better readability of conditional operator in some cases
  6. type inference (IDE supports hints on variable and function types, it's just you don't have to type it)
  7. functional programming style
import java.util.*

data class Tree(var left: Tree? = null, var right: Tree? = null) {
    var value = 0
}

operator fun Tree?.plus(x: Int): Tree? {
    if (this == null) return Tree().apply { value = x }
    if (x < value) {
        left += x
    } else {
        right += x
    }
    return this
}

fun main(args: Array<String>) = with(Scanner(System.`in`)) {
    val n = nextInt()
    val k = nextInt()
    val a = Array(n) { IntArray(k) { nextInt() } }
    println(a.map { it.fold(null, Tree?::plus) }.toSet().size)
}

You can try Kotlin at: https://try.kotlinlang.org

Full text and comments »

  • Vote: I like it
  • +107
  • Vote: I do not like it

By ODT, history, 7 years ago, In English

Hello, Codeforces!

We are glad to invite you to participate in Codeforces Round #449 (both Div. 1 and Div. 2) which will be held on December 2, 17:05 MSK.

There are seven problems, created by webmaster, ODT, dogther.

This round is about the happiest girl in the world — Chtholly Nota Seniorious~!

You will help Chtholly, Nephren, Ithea and Willem (characters in the great novel and anime "What Do You Do at the End of the World? Are You Busy? Will You Save Us?") to solve some problems.

(Image by gin_sei56(・.8・) on pixiv)

This round is our first round on Codeforces.

Thanks to zcyskyaa for helping us, Arpa, cyand1317 and Tommyr7 for testing the round, vintage_Vlad_Makeev and KAN for round coordination and MikeMirzayanov for Codeforces and Polygon platforms.

This round has 5 problems in each division and you have 2 hours to solve them.

The scoring will be announced shortly before the start of the contest.

The contest is rated for both Div. 1 and Div. 2 contestants.

It's recommended for both divisions to read through the Interactive Problems Guide before the round.

Wish everyone high rating and accepted submissions!

Upd: Scoring is 500-1000-1500-2000-2500

Upd2: Congratulations to the winners:

Div 1:

  1. MrDindows

  2. bmerry

  3. krismaz

  4. Shik

  5. ainta

Div 2:

  1. blatuitorulmlc

  2. lumibons

  3. Starlit

  4. Grevozin

  5. lyoz

The editorial will be posted soon.

Upd3: Editorial

Full text and comments »

  • Vote: I like it
  • +172
  • Vote: I do not like it

By NBAH, history, 7 years ago, translation, In English

Hi everyone!

Codeforces Round #448 (Div.2) takes place on 26th of November at 19:05 MSK. As usual, Div.1 participants can join out of competition.

This is my second round on Codeforces! I advise you to read all of the 5 problems. Hope everyone will find something interesting.

I'd like to thank vintage_Vlad_Makeev for coordination, igdor99 for helping me in developing problems. And, surely, thanks to Tommyr7, Arpa, 300iq for testing this round.

Of course, many thanks to MikeMirzayanov for great Codeforces and Polygon platforms.

Scoring: 500-1000-1750-2000-2250

High ratings to everybody!

UPD: Contest is finished. Editorial will be posted soon.

UPD: Editorial

Congratulations to the winners!!!

Div1

  1. uwi

  2. Benq

  3. irkstepanov

  4. dreamoon_love_AA

  5. JustasK

  6. eddy1021

  7. yancouto

  8. chemthan

  9. Nephren_Ruq_Insania

  10. KrK

Div2

  1. Nephren_Ruq_Insania

  2. Mahan_sh

  3. lsrothy

  4. ngfam

  5. georgerapeanu

  6. ZalBinHassan

  7. mtkaya

  8. Bodo

  9. szhouan

  10. fchirica

Full text and comments »

  • Vote: I like it
  • +405
  • Vote: I do not like it

By Huawei_Codecraft, 7 years ago, In English

If you are 14+ and want your ideas to be implemented in new technologies and products, which being used by 1/3 of global population, participate in our Marathon started recently https://it-edu.mipt.ru/en/huawei-codecraft-marathon

Task can be downloaded after registration, see links below: John has a digital camera. He usually takes two photos, first photo is bad quality and blurred, second has good quality, but his hands shaked, and the second photo has moved compared to the first one. Help John to restore first(blurred) photo position, considering that the movement was in the same plane.

Solution: We highly encourage participants to use neural network based approaches for solving this task. You can download 30 samples from checker in txt format. Data generation for neural network training is one of the main point in our task. Converter from/to graphic format is also part of this task.

Registration can be done by captain. The team can consist from 1 to 3 team members: https://it-edu.mipt.ru/el/mod/apply/view.php?id=60 Checker http://huawei.it-edu.mipt.ru/marathon1 Rules https://it-edu.mipt.ru/en/huawei-codecraft-marathon/rules

Submission deadline is 2017 December 1, 23:59:59 Moscow time. Results will be announced on December 3 during the closing ceremony of 1/2 NEERC ACM ICPC 2017 at ITMO.

@stake are 9 internship certificates, 9 smartphones, several tours to HQ

Full text and comments »

  • Vote: I like it
  • +35
  • Vote: I do not like it