NALP's blog

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

By NALP, 11 years ago, translation, In English

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

Full text and comments »

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

By NALP, 11 years ago, translation, In English

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(li) and R = max(ri) 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 105. 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 bi. Let's describe an algorithm. It takes any counter i such that bi = ai 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 bi = ai else we must press the button.

  2. Why doesn't algorithm press some button multiple times? Because it presses button number i only if bi = ai, and after this pressing the value bi 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 bi = ai like this: every time we change value of the counter numbered i we check equation bi = ai 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 a1, a2, ..., an as a table which has size n × 20, and bi, j is jth bit in ai. 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 bi, 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 xi has ones.

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

Full text and comments »

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

By NALP, 11 years ago, translation, In English

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.

Full text and comments »

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

By NALP, 11 years ago, translation, In English

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

Full text and comments »

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

By NALP, 12 years ago, translation, In English

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 bj divide ai 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 r1, p1 and p2. Then:

r22·(B·p1 + A·p2) = r12·B·p1

Now it’s easy of understand, we must take maximum value of r1 and p1, and minimum value of p2 to maximize r2. 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 n1 = max(a, c) and m1 = max(b, d) — sides of bounding box. Then we can calculate value of function f(n1, m1, s), and add to the answer f(n1, m1, s)·(n - n1 + 1)·(m - m1 + 1), where two lastest brackets mean amount of placing this bounding box to a field n × m.

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

If n1·m1 > 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(n3), 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…

Full text and comments »

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

By NALP, 12 years ago, translation, In English

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!

Full text and comments »

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

By NALP, 12 years ago, translation, In English

Hello, friends!

A few hours later you're lucky to participate in this remarkable Codeforces Round #27 for Div. 21 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 #27!

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.

Full text and comments »

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

By NALP, 12 years ago, translation, In English

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.com/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.com/contest/165/standings

Full text and comments »

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

By NALP, 12 years ago, translation, In English

149A - Business trip

First, it is clear that if the sum of all numbers ai 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 ai is more. Thus, the solution is very simple: let's take months in descending order of numbers ai and in these months water flowers. As soon as the sum of the accumulated ai 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(ai)], 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, cl, cr), where the pair (l, r) defines a pair of brackets, and cl and cr 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, cl), and the final result is sum over the states of the form (k, c), where c must not conflict with the cr.

The answer to the whole problem may be calced as the internal dynamic. Time of solution — O(n2) 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.

Full text and comments »

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

By NALP, 12 years ago, translation, In English

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.

UPD: Thanks all for participation! The round has turn out difficult enough and only one person among all participants (including Div. 1) has solved all offered problems - akim239. Our congratulations for him!!

UPD: our congratulations for Top-10 participants in competition:
3. frp
6. hex539
7. not
10. ggbuaa

Full text and comments »

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

By NALP, 12 years ago, translation, In English

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

Full text and comments »

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

By NALP, 13 years ago, translation, In English

Task A. Double Cola

Let's designate characters on the first letter of the name. The queue looks like: SH-L-P-R-G, through 5 cans: SH-SH-L-L-P-P-R-R-G-G, through 10 cans: SH-SH-SH-SH-L-L-L-L-P-P-P-P-R-R-R-R-G-G-G-G.

The regularity is clear, and the solution is very simple: we will be iterated on p - we will find such minimum p that 5· 2p > n (thus if this number is less or equally we will subtract it from n) then we know that at first 2p Sheldon's stand, then 2p Leonard's and so on. And now we can easily answer who took a can number n (namely there was a person with number n / 2p in sequence SH-L-P-R-G (in 0-indexation).

Task B. Sets

For the solution the following important fact is required to us: we will admit elements v and u are in one set then in any of n· (n - 1) / 2 of sequences from the input data where meets v  u necessarily meets. And also if v and u are in different sets there is such sequence in which is v, but isn't present u. Then it is possible to enter the equivalence relation for all elements of all sets - two elements are equivalent, if there is no sequence where one element meets, and another isn't present. Classes of equivalence also are required sets.

It was possible to consider the answer as following algorithm: we will write out for each number the list of numbers of sequences where there is this number, and will unite two numbers if these lists are equal. This algorithm can be realized for O(n2 * log(n)) however the solution for O(n3) passes all tests with time large supply too.

The special case is a test with n = 2. This test was used for a considerable quantity of hacks.

Task C. General Mobilization

At first we will estimate from above the maximum time to which all divisions will reach capital - obviously it is required no more n days for this purpose. Therefore restrictions quite allowed model movements of divisions. The key moment of the solution - we will always consider divisions in priority order. Then in every day we will consider the list of those divisions who hasn't reached yet capital, and we will put in priority order on the necessary train. If the train is already filled, the division remains in a current city, differently we will change its position, and in day when the division will reach capital we will write down the answer. Total: in total days which it is necessary model, no more n, and every day we move no more n divisions. So our solution has asymptotic form no more O(n2)

The solutions using various structures of the data (sets, turns with priorities etc.) work for O(n2· log(n)) and it didn't always keep within in TL.

Task D. Two out of Three

The problem dares the dynamic programming. We will consider a state (i, j) meaning that in the current turn there is a person number i and also all people from j to n inclusive. Any turn achievable of the initial can be presented by corresponding condition. The quantity of conditions is O(n2), the quantity of transitions is only 3, that is O(1). So the total asymptotic form is O(n2).

Task E. Corridor

This problem has some solutions based on the various methods of the search of the area of the association of the figures on a plane. One of such methods is the method of vertical decomposition (more in detail you can esteem in various articles) and also it was possible to notice that among figures there are no three having non-zero crossing and consequently was to learn to find a total area of two figures enough. For this purpose also it was possible to use the various methods, for example, the author's solution is based on algorithm of cutting off of a convex polygon by a semiplane. Authors supposed the solution for O(n2).

Full text and comments »

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

By NALP, 13 years ago, translation, In English

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!

UPD: the contest is over, congratulations to the winner - tourist!

I recall this competition was a qualifying round, and the best 500 will take part in Yandex.Algorithm Round 1!

Today two participants were the most lucky - Hossein_Hima and ss.nurboolean, - they have taken 499-500 places together with result 978 scores.

Full text and comments »

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