Codeforces Round #189
By havaliza, 11 years ago, In English

Hello, Codeforces! :-{D

As two important events IOI and ACM ICPC are coming soon, me and my friends as the Iranian IOI team decided to prepare a gift for all the Codeforces users who'll soon participate in one of these events, and also everybody else. :)

This round authored by me (havaliza), dani1373 and keivan with help from fab. I want to thank all the Codeforces team for their kind and great effort to maintain this website.

Hope you enjoy solving the problems as much as we're enjoying preparing them! ^.^

Update 1. The score distribution for Div. 1 is 500-1000-1500-2500-2500 and for Div. 2 its regular.

Update 2. Special thanks to Aksenov239 who helped us so much to prepare this round.

Update 3. Here is the editorial. To be completed soon :)

Full text and comments »

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

MemSQL announces the start[c]up
By AlexSkidanov, 11 years ago, In English

MemSQL is happy to announce start[c]up -- a programming competition, hosted by Codeforces and MemSQL HQ located in San Francisco, California. start[c]up consists of two rounds.

All rounds will be prepared by MemSQL engineers: pieguy, nika, exod40, SkidanovAlex and dolphinigle.

Round 1 is online and takes place on July 13. Round 1 follows regular Codeforces rules and consists of 5 problems. For this round, the complexity of the problems will be comparable to a regular Codeforces round. There are no eligibility restrictions to participate in the round.

Round 2 takes place on August 3, consists of 5 problems, and uses regular Codeforces rules. The complexity of the problems is higher than a regular Codeforces round. Only people who finished in the top 500 in Round 1 can participate. The top 100 in round 2 will receive a start[c]up T-shirt.

For the Silicon Valley residents, MemSQL will be hosting up to 25 people on-site during the second round. The winner of the on-site round will be awarded a special prize.

MemSQL is building an in-memory database that powers many well-known companies, such as Morgan Stanley and Zynga. Nearly half of our engineers are TopCoder Open Algorithm finalists in recent years, and we have more IOI and ICPC medals than we have engineers.

The reason for such a skew towards topcoders is that only very good engineers can build a database. Even though topcoders might not have skills necessary to build a database, they are known to be very smart. We’ve seen that smart coders can quickly acquire necessary skills, but average coders, regardless of experience, cannot learn to be smart.

We have lots of exciting problems for topcoders. For example SQL Query optimizer, cluster management for the distributed system, lockfree storage engine were all written by topcoders in here. If you are looking for an internship or for a full-time position and want to work on exciting stuff with people who are as smart as yourself, send your resume to [email protected].

Full text and comments »

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

New feature of Polygon: tests for checkers and validators
By Fefer_Ivan, 11 years ago, translation, In English

Good afternoon, Codeforces!

Today I'll tell you about a new feature of Polygon system, which is used to prepare all Codeforces rounds. Of course the system is open to any user – many contests for other competitions and training camps are prepared there.

Two key elements of a problem, besides the author's solution, tests and statements, are two programs: the validator and the checker.

The validator is the program that reads the test and reports whether it corresponds to the condition of a problem or not. Validators must be absolutely formal – a validator validates a test if and only if it meets the conditions of the problem and can be safely added to the test set. You can easily write validators using the testlib.h library. Sometimes authors neglect validators (which never happens during the Codeforces contests) and it threatens the validity of tests. Since the Codeforces contests contain hacks, the importance of correct validator greatly increases. Naturally, all the hacks are validated before reaching a contestant’s solution. Most tasks have relatively simple validators, but when a problem contains additional conditions (for example, that there is a solution for the test), then the complexity of the validator is greatly increased.

The checker is the program that receives the test, the output of the participant’s code, the output of the jury’s code and determines the correctness of the participant’s output. Unfortunately, errors in the checker often lead to serious consequences. Not all problems let you simply compare the solutions. For example, in problem 234H - Merging Two Decks the checker uses a Cartesian tree. If the problem statement requires a certificate, then it’s a good idea to write the checker in the concept of readAnswer(ans)/readAnswer(ouf). You can easily write checkers using the testlib.h library.

Testing of these programs usually takes place either manually from the command line or indirectly — by adding wrong solutions and temporarily adding of non-valid tests. In fact, the authors often neglect to test checkers and validators. This method of testing is inconvenient, and the tests are not saved. When there are two authors cooperating, a co-author cannot view the tests, on which the validator/checker were tested, or restart them after the correction of the validator or checker.

The updated version of Polygon has improved immensely! We’ve made a convenient means for testing the validator and the checker.

Full text and comments »

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

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