matrix's blog

By matrix, history, 3 years ago, In English,

Hi,

I've tried downloading testcases of BOI 2015 problems from the contest's website. However downloading 3 of 6 problems(EDI, NET, TUG) testdata results in 404 Not found error.

Is there anyone who has access to the testdata of these problems? Could you please share them here?

Thanks.

Read more »

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

By matrix, 3 years ago, In English,

Hi, Sharif University of Technology is holding an international AI competition. You may read a short description about it below:

=========

Student Scientific Chapter of computer engineering department at Sharif University of Technology will hold the first international Sharif Artifical Intelligence Challenge on March 2nd and 3rd.

This competition will be held in two phases including an online and an on-site phase in which competitors will compete in teams of three in a game designed by our technical team.

The only pre-requisite to enter this competition is familiarity with programming using C++, Java or python. But obviously, knowledge of algorithmic thinking and artificial intelligence will be a great asset for any of the participating teams. The registration for online competition is free and open from february 1st through to february 8th available at http://aichallenge.sharif.edu .

After finishing the online phase which starts on February 9th and continues untill February 17th we will run submitted codes and teams with highest scores will make it to on-site competition. Winners of on-site competition are awarded. For further news and announcment please checkout our blog at http://aichallenge-en.blog.ir or follow @aichallenge on twitter and instagram.

THE COMPETITION IS FIERCE.

=========

UPDATE #1: On-line competition is open to everyone however to participate in the on-site contest you have to be a student. You may participate in the on-line competition with a team of at most three members however participating in the on-site contest requires a team with exactly three members.

Read more »

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

By matrix, 5 years ago, In English,

495A - Цифровой индикатор

For each digit x you can count the number of digits y that because of some broken sticks x is shown instead of y by hand. for example when x = 3, y can be 3, 8 and 9. Let's denote this number by ax. Then if the input is xy (the first digit shown in the counter is x and the second is y) the answer will be ax × ay.

495B - Модулярные уравнения

  • If a < b then there is no answer since .
  • If a = b then x can be any integer larger than a. so there are infinite number of answers to the equation.
  • The only remaining case is when a > b. Suppose x is an answer to our equation. Then x|a - b. Also since then b < x. These conditions are necessary and sufficient as well. So the answer is number of divisors of a - b which are strictly greater than b which can be solved in .

494A - Сокровище

Consider a string consisting of '(' and ')' characters. Let's build the following sequence from this string:

  1. a0 = 0

  2. for each 1 ≤ i ≤ |s| ai = ai - 1 + 1 if si = '(' and ai = ai - 1 - 1 otherwise. (The string is considered as 1-based index).

It can be proven that a string is beautiful if the following conditions are satisfied:

  1. for each 0 ≤ i ≤ |s| ai ≥ 0.

  2. a|s| = 0

Using the above fact we can prove that if in a beautiful string we remove a ')' character and put it further toward the end of the string the resulting string is beautiful as well. These facts leads us to the following fact: if we can move a ')' character further toward the end of string it is better if we'd do it. This yields the following greedy solution:

We'll first put exactly one ')' character at each '#' character. Then we'll build the sequence we described above. if the first condition isn't satisfied then there is no way that leads to a beautiful string. So the answer is -1. Otherwise we must put exactly a|s| more ')' characters in the place of last '#' character. Then if this string is beautiful we'll print it otherwise the answer is -1.

494B - Одержимость строкой

We call an index i(1 ≤ i ≤ |s|) good if t equals si - |t| + 1si - |t| + 2... si. To find all good indexes let's define qi as the length of longest prefix of t which is a suffix of s1s2... si. A good index is an index with qi = |t|. Calculating qi can be done using Knuth-Morris-Pratt algorithm.

Let's define ai as the number of ways to choose some(at least one) non-overlapping substrings of the prefix of s with length i (s1s2... si) so t is a substring of each one of them and si is in one the chosen substrings(So it must actually be the last character of last chosen substring). Then the answer will be .

Also let's define two additional sequence q1 and q2 which will help us in calculating a.

The sequence a can then be calculated in O(n) as described below:

If i is not a good index ai = ai - 1 since in each way counted in ai the substring containing si also contains si - 1 so for each of these ways removing si from the substring containing it leads to a way counted in ai - 1 and vice-versa thus these two numbers are equal. If i is a good index then ai = q2i - |t| + i - |t| + 1. To prove this let's consider a way of choosing substring counted in ai. We call such a way valid. The substring containing si can be any of the substrings sjsj + 1... si (1 ≤ j ≤ i - |t| + 1). There are i - |t| + 1 valid ways in which this substring is the only substring we've chosen. Number of valid ways in which substring containing si starts at sj equals to q1j - 1. So the total number of valid ways in which we've chosen at least two substrings are equal to which is equal to q2j - 1. So ai = q2i - |t| + i - |t| + 1.

494C - Помощь нуждающимся

We'll first create a rooted tree from the given segments which each node represents a segment. We'll solve the problem using dynamic programming on this tree. First of all let's add a segment [1, n] with probability of being chosen by Malek equal to 0. The node representing this segment will be the root of the tree. Please note by adding this segment the rules described in the statements are still in place.

Let's sort the rest of segments according to their starting point increasing and in case of equality according to their finishing point decreasing. Then we'll put the segment we added in the beginning. A segment's father is the right-most segment which comes before that segment and contains it. Please note that since we added segment [1, n] to the beginning every segment except the added segment has a father. We build the tree by putting a segment's node child of its father's node.

In this tree for each two nodes u and v which none of them are in the subtree on another the segments representing these two nodes will not overlap. Also for each two nodes u and v which u is in subtree of v segment representing node u will be inside(not necessarily strictly) segment representing node v. We define mxi as the maximum money a person in the segment i initially has. mxi can be calculated using RMQ. Let's define ai, j as the probability of that after Malek finishes giving his money the maximum in the segment i is at most {mx}i + j. The properties of the tree we built allows us to calculate ai, j for every i and j in O(q2) (since 1 ≤ i, j ≤ q). If number of the segment we added is k then the answer will be .

Calculating ai, j is described below:

Suppose f is a child of i and suppose Malek doesn't accept the i-th recommendation. Then since we want the maximum number after money spreading to be at most mxi + j in segment i and since f is inside i we want the maximum number after money spreading to be at most mxi - mxf + j. If Malek accepts the recommendation then we want it to be at most mxi - mxf + j - 1. So if probability of i-th recommendation being accepted by Malek be equal to pi then . Using this formula we can calculate ak, j recursively and calculate the answer from it in O(q2). The overall complexity will be O(nlgn + q2). nlgn for creating RMQ used for calculating the array mx and q2 for the rest of the algorithm.

494D - День рождения

We solve this problem by answering queries offline. We'll first store in each vertex v number of vertices such as x for which we must calculate f(v, x) . starting from the root. We'll keep two arrays a and b. Suppose we're at vertex v right now then ai equals d(i, v)2 and bi equal d(i, v). Having these two arrays when moving from vertex v to a child with an edge with weight k one can note that bi for all is inside subtree of v decreases by k and all other bis gets increased by k. Knowing this fact one can also update array a as well. To calculate f(v, x) it's enough to be able to calculate sum of ais for all i inside subtree of x. Handling each of these operations is a well known problem and is possible using a segment tree. Overall complexity is O((n + q)lgn). There is an online solution using dynamic programming as well.

494E - Шарти

Let's first solve this problem for another game: Suppose that we've an n × n table. Each cell have some(possibly zero) marbles on it. During each move the player chooses a square with side-length at most k which its lower-right cell has at least one marble, he removes one marble from it and puts one marble in every other cell of this square. One can notice that in such game each marble is independent of the others and doesn't affect other marbles. So one can see this game as some separate games played on some tables. More formally for each marble placed in a cell such as (i, j) consider the game when played on a i × j table which the only marble placed on it is at its lower-right cell. Let's denote the Grundy number of this game by gi, j. Then according to Grundy theorem the first player has a winning strategy if and only if the xor of gi, j for every cell (i, j) having odd number of marbles on it is positive.

To calculate gi, j note that the first move in such game must be choosing a square with its lower-right cell being the lower-right cell of table. So the only thing to decide is the side-length of chosen square at the first move. Let's say we choose the first square width side length l. Grundy number of the next state will be equal to xor of gc, d for every i - l < c ≤ i, j - l < d ≤ j. Using this fact one can calculate gi, j for all (1 ≤ i, j ≤ a) (a being an arbitrary integers) in O(a3).

If we calculated the first values of gi, j one can see a pattern in the Grundy numbers. Then one can prove that gi, j = min(lowest_bit(i), lowest_bit(j), greatest_bit(k)) where lowest_bit(x) =  the maximum power of 2 which is a divisor of x and greatest_bit(x) =  the maximum power of 2 which is not greater than x.

Now let's prove that our first game(the game described in the statement) is actually the same as this game. Suppose that a player has a winning strategy in the first game. Consider a table containing one marble at every cell which is white in the table of the first game. We'll prove that the same player has winning strategy in this game as well. Note that a cell is white in the first game if and only if the parity of marbles in the second game is odd so there is at least one marble on it. So as long as the other player chooses a square with its lower-right cell having odd number of marbles in the second game, his move corresponds to a move in the first game so the player having winning strategy can counter his move. If the other player chooses a square with its lower-right cell having even number of marbles, it means the cell had at least 2 marbles on it so the player can counter it by choosing the same square which makes the parity of every cell to be the same after these 2 moves. And since it can be proven that both of the game will end at some point then the player has winning strategy in this game as well. The reverse of this fact can also be proven the same since if a player has a winning strategy there is also a winning strategy in which this player always chooses squares with lower-right cell having odd number of marbles(since otherwise the other player can counter it as described above) and counters the moves of the other player at which he chose a square with lower-right cell having even number of marbles by choosing the same square(since the Grundy number by countering in this way won't change the Grundy number and thus won't change the player with winning strategy).

So if we consider a table having one marble at each of the cells which are in at least one of the rectangles given in the input we only need to calculate the Grundy number of this state and check whether it's positive or not to determine the winner. To do this for each i(1 ≤ i ≤ greatest_bit(k)) lets define ai as the number of cells (x, y) which are contained in at least one of the given rectangles, 2i|x and 2i|y. Lets also define agreatest_bit(k) + 1 = 0. Then according the fact we described above about gi, j the number of 2is which are xored equals ai - ai + 1. Knowing this calculating the Grundy number of the initial state is easy. Calculating ai is identical to a very well-known problem which is given some rectangles count the number of cells in at least one of them and can be solved in O(mlgm) (m being number of rectangles). So overall complexity will be O(mlgmlgk).

If there is any problem in the editorial please feel free to note that to us.

Thank you.

Read more »

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

By matrix, 5 years ago, In English,

Hi,

Codeforces Round #282 will be held at 13th of December, 19:30 MSK. Please don't note anything since the time is the usual time of contests.

The round is prepared by FarbodY, Haghani and Me(matrix).

We'd like to thank Zlobober who helped us a LOT for preparing the problems, MikeMirzayanov for the Polygon and Codeforces platforms and delinur for helping us in preparing statements and translating them.

Our special thanks goes to mruxim for testing the round.

The problems will be sorted according to the estimated order of difficulty according to our opinion but we strongly recommend you to read all of the problems.

As always the update regarding score distribution will be posted just before the round starts. :)

UPD: It was written that contest starts at 20:00 MSK. it was a mistake and is fixed now. The round starts at usual time 19:30 MSK.

UPD2: We also thank niyaznigmatul for testing our round.

UPD3: Score distribution:

Div1: 500-1000-1750-1750-2500

Div2: 500-1000-1500-2000-2750

As you might have noticed, the scores can now be multiples of 250 as well. Let's thank Codeforces team for adding this feature!

Good luck and Have fun!

UPD4: Congratulations to the winners of both divisions:

Div1:

  1. tourist
  2. winger
  3. sankear
  4. uwI
  5. Egor

Div2:

  1. Ginger88895
  2. pwild
  3. arthurpd
  4. konmaj
  5. ezkatka

The editorial for all problems except D and E Div1 are ready and can be found here. It'll be completed soon.

We thank you all for participating and hope you had a good time.

UPD5: The editorial is now complete and can be found here.

Read more »

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

By matrix, 5 years ago, In English,

Hi!

415A - Mashmokh and Lights

For this problem for each light j you could just iterate over all pressed buttons and find the first button bi that bi < j. Then you could output bi and move to next light.

Read more »

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

By matrix, 5 years ago, In English,

Hi everybody!

Codeforces round #240 will take place tomorrow 19:30 MSK

This is our first round in Codeforces and we hope that everything will be fine. The problems were prepared by Amir Keivan Mohtashami(matrix), Farbod Yadegarian(FarbodY) and Gerald Agapov(Gerald). Also special thanks to Mohammad Amin Khashkhashi Moghaddam(alex-mercer) for testing this round.

I want to also thank MikeMirzayanov for Polygon and Codeforces systems, and also Maria Belova(delinur) for translating the statements.

We wish you a good and challenging round.

Have fun!

Score distribution:

div1: 500 — 1000 — 1500 — 1500 — 2500

div2: 500 — 1000 — 1500 — 2000 — 2500 (standard)

UPD: due to technical reasons the round was delayed for 10 minutes. We apologize for any inconvenience caused.

Read more »

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