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!

Hi to all!

A few hours later you're lucky to participate in Codeforces Round #159 for Div.2 participants, but traditionally the others can take part out of the competition. It has been prepared by me (NALP), Ivan Fefer (Fefer_Ivan), Pavel Holkin (HolkinPV), Vitaly Aksenov (Aksenov239) and Gerald Agapov (Gerald). Also we express thanks to Mary Belova (Delinur) and Mike Mirzayanov (MikeMirzayanov).

Traditionally I wish good luck, accepted solutions and successful hacking attempts for you!

UPD: Today it is decided to use dynamic scoring system. But the problems will be sorted from low difficulty to high by authors' opinion!

UPD: The contest finishes, congratulations to the winners!

1.GreatEagle

2.CarlyPlus

3.Dakurels

4.ytqiaqia

5.SuccessfulHackingAttempt

242A - Heads or Tails

This problem was very easy, we should only use two cycles with i and with j (a ≤ i ≤ x, b ≤ j ≤ y), iterate all possible outcomes of the game and print such in that i > j. The time is O(x·y).

242B - Big Segment

At first, we must note that the answer is always unique, because if segment i covers segment j, that segment j can't cover segment i. It possible if and only if there are coincide segments in the set, but it's not permissible by the statement. Let's pay attention the answer covers the most left point of all segments and the most right point of all points too. Now then we should found L = min(l_i) and R = max(r_i) and print index of segment [L, R], or  - 1 if there is no such segment in the set. The time is O(n).

242C - King's Path

The most important thing for accepted solution is that it is guaranteed that the total length of all given segments doesn't exceed 10⁵. We should use this feature, let's number allowed cells and found shortest path by BFS. It's easiest to use associative array such as map in C++ for numbering. The time is O(n·log(n)).

242D - Dispute

Denote current value of counter number i as b_i. Let's describe an algorithm. It takes any counter i such that b_i = a_i and presses its button. The algorithm finishes if there is no such i.

Let's proof correctness of the algorithm:

1. Why does Valera win the game? Because there is no such counter which has b_i = a_i else we must press the button.

2. Why doesn't algorithm press some button multiple times? Because it presses button number i only if b_i = a_i, and after this pressing the value b_i is increased and the equation will be true never.

3. Why is the algorithm fast? Because of paragraph 2 it does no more n pressings which produces no more n + 2·m increases of the counters. We should use queue for fast seaching counters which has b_i = a_i like this: every time we change value of the counter numbered i we check equation b_i = a_i and if it's true then we push value i to the queue. It's easy to understand that all indexes i will be in queue no more one time.

Also these paragraphs proof that the answer always exists. You must print  - 1 never. The time is O(n + m).

242E - XOR on Segment

Let's write numbers a₁, a₂, ..., a_n as a table which has size n × 20, and b_i, j is jth bit in a_i. Then sum of numbers on segment [l, r] equals . The last notation helps us to process queries.

For fast implementation we should use 20 binary trees like cartesian trees or range trees. Every tree matchs one of bits (and matchs one of the columns of the table b_i, j).

1. calculation of sum is equal to counting 1-s from l-th to r-th.

2. operation "xor" equals reversing all bits from l-th to r-th (i.e. 0 changes to 1, 1 changes to 0).

The first operation executes for all bit numbers, the second executes only for bits in which input number x_i has ones.

These operations may be easy implemented with binary trees. The time is O(m·log(n)·20).

Hi to all!

A few hours later you're lucky to participate in Codeforces Round #149 for Div.2 participants, but traditionally the others can take part out of the competition. It has been prepared by me (NALP), Igor Kudryashov (Igor_Kudryashov), Pavel Holkin (HolkinPV) and Gerald Agapov (Gerald). Also we express thanks to Mary Belova (Delinur) and Mike Mirzayanov (MikeMirzayanov).

Traditionally I wish good luck, accepted solutions and successful hacking attempts for you!

The standart scoring system will be used: 500-1000-1500-2000-2500

UPD: The contest is over, thanks to all!

UPD: Congratulations to the winners:

1. Fio

2. ballmaids00

3. mihaipopa12

4. Yukari

5. chlxyd

UPD: the tutorial has been published.

Hi!

A few hours later you're lucky to participate in Codeforces Round #147 for Div.2 participants, but traditionally the others can take part out of the competition. It has been prepared by me (NALP), Igor Kudryashov (Igor_Kudryashov), Pavlik Holkin (HolkinPV), Gerald Agapov (Gerald), Mary Belova (Delinur) and Mike Mirzayanov (MikeMirzayanov).

Traditionally I wish good luck, accepted solutions and successful hacking attempts for you!

The standart scoring system will be used: 500-1000-1500-2000-2500

UPD: The contest has ended, congratulations to the winners:

1. try_skycn

2. AntiKismet

3. dianbei_03

4. Uncia

5. Bigsophie

Hi to all!

215A - Bicycle Chain

Because of small constraints we can iterate i from 1 to n, iterate j from 1 to m, check that b_j divide a_i and find max value of . Then we can start this process again and find amount of the pairs in which is max value.

215B - Olympic Medal

Let amagine we have values of r₁, p₁ and p₂. Then:

Now it’s easy of understand, we must take maximum value of r₁ and p₁, and minimum value of p₂ to maximize r₂. You could not use three cycles for iterating all values, but you could find property above about at least one value and use two cycles.

215C - Crosses

Let’s iterate n₁ = max(a, c) and m₁ = max(b, d) — sides of bounding box. Then we can calculate value of function f(n₁, m₁, s), and add to the answer f(n₁, m₁, s)·(n - n₁ + 1)·(m - m₁ + 1), where two lastest brackets mean amount of placing this bounding box to a field n × m.

Now we must calculate f(n₁, m₁, s). At first, if n₁·m₁ = s then the result of the function is 2·(⌊ n₁ / 2⌋ + 1)·(⌊ m₁ / 2⌋ + 1) - 1 (you can prove it to youself).

If n₁·m₁ > s then we must to cut 4 corners which are equal rectangles with square . We can iterate length of a one of sides, calculate another side, check all constraints and add 2 to the result of the function for all such pairs of sides.

The time of a solution is O(n³), but it’s with very small constant, less then 1.

215D - Hot Days

You can use only two features about this problem: the solution is independenly for all regions and there are only 2 possible situations: all children are in exactly one bus or organizers must take minimum amount of bus such no children got a compensation. It’s bad idea to place some children to hot bus and to place some children to cool bus simultaneously.

For solving you must calculate this 2 values and get minimum.

215E - Periodical Numbers

Will be soon…

Hi!

A few hours later you're lucky to participate in Codeforces Round #132 for Div.2 participants, but traditionally the others can take part out of the competition. It has been prepared by me (NALP), Edvard Davtyan (Edvard), Vitaly Aksenov (Aksenov239), Gerald Agapov (Gerald), Mary Belova (Delinur) и Mike Mirzayanov (MikeMirzayanov).

Traditionally I wish good luck, accepted solutions and successful hacking attempts for you!

Especially, we want to wish grand results and good luck to all sportsmens, who are representing their countries on XXX Olympic Games in London!

Today it is decided to use dynamic scoring system. But the problems will be sorted from low difficulty to high by authors' opinion!

UPD: The Round is finished, thanks to all for participation! We hope you have got fun!

UPD: Congratulation to winners!

1. yooo — solved all problems!

2. zzy

3. High_Rich_Handsome

4. bookcity_clock

5. capythm

UPD: Tutorial in English is published!

Hello, friends!

A few hours later you're lucky to participate in this remarkable Codeforces Round #2⁷ for Div. 2¹ participants, but traditionally the others can take part out of the competition.

It has been prepared by a small band of authors: me (NALP), Igor Kudryashov (Igor_Kudryashov), and Pavel Kholkin (HolkinPV). There were Gerald Agapov (Gerald), Maria Belova (Delinur) and Mike Mirzayanov (MikeMirzayanov) with us as always.

It’s well-known that you can participate in this Round into competition only today! There won’t be another Codeforces Round #2⁷!

Traditionally I wish good luck, accepted solutions and successful hacking attempts for you!

UPD: Points are standard: 500, 1000, 1500, 2000, 2500.

UPD: Round is over, thanks to all! We hope you have got a fun. Don't forget, system testing will be soon.

Dear friends!

The next competition — Codeforces Round 112 for participants Div. 2 will take place through a pair of hours, but the others can traditionally participate out of competition. It has been prepared by a small command of authors: me (NALP), Artem Rakhov (RAD) and Pavel Holkin (HolkinPV). There were Gerald Agapov (Gerald), Maria Belova (Delinur) and Michael Mirzayanov (MikeMirzayanov) with us as always.

Especially I would like to wish good luck to my teammates Artem Rakhov and Max Ivanov (e-maxx) who recently flew to the U.S. to participate in Onsite Round Facebook HackerCup.

We hope that this problems will be pleasant to all participants and everyone will take the deserved high place in the standings :)

UPD: The contest is over, thanks to all for taking part :) We hope you have fun.

UPD: You can find the tutorial here http://codeforces.me/blog/entry/4124

UPD: Congratulations to the winners!

1. Doriam30

2. woshisb

3. Senjougahara_Hitagi

4. LiWenHaoTianXiaDiYi

5. pqxdcel

6. UranusX

7. QDkAc

You can see the full standings here: http://codeforces.me/contest/165/standings

149A - Business trip

First, it is clear that if the sum of all numbers a_i is less than k, then Peter in any case will not be able to grow a flower to the desired height, and you should output <<-1>>.

Secondly, it is easy to see that if we want to choose a one month of two, in which we watered the flower, it is better to choose one where the number of a_i is more. Thus, the solution is very simple: let's take months in descending order of numbers a_i and in these months water flowers. As soon as the sum of the accumulated a_i becomes greater than or equal to k — should stop the process, the answer is found.

149B - Martian Clock

In this task required only the ability to work with different numeral systems. Let's try to go through numeral bases, each base to check whether it is permissible, as well as convert hours and minutes to the decimal system and compared with 24 and 60, respectively.

What is maximal base, that we need to check? In fact, it is enough to 60, because 60 — upper limit on the allowable number. It follows from the fact that if the number in an unknown number system consists of one digit, then its value in decimal not ever change, otherwise its value is not less than the base.

It is also worth to consider the case with the response <<-1>>, for this example, you can check a big base, such as 100, and even if the time for him correct, then for all large, it is also correct and the answer is <<-1>>.

149C - Division into Teams

Sort all the boys on playing skill. Then, if we send in the first team all the boys standing in a sorted array for odd places, and the second — even standing on the ground, then all requirements for division executed.

The first two requirements are obviously satisfied.

To prove the third we consider the geometric representation: Let each child designated point on the X axis with a value equal his playing skill. Connect the points with segments numbered 1 and 2, 3 and 4, and so on. If n is odd, then join the last point with the nearest the previous one.

Obviously, all these segments don't intersect in pairs, except at the points, and their total length is equal to the difference amounts to play boys' skills contained into the first team and second team. It is also clear that all of these segments completely contained in the interval [0, max(a_i)], as well as the pairs are a length of zero crossing, the third requirement is satisfied, which we proved.

149D - Coloring Brackets

We introduce the notation of colors: 0 — black, 1 — red, 2 — blue. Note that a single pair of brackets has 4 different coloring: 0-1, 1-0, 0-2, 2-0.

Consider the dynamic programming, where the state is (l, r, c_l, c_r), where the pair (l, r) defines a pair of brackets, and c_l and c_r denote a fixed color for them. The value of the dynamic is a number of ways to paint all the parenthesis brackets inside the interval (l, r) in compliance with all conditions.

We write down all the pairs of brackets that are directly placed into a pair of (l, r), let k of their pieces. Moreover, we consider only the first level of nesting, it is directly attached.

In order to calculate the value of the dynamics for the state, within this state shall calculate the another dynamic, where the state is a pair (i, c) which means the number of correct colorings of the first i directly nested parentheses, and all inside them, if the latter closing bracket has a color c. Calcing the values of this dynamic is very simple, let's try to paint a (i + 1)-th parenthesis in one of four variants, but you should keep in mind possible conflicts. In such dynamics the initial state is a pair (0, c_l), and the final result is sum over the states of the form (k, c), where c must not conflict with the c_r.

The answer to the whole problem may be calced as the internal dynamic. Time of solution — O(n²) by a factor of about 12.

149E - Martian Strings

We will solve the problem separately for each m strings. Thus, suppose we have a string p, its length is l, and we need to check whether the Martian be seen.

We introduce additional arrays: let pref[i] is minimal position in the s of the begin of occurrence p with length exactly i, and let suff[j] is the maximum position in the s of the end of occurrence p with length exactly j

It is easy to understand that a Martian could see the p, if there exists an i, that suff[l - i] ≥ pref[i] + l - 1.

How to calculate the arrays? For pref array is sufficient to find Z-function p#s, but for an array of suff — Z-function r(p)#r(s), where r(t) means the reversed string t. Using an array of Z-functions calcing of arrays suff and pref is trivial.

Dear friends!

The next competition - Codeforces Round 101 for participants Div2 will take place through a pair of hours, but the others can traditionally participate out of competition. It has been prepared by a small command of authors: me (NALP), Polina Bondarenko (Polichka) and Gerald Agapov (Gerald). There were Artem Rahov (RAD), Maria Belova (Delinur) and Michael Mirzayanov (MikeMirzayanov) with us as always.

It is a little bit about authors: all of us study at the Saratov State University at faculty of Computer Sciences and Information technology on 4th course. Now in free time from competitions and problems we pass the exams :) I’m a 1/3 part from command Saratov SU#2, and Gerald with Polina - 2/3 from Saratov SU#1. We would like our rounds became kind tradition on Codeforces and you have seen us among authors soon again.

We hope that this problems will be pleasant to all participants and everyone will take the deserved high place in the total table. Today you will help Santa Claus, Elf, Vasya and the other characters. All the similarities to real people are casual :)

The points on problems are distributed today in this way: 500-1000-2000-2000-2500

UPD: You can read the tutorial here.

Registration to SRM 523 is open! See time on your timezone here

Task A. Double Cola

Task B. Sets

Task C. General Mobilization

Task D. Two out of Three

I'm glad to welcome all fans of programming!

The second qualifying round Yandex.Algorithm will take place today, and it was prepared for you by Artem Rakhov, Michael Mirzayanov and me.

Please pay attention that as well as during the previous qualifying round Codeforces's functionality will be a little cut down for the period of the competition. Don't worry, all will return into place after the round termination.

I remind the best 500 participants pass in Yandex. Algorithm 2011 Round 1 which will take place on May, 20th at 19.00

Good luck!