Codeforces Round #188
By yaro, 11 years ago, translation, In English

Hello, friends!

Winter 188th Codeforces Round is coming!

We wished to prepare for you some enjoyable problems (as we believe, not very difficult) with nice ideas and clear statements.

"We" includes authors of the problems yaro and Rei, Codeforces Rounds supervisor Gerald and the platform founder MikeMirzayanov. Special thanks to Pasha (PavelKunyavskiy) and Artem (RAD) for the testing and helpful comments.

Last time I was preparing a competition here on Codeforces, Rounds were still "beta". Well, with less "beta" comes greater responsibility. So I wish the authors and the organizers a successfully held Round. As for the participants, I wish you the unconventional ideas, the clean code (and a clean keyboard, of course), and satisfaction from five (well, possibly the less number will also do...) correct and accepted solutions!

It seems to us that it is not an easy job to arrange the problems by their difficulty, so we have chosen the dynamic scores. Still (out of curiousity) let us put a bet on the following relative difficulties for the problems: div.1 — B-B-C-C-E, div.2 — A-B-C-C-E. How close is our guess?

UPD Sorry for the problems with the Codeforces testing queue during the round.

We will still be happy if you rate our contest (when it will be over): short survey.

And with the gap of one hack the winner of div.1 is meret (Jakub Pachocki)!

Div.1 standings, Div.2 standings.

Analysis (thanks to Rei for the translation).

Full text and comments »

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

ABBYY Cup 3.0. Solutions
By ruzana.miniakhmetova, 11 years ago, translation, In English

Dear all, ABBYY Cup 3.0 online-part is over!

Thank you for participating! We are sorry for inconveniences with testings. MikeMirzayanov has informed us about plans to buy new testing machins. So we hope that there won't be such cases in the future.

Solutions are the following:

Problem "Special task"

It was one of the easiest problems in the contest. A solution consists of considering several cases. The initial answer equals one. Firstly, let’s note that if there is a "?" in a string, so the number of every possible codes increases in 10 times. With the exception when "?" is at the beginning if a string so the number of every possible codes increases in 9 times. Next let’s consider the case when the letters are found in the strings. There are two cases here:

  • The first symbol of the string is not a letter. So one should multiply the answer by number of the arrangements of 10 figures for the number of different letters in the string.
  • The first symbol of the string is a letter. So one should multiply the answer by 9 and the number of the arrangements of 9 figures for the N - 1, where N is the number of different letters in the string.

    It is no need to realize long arithmetic here. As all the operations (with the exception of multiplying be 10 because of the "?" can be done by standard arithmetic. For multiplying by 10 you can simply output the number of required zeros.

    Problem "PE Lesson"

    To begin with the term “order of balls” conforms to commutation. And the constraint to number of kicking a ball conforms to the number of transpositions. The problem is to calculate the number of “suitable” commutations. The commutation is “suitable” means the following: if to divide the commutation into the loops then every loop will consist of no more than two elements with the maximum number of inversions equals 1. So you can solve the problem with the help on dynamic programming. For this purpose the function f(a, b) should be calculated, where a — is the digit 1 and b — is the digit 2 used in the problem. f(a, b) is the number of “suitable” commutations. One should note here that f(a, b) can be calculated using the following formula: , where I(n) = I(n - 1) + (n - 1) * I(n - 2) You can prove it yourselves.

    Problem "Suns and Rays"

    This problem has different solutions. Let’s consider one of them. Denote the initial image as T. There are two operations for T: erosion and delation. Erosion is an operation of substitution of all the pixels which refer to image and are contiguous with pixels of background for the pixels of background. Dilation is an operation which is similar to inverse erosion: we substitute the pixels of background which are contiguous with pixels of image for the pixels of image. For determination neighbouring pixels you can use 4-connected neighborhood. The beams will vanish and the sun will stay as only a circle after applying erosion operation to T for several times. Then we should apply dilation operation for several times. Note that number of applied dilation operation should be more than number of applied erosion operation. Denote the obtained image as P. Then let’s consider initial image T and sort out connected components corresponding to the suns. After that you should sort out parts corresponding to the beams. How do it? The pixels which are in the image T and which are not P are corresponding to the beams.

    Problem "EKG"

    Firstly one should sort out the chains in the waiting line. The chain is a sequence of the beavers which stay one after another. After that the length of all the chains and the chain in which are Smart Beaver are known. Secondly one can simply apply methods of dynamic programming for further calculation.

    Problem "Tidying up"

    Let’s move from initial matrix to the bipartite graph. The matrix elements (i, j) for which i + j are even should be place to one part, the matrix elements (i, j) for which i + j are uneven should be place to another part. The edges are corresponding to squares which are situated side by side. After that let’s weigh the edges. The edges which connect equal elements of matrix have weights 0, for unequal elements – weight 1. After that the problem is reduced to finding of the maximum independent edge set with minimal weight. Substantiation of above-stated is following: an answer to the problem represents a partitioning of initial matrix for pairs. Note that for any partitioning minimal number of changing matrix elements corresponds to the number of pairs on unequal elements. So in the optimal partitioning the number of pairs of equal elements is maximum. For solving minimum-cost flow problem is needed to use some effective algorithm. For example, Dijkstra algorithm with heap adding conversion of edges weights from Johnson's algorithm.

    Problem "Summer Homework"

    To solve this problem one should use segment tree. Let’s consider line segment [l;r] on this tree. For this purpose let’s introduce S(x), where x is integer. S(x) = F0 + xAl + F1 + xAl + 1 + … + Fr - l + xAr, where Fi – i-th Fibonacci number, Ai – the array which consists of even numbers. One should note that S(x) with x = 0, 1, 2… are similar to Fibonacci numbers. Id est S(x) = S(x - 1) + S(x - 2) for x ≥ 2. This means that for every line segment [l;r] one should memorize S(0) and S(1). To calculate S(x) for x ≤ 2 one could use the formula: S(x) = S(0)Fx - 2 + S(1)Fx - 1. So solving 2-type query is reduced to calculation no more than values if S(x) for different segment lines. The 1-type modification can be done by walking down the tree. For 3-type query one should use additional information in the tree and partial sums of Fibonacci number.

    Prblem "Good substrings"

    For a start one needs to learn to compare quickly any two substrings, which could be taken from the source string or from one of the strings, which corresponds to the rules. It can be done, for example, with the help of suffix array, that contains every possible input strings. After construction of such an array and calculation of LCP (longest common prefix) values the problem of comparison of two substrings reduces to computation the number of identical characters and comparison the characters, that come after identical blocks. Computation the numbers of identical characters are equivalent to a problem of calculation of minimum on the interval of an array of LCP values. Because the LCP array does not change, efficient resolution of such requests can be earned with help of RMQ algorithms. Thus, in time O(1) we can compare any two substrings. Note, that time of precomputing depends on algorithms used for suffix array building and construction of RMQ.

    Further we need to find the number of entries of a certain substring from the source string into the string of one of the rules. It can be done with help of binary search of string of rule in suffix array. Note, that we are able to compare two substrings in time O(1). Therefore complexity of search of the number of entries of a substring into a string will be .

    Now let’s consider a certain suffix of a source string. We know its LCP with the previous suffix. This is the lower limit for the number of the characters, which we are considering in this suffix. Note, that the number of entries of a certain prefix of considered suffix monotonously depends on length of this prefix. Therefore for each rule one can define by binary search what minimum and maximum length of a prefix can be, to fit this prefix for the rule. After, it is essential to cross all received intervals. It is likely that using another structures of data on strings can get a simpler solution. Technical realization of considered solution is fairly laborious.

    • Full text and comments »

    Tutorial of ABBYY Cup 3.0
    • Vote: I like it
    • +93
    • Vote: I do not like it

    ABBYY Cup 3.0 is waiting for you!
    By ruzana.miniakhmetova, 11 years ago, translation, In English

    UPD2: Dear all!

    As promised, we invite ABBYY Cup 3.0 online part 25 best participants to ABBYY Open Day which takes place on the 17th of July at ABBYY Headquarters. So the onsite will be held at ABBYY Open Day.

    If you want to visit us, please, mail to [email protected] in the next 5 days. Remind you that we'll privide you by food, lodging and help with transfer and visa. Transportations costs are on you.

    UPD1: Solutions!

    UPD: Dear all, ABBYY Cup 3.0 online part will take place today!

    Some notes:

  • The constest will be rated for all participants but programming problem contest winners.
  • Programming problem contest winners may register and take part in beyound the rating.
  • Our jury dicided to add 7th problem of their authorship.

    Good luck at the constest!

    Hi everyone!

    We are happy to announce ABBYY Cup 3.0, the long-expected programming contest! As promised, this year’s participants are to be given the tasks which won our programming problem contest.

    ABBYY Cup 3.0 has two parts, an online and onsite one. The first part is starting very soon – Wednesday, June 12, 17:00-21:00 Moscow time.

    We would like to give our personal thanks to Codeforces project team, especially to MikeMirzayanov and Gerald, for their help in running contests. And many-many thanks to all of you who participated there! Dear winners, please don’t get surprised that you can’t recognize the tasks you once sent to us, simply because they could easily be reserved for the onsite part and also because we could modify them seriously.

    The details

    The online round includes 6 tasks, 100 points each. All these tasks are divided in test sets and arranged either in two or three groups according to complexity level and point value. The first scheme implies there are an “easy” group and a “difficult” group of 30 and 70 points respectively. Another scheme provides three groups (ranked as “easy”, “medium” and “difficult”) of 20, 30 and 50 points per each. To add, we have a surprise in stock for you and this is a marvelous heuristic task!

    Official contest languages are C/C++, Pascal, C# and Java. You can program the tasks in any language supported by Codeforces, however the jury has no guarantee that complete solutions do exist for all the languages enlisted. Passing the whole chain of tests is necessary. When points are equal, time penalty is used according to ACM rules. Any fully completed test set means a fully completed ACM-task and is a signal flag to set time penalty for other contestants. Besides this year all participants will be in rating. Registration for ABBYY Cup 3.0 opens 12 hours before the start of the contest and closes when the contest is over. Just a brief reminder: winners of April tasks contest can take part in this one but won’t fight for ratings.

    What’s then?

    According to the online round’s results, 25 best participants are to meet in ABBYY Cup final, July 17, which takes place in company’s Moscow office along with ABBYY Open Day event. Food and lodging will be provided by ABBYY, travelling costs compensation will be dicussed individually.

    Good luck!

    • Full text and comments »

    Announcement of ABBYY Cup 3.0
    Announcement of ABBYY Cup 3.0 - Finals
    • Vote: I like it
    • +173
    • Vote: I do not like it

    ICPC Challenge 2013
    By NALP, 11 years ago, In English

    Hello everyone,

    I guess almost everyone knows that the ICPC Challenge takes place every year before the ICPC World Finals. Of course, this year isn’t an exception. If someone doesn't know, the ICPC Challenge is an additional AI-contest for the ICPC finalists where they have two weeks to solve a single game problem. After that, a double-elimination tournament will be held between the team's submissions. The results will be announced at the Finals.

    The ICPC Challenge 2013 has started several days ago (on the 3th of June, to be exact) and I want to solemnly declare that this year ICPC Challenge has been prepared by the team from Baylor University, North Carolina State University and Saratov State University, which I represent! We introduce you a new game called CodeRunner.

    About the Game

    The 2013 ICPC Challenge game, CodeRunner, has a playing field that looks something like the following figure. A red player and a blue player compete to collect gold, while avoiding several enemies that are moving around the map. Each player directly controls a single runner character, who can move left and right, climb up and down ladders and break temporary holes in the floor with a large hammer. In addition to collecting gold, the players earn points by exploring the map and trapping enemies and their opponent in holes.

    Surprise

    But the point of my speech is that everyone can compete in the challenge this year! In addition to the regular ICPC Challenge, a contest among ICPC World Finalist teams, we are running a new competition called the Open ICPC Challenge. This competition invites any competitive programmers worldwide to compete head-to-head on the same programming problem as the 2013 ICPC World Finalists.

    You can find more information here and here.

    We invite everyone to take part in this event!

    Good luck and have fun!

    Full text and comments »

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

    Codeforces Round #187
    By Sereja, 11 years ago, translation, In English

    Hello everyone!

    Codeforces Round #187 will take place on Friday, June 7th at 19:30 MSK. This is my seventh Codeforces round and I hope not the last.

    I'd like to thank Gerald, Furko and Aksenov239 for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

    I strongly recommend you to read ALL the problems.

    Gl & hf ! :)

    tutorial.

    Full text and comments »

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

    Codeforces passes 100000 users!
    By MikeMirzayanov, 11 years ago, translation, In English

    Our community keeps on growing and gaining in popularity! We are glad to announce that Codeforces has recently registered its one hundred thousandth user. Thanks to everybody who keeps the project going — the problem writers, testers, corporate partners and of course all members of the community. Our special gratitude is to the VK.com company!

    One cannot get enough of the good statistics. Here are some more numbers:

    • our database contains more than 3.5 millions of your submitted solutions,
    • the number of problems comes near 3000,
    • the number of site visitors per month excedes 400000,
    • the number of page views per month amounts is approximately 5000000.

    Full text and comments »

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

    Saratov State U Summer School — "Sazanka 2013"
    By MikeMirzayanov, 11 years ago, translation, In English

    The first information letter


    General information

    In the first part of August 2013 Saratov State University runs an international student summer school in computer programming. The exact dates are 5-15 of August. Teams of three people and individual participants are invited to take part in it.

    The school will take place in a picturesque place at one of Saratov resort centers on the Volga bank. The participants will be provided comfortable rooms for 2-4 people and meals three times a day. The resort center owns a beach and sport grounds.

    It will be 10 training days. The school includes lectures by Saratov state university coaches, joint trainings, problems tutorials and topical workshops. The curriculum is designed for younger university students who aspire to achieve high results at programming competitions. Official language is Russian.

    The fees are 16500 RUR (~ 525 USD) per a person. Moreover, each team or an individual participant should bring a laptop with the support of WI-FI.

    All interested participants and teams should register at http://goo.gl/DHwqU till 15th June 2013. Don't postpone the registration, as the number of participants we can take is limited.

    You can get additional information by e-mail mirzayanovmr[symbol-at]gmail.com. As since the official language of the school is Russian, the registration requires knowledge of Russian. Also it is recommended to view this page in Russian.

    Full text and comments »

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

    Codeforces Round #186 (Div. 2)
    By Furko, 11 years ago, translation, In English

    Hello everyone!

    Codeforces Round #186 (Div. 2) will take place on Thursday, May 30th at 19:30 MSK. This is my first Codeforces Round and I hope that everyone will enjoy this round.

    I would like to thank Gerald for helping me prepare this round. Special thanks to Delinur for translation of all problem statements into English.

    Problems point values today is: 500-1000-1500-2500-2500

    Good luck & have fun! :)

    Full text and comments »

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

    Codeforces Round #185
    By lydrainbowcat, 11 years ago, In English

    Hello,everyone!

    Codeforces Round #185 will take place on Sunday, May 26th at 19:30MSK (23:30CST).

    This round is initiated by zanoes, and here are the problem setters:

    • Div.1E & Div.2B —— zanoes (**Zhang Gaoxiang**)
    • Div.1D & Div.1A —— liouzhou_101 (**Wang Qisheng**)
    • Div.1C & Div.1B & Div.2A —— lydrainbowcat (**Li Yudong**)

    Testers are roosephu(Luo Yuping), FredaShi(Shi Haoyue), sjynoi(Sun Jiayu), sevenkplus(Gu Yuzhou), MinakoKojima(Tang Feihu) and Riatre.

    Especially thanks Gerald for helping us to prepare the round, MikeMirzayanov for the great platform and Delinur for translation.

    Score will be standard, 500-1000-1500-2000-2500 in both divisions. In our opinion, problems are easier than the past several rounds prepared by Chinese)

    This is our first Codeforces round, I hope you can enjoy it. Wish you high rating and good luck!

    UPD: We feel really sorry about the mistake we made. The following words were written by Div.1A (Div.2C)setter, liouzhou_101. http://codeforces.me/blog/entry/7773#comment-134702 .

    Meanwhile, It's also zanoes's and my fault that we didn't check his checker carefully, even brought troubles to Codeforces flat. I beg your forgive for liouzhou_101, for he also tried to prepare the round well these days.

    UPD2: The round will be unrated.

    Editorials will come out soon. Now you can find some of the editorials here: http://codeforces.me/blog/entry/7785

    Contest is over. Congratulations to the winners.

    Div.1

    1. zfmdhy786 (I promise it's someone who pretends to be roosephu, and I've known who he is.)
    2. cp12321
    3. RAD
    4. ACMonster
    5. kAc

    And ryz , cgy4ever, who passed problem E in the contest.

    Div.2

    1. ymxlkAc
    2. sasha.sochka
    3. bohuss

    Full text and comments »

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

    All Andrew Stankevich Contests at Gym
    By Fefer_Ivan, 11 years ago, translation, In English

    Good evening, Codeforces.

    Today I've added the first five contest of the famous Andrew Stankevich Contest series. They are available for virtual participation and practice.

    I competed in several Andrew Stankevich Contests and I can say that these contests are always well prepared and consist of extremely interesting problems. You can really enjoy taking part in them.

    Good luck and have fun.

    P.S. All contests are available in Andrew Stankevich Contests group.

    Direct links

    Please note that all problems uses different input and output files. You can find correct input/output file names at the contest dashboard and in the statements.

    Full text and comments »

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