Seyaua's blog

By Seyaua, 5 years ago, In English,

Hello Codeforces community,

I am happy to announce that Rocket Fuel Inc. will be hosting a Rockethon competition again! The contest is prepared by Rocket Fuel employees Eldar Bogdanov, Anton Lomonos, Lasha Lakirbaia, Alexander Ruff, Nikhil Goyal and me, Ievgen Soboliev. We hope everyone will find some interesting problems in the contest and everyone will have as much fun solving these problems as we had preparing them. Just like last year, the best participants will receive valuable prizes and top performers will get Rockethon 2015 T-shirts! Also, Rocket Fuel is interested in hiring people after this event, so please fill out the simple form during registration.

About Rocket Fuel

Rocket Fuel is building technology platform to do automatic targeting and optimization of ads across all channels — display, video, mobile and social. Our pitch to advertisers is very simple "If you can measure metrics of success of your campaign, we can optimize". We run campaigns for many large advertisers and our clients include many top companies within the following industries: autos, airlines, commercial banks, telecom, food services, insurance, etc. Examples include BMW, Pizza Hut, Brooks Running Shoes and many more!

We buy all our inventory through real time bidding on ad exchanges like Google and Yahoo. Ad exchanges are similar to stock exchanges except the commodity being traded is ad slots on web pages. Our serving systems currently process over 60B bid requests/ day with a response time requirement of 100ms. Our data platform has 64 PBs data that is used for analytics as well as modeling.

Our engineering team is still small (~150) enough for any one person like yourself to make a huge impact. The team represents many top schools in US and outside — Stanford, Carnegie Mellon, MIT, Wisconsin-Madison, IIT (India), Tsinghua (China).

Rocket Fuel has been named #4 on Forbes Most Promising Companies in America List in 2013 and #1 Fastest Growing Company in North America on Deloitte’s 2013 Tech Fast 500 and our CEO George John was recently named “Most Admired CEO” by the SF Business Times in 2014.

My Personal Story

About one year ago I visited CodeForces and saw an announcement of Rockethon 2014. My first thought was "Another competition from a big company, that's nice!". I took part in this contest, performed quite well and recruiters from Rocket Fuel have contacted me and scheduled some interviews. I passed the interviews and now I'm here, in Rocket Fuel.

It has been a nice opportunity to learn advanced concepts of software engineering from a huge amount of smart people working with you. Also, our activities here are not limited only to writing code — we do fun things here like playing basketball, soccer, table tennis. I invite everybody to take a part in the competition and would be glad to hear if any of you thinking about joining Rocket Fuel.

Contest Overview

The contest will begin on February 7, 9AM PST.

The contest length is 3 hours.

The testing of each submission will be performed as soon as the submission is received and the verdict will be delivered to the submission author right away.

The problemset will consist of 7 problems. Each problem can contain from one to three subproblems. Each subproblem will be worth a fixed amount of points. The ties between contestants with the same score will be broken by penalty time which is computed similar to ACM scoring system.

Prizes

The top three contestants will receive the following prizes:

1) IPhone 6 (16 Gb)

2) Participant can choose Apple Watch or Samsung Gear S

3) Participant can choose Apple Watch or Samsung Gear S

The top 150 performers will receive a Rockethon T-shirt designed specially for this contest.

If you are unable to take part in the competition but are interested in joining Rocket Fuel, we will be screening resumes submitted through the special form.

Read more »

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

By Seyaua, 6 years ago, translation, In English,

Hello everyone!

I invite all of you to take part in the contest 101 Hack March. The link for the contest start time in different timezones. There will be five problems in two hours. I am the author of the problems and in my opinion problems are very interesting.

Attentive people can observe, that in 30 minutes before this contest the TopCoder SRM 614 will start. I want you to participate at HackerRank and would like to mention, that top-10 contestants will receive t-shirts! It is your choice where to participate, however, there are four SRM-s per month at TopCoder, but at HackerRank you will have a chance to win exclusive t-shirt!

Again, in my opinion, problems for the contest are very good, and it wouldn't be nice if these problems will stay unsolved :)

Many thanks to all of you, who will take part in 101 Hack March!

Read more »

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

By Seyaua, 6 years ago, translation, In English,

Problem A. Morning run

We were asked to find the expected value of meetings between the runners. How to do that? As the first step, expected value is lineal, so we can split the initial problems into the different ones: find the expected value of meetings between the fixed pair of runners. We will solve these problems. To do that we need to make some observations:

  1. Let x be the distance between the two runners and they run face to face for infinite amount of time (probability of that obviously equals to 0.5·0.5 = 0.25). Then the first meeting will happen at time , the next one — , the next — and so on.

  2. Let us assume that every run ran for l time units. Then if two runners meet — they meet exactly two times. The probability of the meeting equals to 0.5, because in two cases they run in the same direction and in two cases in the different ones.

We will build our solution based on these two observations. As the first step let us represent t as t = k·l + p, where 0 ≤ p < l. Then each runner will run k full laps. What does that mean? Because we have pairs of runners, then in those k laps each pair will have 2k meetings with probability equals to 0.5. So, we need to add to the answer.

Now we need to take into account p seconds of running. Let us assume that the distance between two runners is x and they run towards each other. Then they will meet if , or x ≤ 2t. They will meet once more if , ir x ≤ 2t - l. They cannot meet more than twice, because p < l.

Let us fix one of the runners, then using binary search we can find all other runners at distance no more than x from the fixed one. Let us choose x as x = 2t, and then the number of runners at the distance no more than x stands for the number of runners which meet with the fixed one at least once. If x = 2t - l, we will find the number of runners which meet with the fixed one exactly two times. Multiplying these numbers by 0.25 — probability of the meeting, and add it to the answer.

The complexity of this solution is . We can reduce it using two pointers method.

Problem B. Context Advertising

We were asked to find the maximal number of words we can fit into the block of size r × c. Let's first solve such problem: what is the maximal number of consecutive words which can fit in a row of lenth c, if the first word has index i. We can solve it using binary search or moving the pointer. Now let us build a graph, where vertices are the words and there is a directional edge between i and j, if words from i to j - 1 fit in one row of length c, but words from i to j don't. The weight of the edge is j - i. The we have the following problem: we need to find the path of length k, which has the maximal weight. Easy to solve it with complexity saving weights of all the paths with lengthes equal to the powers of two, or in O(n) time using dfs.

The other problems competitors faced — that we were asked to print the whole text, not only the length.

Problem C. Memory for Arrays

We were asked to find the maximal number of arrays we can fit into the memory. A small observation first, let the answer be k, then one of the optimal solutions fits the k smallest arrays into the memory. We can assume that we have arrays of size 1 and we want to arrange the memory for the maximal arrays as possible. Then if we have parts of memory of odd size, if we fit array of size 1 at this part we will obtain part of even size. From other hand, if we put arrays of bigger size we will not change the parity and if we don't fill it with arrays of size one and initially it's of odd size then in the end we will have at least one empty cell. So it's reasonable to put the arrays of size one into the memory of odd size. Let's do it until we can do it. We have three possible situations:

  1. We don't have memory parts of odd size anymore.

  2. We don't have arrays of size 1 anymore.

  3. We don't have neither arrays of size 1 neither memory parts of size 1.

Let us start from the first case. Suppose that there are some arrays of size 1 left, but there are no memory parts of odd size. Easy to see then in such case we need to group arrays of size 1 in pairs and then consider them as the same array. So we can divide every number by two and reduce the problem to the initial one.

In the second case if we divide every number by two we will obtain the same problem (and that cannot increase the answer).

The third case is similar to the second one.

When implementing this we need to remember that first we have to fill the memory with arrays which are build from the maximal numbers of initial arrays.

The complexity of the given algorithm is .

Problem D. Tennis Rackets

We were asked to find the number of obtuse triangles which satisfy the problem statement. Author's solution has complexity O(n2), but it has some optimizations, so it easily works under the TL.

Every triangle has only one obtuse angle. Due to symmetry reasons we can fix one of the sides and assume that obtuse angle is tangent to this side. Then we only need to find the number of such triangles and multiple the answer by 3.

Every side is also symmetric, so we can consider only one half of it and then multiple the answer by 2.

Let us assume that vertex A of the triangle has coordinates (0,0). Vertex B (0,) and C(2,0). Then we can find the coordinates of every single point at each of the sides and apply cosine theorem. We obtain the inequality which guarantee us that the triangle is obtuse. It can be written in many ways, on of them is following: If 1 ≤ i, j, k ≤ n — indices of points which are fixed at each of the sides, then triangle is obtuse iff: f(i, j, k) = 2i2 - i(n + 1) + 2j(n + 1) - ij - k(i + j) < 0. We can see that monotonically increases, so we can use moving pointer method applied to variable k. Then just go over all i from m + 1 to , then j from m + 1 till upper bound for k is less than or equal to n - m + 1 and just sum the results.

We should mention that all of the operations have to be done in int type, it significantly increases the speed.

Problem E. Sheep

Author's supposed greedy algorithm as a solution for this problem. Let us follow this algorithm. Let us create to label for every interval Positionv and MaximalPositionv.

Positionv — stands for position of v in the required permutation.

MaximalPositionv — stands for maximal possible position of v in the particular moment of the algorithm.

Also let's consider count as a counter with initial value of 0 and set of unprocessed vertices S. The algorithm is following.

  1. Using binary search we find the maximal possible distance between the farthest sheep. And then check whether exists the permutation with maximal distance no more than K.

  2. Sort all the intervals in the increasing order of ri.

  3. Positioni = 0, 1 ≤ i ≤ n, MaximalPositioni = n, 1 ≤ i ≤ n, current = 1, count = 0.

  4. Do count = count + 1, Positioncurrent = count, erase current from S, if S — is empty, required permutation has been found.

  5. Look at every interval connected to current, and update MaximalPositionv = min(MaximalPositionv, Positioncurrent + K)

  6. Build sets S(count, j) = {v|MaximalPositionv ≤ count + j}. If for every j ≥ K - count + 1 holds |S(count, j)| ≤ j go to the step 7, otherwise there is no such permutation.

  7. Choose the minimal j such that |S(count, j)| = j. Choose from it the interval with the smallest ri and consider it as a new value for current, go to the step 4.

First let us discuss the complexity. Let us fix K (in total there are iterations with fixed K).

Every step from 4 to 7 will be done at most n times (every time size of S decreases by one). Every step can be implemented in O(n) time. The most difficult one — step 6. But we can see that it's not necessary to actually build the sets, all we need to know — their sizes. This can be done in linear time just counting the number of intervals that MaximalPositionv = i. Let if be Ci — then size of S(count, j) equals to C1 + C2 + ... + Ccount + j, which can be easily calculated with partial sums.

Now let us discuss why this algorithm works. If we have Position labels for every interval — we obviously have the solution. Now let us assume that we ended up earlier. Then we will show that there is no such permutation. If algorithm ended, it means that for some count (consider the smallest such count), exists j0, that |S(count, j0)| > j0 at this step. Then |S(count, k)| > k. Let us prove that from contradiction. From the definition of count we have |S(count - 1, j)| ≤ j for every j ≥ k - count + 2. Then |S(count, j)| = |S(count - 1, j + 1)| - 1 ≤ j for every j ≤ k - 1. And S(count, j) = S(count, k) for k ≤ j < n - count = |S(count, j)| = |S(count, k)| ≤ j. Finally |S(count, n - count)| = n - count. Then |S(count, j)| ≤ j for every j, so we obtain contradiction. That means if algorithm stops at step 6 we have |S(count, k)| > k. So exist at least k + 1 interval, which still don't have assigned label Position and they should be assigned after count. So one of the intervals in S(count, k) has to have the value of Position at least count + k + 1. But every intervals in S(count, k) connected to at least one interval with Position ≤ count. So, we obtain that there is now such permutation.

Editorial was prepared by sdya and Seyaua.

Read more »

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

By Seyaua, 6 years ago, In English,

Here you can find the solutions for the problems from the past round. You can ask questions in the comments below.

A Div 2

If ai divide aj than ai ≤ aj. So the number which will divide every other number should be less than or equal to every other number, so the only possible candidate — it's the minimum in the array. So just check whether all elements are divisible by the minimal one.

B Div 2

Easy to see, that Ksusha is unable to complete her journey if there is a sequence of consecutive # with length more than k.

C Div 2 / A Div 1

The first observation — we don't care about the actual strings, all information we need — number of pairs {0,0}, {0,1}, {1,0}, {1,1}. Count that and then just follow the greedy algorithm, for the first player: try to get a index with {1,1} if there are some, than {1,0}, than {0,1} and than {0,0}.

For the second player similar strategy: first {1,1}, than {0,1}, than {1,0}, than {0,0}.

After that just compare who has more 1.

D Div 2 / B Div 1

Every path from the topleft cell to the bottomright cell contain exactly n + m - 1 cells. And all of the should be of different color. So n + m - 1 ≤ k. Due to the small constraints for k we may assume that bruteforce might work. The only optimization to get the correct solution is some canonization of the colors. So let's go over all of the cells in some order and color them but with following condition. If i > j, than color i appeared later than color j. If we bruteforce in such way we will have about 1 million different patterns for max case. Than just match them with already painted cells and calculate for each pattern how many different permutations of color we can apply to it.

E Div 2 / C Div 1

After reading the problem statement one can understand that all we need is to calculate the number of positive integer solutions of equation: (a + b + c)3 - a3 - b3 - c3 = n.

The key observation is: 3(a + b)(a + c)(b + c) = (a + b + c)3 - a3 - b3 - c3, after that simply calculate all divisors of and then first go over all x = a + b, such that then go over all y = (a + c) ≥ x, such that and then determine z = (b + c), such that . After that we need to solve the system a + b = x, a + c = y, b + c = z and find out how many solutions it adds.

D Div 1

We can see that we asked to calculate for all integer points inside the polygon or on its border. We can see that we can process Xs and Ys independently.

For each x determine yleft, yright, such that all points (x, y) where yleft ≤ y ≤ yright are inside the polygon and the range [yleft, yright] is as maximal as possible. Now let's assume that we have a1, a2, ..., ak different points with fixed x coordinate (a1 stands for x =  - 106, a2 for x =  - 106 + 1 and so on).

Now the required answer is a2a1 + a3(a2 + 22a1) + a4(a3 + 22a2 + 32a1) + ...

We can see that:

(a2 + 22a1) - a1 = a2 + 3a1,

(a3 + 22a2 + 32a1) - (a2 + 22a1) = a3 + 3a2 + 5a1,

and so on.

So we can precalculate partial sums like a2 + 3a1, a3 + 3a2 + 5a1, a4 + 3a3 + 5a2 + 7a1 (the difference between two consecutive sums is 2(ai + ... + a1), so we can do that in O(k) time).

After this precomputation we just need to sum the results.

E Div 1

Let's assume that we have a data structure which can perform such operations as: — add point (x,y) to the structure;

  • shift all points in the structure by vector (dx,dy);

  • answer how many point (x,y) are in the structure where x ≤ xbound, y ≤ ybound;

  • get all elements which are now in the structure;

For every vertex of the tree we will store the pointer to such structure.

How we update the structures. We will proceed all the vertices in dfs order, if we are in a leaf node, than we create structure which contains only one element (0,0).

Otherwise we will sort the children structures by it's size in decreasing order and assign the pointer of the biggest structure to the pointer of the current vertex (Don't forget to shift the structure by (1, weight of edge)).

After that we will go over all other children one by one and do the following thing:

  • Shift the structure by (1, weight of edge);

  • Get all elements from the structure;

  • For every element (x,y) answer the query xbound = L - x, ybound = W - y (we use parent's structure);

  • Add elements one by one into the structure;

After that answer the query xbound = L, ybound = W and add element (0,0).

The sum of the results of all the queries is our answer. It's easy to see that there will be no more than queries and add operations.

The remaining part is designing the structure.

It can be done in many ways. One of the ways:

  • We have small structures with sizes equals to powers of two;

  • Each structure — it's two-dimensional segments tree;

  • We can add one element in a following way: if there is no substructure with size 1, than add it; else get structures with sizes 1, 2, 4, ..., 2k and all its' elements and rebuild the structure with size 2k + 1;

  • Shifting — just remember shifting vector for every substructure;

  • Answering the query — go over all substructures and add the results.

Editorial was prepared by sdya and Seyaua

Read more »

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

By Seyaua, 6 years ago, translation, In English,

Hello everyone!

Round 2 of All-Russian Programming Championship CROC-2013 will take place today. Round was prepared by sdya, Seyaua, Gerald and traditionally, problem statements were translated to English by Delinur.

Good news for people, who didn't qualify to this round — today everyone can participate out the competition. Additionally, round will be rated for both official participants and out of competition participants.

Remind some facts about the official participants:

  • All the participants should be 18+ years old
  • The championship finals are going to take place on May, 16-17 in Moscow in the CROC office (50 participants)
  • The CROC company pays for the accomodation in Moscow during the finals
  • For Russian citizens: the travel expenses around Russia will be covered, the transport expenses outside Russia can be covered possibly partially but you need to contact CROC and clarify it for each particular case
  • All finalists should confirm invitation and their participation in finals until May 2

A little bonus: top 200 official Championship contestants will receive t-shirts!

Enjoy problems and good luck!

UPD: Point values for problems will be unusual today. 500-1500-1500-2000-2500 for first division and 500-1000-1500-2500-2500 for second.

UPD2: We are really sorry for technical problems. After some discussion we have decided that this round should be rated. The list of the finalists will be based on today's results.

Read more »

Announcement of Croc Champ 2013 - Round 2
Announcement of Croc Champ 2013 - Round 2
 
 
 
 
  • Vote: I like it
  • +108
  • Vote: I do not like it

By Seyaua, 8 years ago, translation, In English,
Southeastern European Regional Contest of ACM ICPC World Finals took place on 15th of October. However, there were a few major problems during the competition caused by some decisions of the Romanian judges. Here are some key points that led to absolutely unfair and unpredictable results:

1). Although it was declared that contest will be held in multisite mode testing of all the solutions was done on Bucharest PC^2 server. In spite of all requests on people organizing contests in Vinnitsa tests were never sent there. During the contest teams from Ukrainian site were submitting their solutions not directly to the main server, but using an additional online server of PC^2.
2). In the interval from 20th to 30th minute of the competition, server in Bucharest was rebooted and as a result all information about submits before that time was lost. It made a significant impact on penalties of many competitors.
3). During the contest participants had almost no ability to observe the results. All the teams in standings were shown as "TeamXX", where XX is the team number. The monitor was also refreshing very rarely.
4). During the contest some of the problems were rejudged. The problem "J" was rejudged almost at the end of the contest and problem "E" was rejudged only after the contest, while during the contest the clarification was sent that some tests do not fit the input format specification and teams had to deal with it by theirselves (instead of fixing wrong tests and making a rejudge at the moment it was found out). Moreover, some of the submits were judged long after they were sent. As an example, the team of Kharkiv National University had to wait more than 90 minutes before receiving the verdict for their submission of problem "C". It happened only after the direct question to the jury about why the problem is still in queue for judging.

I should also mention that the problem "I" was almost exact copy of a problem from SEERC 2010 contest, and the problem "J" was seen before on one of Moscow school olympiads. Apart from that many problem statements were prepared badly and had ambiguities in statements.

5). During the contest server was not available for significant amounts of time. Moreover, about 4 hours after the restart of the contest (about 4:30 after statements were distributed) the connection between servers in Vinnitsa and Bucharest was lost and as a result the solutions from teams participating in Vinnitsa site were not sent for judging to the server in Bucharest. During the contest those solutions were collected by organizers in Vinnitsa and later sent to Bucharest but the jury there refused to test those solutions even though it was a force-majeure situation. As you can see, the contest for participants in Vinnitsa appeared to be unexpectedly shorter.

As a result of the decisions of Bucharest side of the jury the results of SEERC-2011 can not be treated as fair because of all the problems listed above and the situation described in paragraph 5, in particular. All of that led to the situation in which teams were not in equal conditions. After such violations any regular competition would be at least considered unrated or the results would be split. (In this case the latter is impossible because it was a contest for one region).

I should also note, that it is impossible to recover all the penalty times, beacuse of loss of the data.

Read more »

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

By Seyaua, 8 years ago, translation, In English,

Here you can find solutions to the problems from the past round. Editorial for Problem D (Div 1) was prepared by sdya

Division 2, problem A

In this problem one could transform all letters in both strings to lower case and then compare the strings lexicographically.

Division 2, problem B

One can notice that if we want to divide a square into two equal parts, then the cutting line should pass through the center of our square. Thus, if the marked cell contains the center of the square, then we can’t make a cut, otherwise we can. Here is the code which solves the problem:

scanf("%d%d%d", &n, &x, &y);

n /= 2;

if ((x == n || x == n + 1) && (y == n || y == n + 1)) printf("NO\n"); else printf("YES\n");

Division 2, problem C (Division 1, problem A)

It is easy to see that in order to maximize the sum of squares, one should make all numbers except the first one equal to 1 and maximize the first number. Keeping this in mind we only need to check whether the given value of y is large enough to satisfy a restriction that all n numbers are positive. If y is not to small, then all we need is to ensure that x ≤ 1 + 1 + … + (y - (n - 1))2

Division 2, Problem D (Divison 1, problem B)

Let’s create an array used[], j-th element of which will be the index of the last number from the input, which is divisible by j. Then for each query we’ll iterate over all divisors of xi and for each k, which divides xi we’ll check whether it is “unique”. After that we’ll update used[k].

Division 2, Problem E (Division 1, problem C)

This problem has many different approaches. One of them uses the fact that the overall number of possible inputs is small and it is possible to compute the answer manually for all of them. One could also write a brute-force with a few optimizations, which works even without a precalc.

However, the major part of all solutions involved dynamic programming with bitmasks. The solution below was described by Zlobober.

Instead of counting the maximal number of free cells, we’ll count the minimal number of occupied cells. We’ll assume that the number of rows is not greater than 6 (otherwise we can rotate the board).

Let D[k][pmask][mask] be the minimal number of occupied cells in the first k columns with the restrictions that the k-th column is described by pmask (ones correspond to occupied cells and zeroes correspond to free cells) and k+1-st column is described by mask. To make a transition from D[k-1][*][*] we can iterate over all possible masks for the k-1-st column, check whether we can distribute spiders in kth column knowing the masks for k+1-st and k-1-st columns and find the minimal value of D[k-1][*][pmask] for all such masks.

 

The overall complexity is O(n*23m), n > m.

 

Division 1, Problem D

One can notice that if m = 1 then the answer is kn, because all colorings are possible.
Now we’ll assume that m > 1. Let’s look on the first column of the board (i.e. the vertical cut will be made right next to the first column). Suppose there are x distinct colors in this column. Then in the rest of the board there are also x colors. If we move the vertical line by one unit to the right, the number of different colors to the left of it will not decrease and the number of colors to the right of it won’t increase. It means that the number of different colors in both parts of the board will be also x. We can repeat this process until the line reaches the rightmost column, which means that the number of distinct colors in it is also x. It is easy to see that we can only use colors which belong to the intersection of sets of colors in the leftmost and rightmost columns in the rest of the board.

Let’s iterate over all values of x and y, where x is the number of colors in the leftmost column and y is the number of elements in intersection of sets of colors in the rightmost and leftmost columns. It is easy to see that x is limited by the number of rows in the board and y can’t be greater than x. Let’s find the answer for all such pairs of x and y and at the end we’ll add them up together.

 

Suppose x and y are fixed. We first need to choose (2x - y) colors from the given k colors, which we will use, which means that the answer for will be multiplied by C(k, 2x — y). After that we’ll choose (x-y) unique colors which will be used in the first column, which means that the answer will be also multiplied by C(2x-y, x-y). Then we’ll choose x-y colors for the rightmost column and multiply the answer by C(x, x-y). Now all we need to know is how many ways of coloring n cells into x colors are there. We’ll use a dynamic programming approach to solve this sub-problem.

 

Let d[i][j] be the number of ways to color a rectangle of unit width and length i into colors, numerated from 1 to j with the following restriction: if a < b then the first appearence of color a in the rectangle will be before the first appearence of color b.
Then we can calculate this function using the following recurrence:

d[i][j] = j * d[i — 1][j] + d[i — 1][j — 1].

After we finish calculating d[i][j], we need to multiply the answer by d[n][x]2 (to color the first and the last columns). Now we need to notice that we can reorder all colors in the first and the last columns in arbitrary way, which means that the answer should be multiplied by (x!)2. Finally, we need to multiply the answer by yn(m-2), which correspond to coloring the rest of our board.

 

Here is the code, which solves the problem for the given values of x and y:

long long ans=0;

     

for (int y=0; y<=n; y++){

      long long cur=powmod(y,n*(m-2));

      for (int x=y; x<=n; x++)

      if (2*x-y<=k)

      {

            long long tek=cnk[2*x-y];

            tek*=cnn[2*x-y][x-y], tek%=mod;

            tek*=cnn[x][x-y], tek%=mod;

            tek*=d[n][x], tek%=mod;

            tek*=d[n][x], tek%=mod;

            tek*=f[x], tek%=mod;

            tek*=f[x], tek%=mod;

            tek*=cur;

            ans+=tek;

            ans%=mod;

      }

}

cout<<ans<<endl;

Some contestants had problems with time limit, because of calculation of C(N,K). One can notice that we won’t need more than 2000 colors, which reduces the time significantly. Author’s solution worked less than 200ms with the time-limit of 5s.

Division 1, Problem E

Let the length of the maximal path be S. First, we’ll estimate the value of S without specifying the longest path itself.

Let’s color our board into a chess-coloring. Obviously, each two neighboring cells in the path will have different color. Keeping this in mind we can make some estimation on the value of S. For example, if there are 4 white cells and 5 black cells on the board and we know that both starting and ending cells are white, than the length of the path can’t be greater than 7, because white and black cells must alternate in the path. We can write a simple function which calculates the maximal value of S using only the fact described above. Here, n and m are the dimensions of the board, (sx, sy) is the starting cell and (fx, fy) is the ending cell.

int fnd_ans(int n,int m,int sx,int sy,int fx,int fy){

      int col1=((sx+sy+1)%2); //color of the start cell

      int col2=((fx+fy+1)%2); //color of the finish cell

 

      int cntb=(n*m+1)/2; //the number of black cells

      int cntw=(n*m)/2; //the number of white cells

 

      if (col1==1&&col2==1)

            return cntb*2-1;

      if (col1==1&&col2==0)

            return cntw*2;

      if (col1==0&&col2==1)

            return cntw*2;

      if (col1==0&&col2==0)

            return 2*cntw-1;

}

It appears that for the constraints mentioned in the statement, this theoretical bound for S is always achievable. All we need is to find the path of the length S. Author solution divides the board into 5 pieces and solves the problem for each piece separately.

 

Let’s divide the board into 5 parts as it was shown on the first picture. We’ll assume that the relative location of the starting and ending cells is the same as on the picture. In each part we’ll try to build a longest path which completely belongs to it. For the first part we’ll try to build a path from the upper-right corner to the upper-left corner. Similar rules will hold for all other parts (see the picture above for further clarification). Paths can be different for different boards, but they will have similar structure. One can notice that there are only two types of paths (with respect to rotations of the board): the one which starts at the upper-left corner and ends at the bottom-right corner and the one which starts at the upper-left corner and ends at the upper-right corner. Now we can write down an algorithm:

1) Divide the board into 5 parts.
2) Find the longest path in each of the parts.
3) Check if the total length is equal to S.
4) If the above is false, then rotate or reflect the board and continue to the step 1.

In order to find the longest path in a particular part, one can either consequently move through all rows of the part or through all its columns.

This solution gives correct answers for all 4 ≤ n, m ≤ 20. All possible cases of parity of each part are feasible within those constraints, which means that the solution will work for all boards, including ones with n > 20 or m > 20. The overall complexity of described algorithm is O(N*M).

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Seyaua, 8 years ago, In English,
Hi to everybody from sunny Petrozavodsk!

Today me and my brother sdya prepared a few interesting problems for you. Because of very tight schedule in Petrozavodsk training camp, that includes rafting and watching anime all night long, we didn't have time to write long problem statements. So enjoy unambiguous short statements and you are welcome to invent some legends for them on your own.

Good luck and have fun!

Contest is over! Congratulations to winners!

Division 1:
  1. dolphinigle
  2. ilyakor
  3. marek.cygan
Division 2:
  1. wuzhengkai
  2. jayi
  3. superpear
Editorial.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Seyaua, 9 years ago, translation, In English,

Here you can find the editorial for the past round. You can ask questions in the comments below. Special thank you goes to sdya who prepared editorials for problems D and E, which I used here.

Problem A

In this problem you should answer to 4 questions:

1)       Can we use type byte to store N?

2)       Can we use type short to store N?

3)       Can we use type int to store N?

4)       Can we use type long to store N?

We should check these conditions in the given order. If all these conditions are wrong, the answer is BigInteger.

The simplest way to check these conditions is to store numbers as strings and write a function to compare such strings. In Java you can use type BigInteger.

Problem B

Try to check all possibilities for creation artificial rain and calculate how many sections contain water. The maximal answer from all these possibilities is the answer for the problem. To calculate the answer for the given position we should check how many sections are to the left and to the right of the given section receive water. The complexity of this algorithm is O(N^2).

Problem C

Will be published later. 

Problem D

Consider N distinct prime numbers: p1, p2, …, pn.

Let A=p1*p2*…*pn. Then, easy to see, that the numbers A/p1, A/p2, …, A/pn can be considered as the answer.

The special case is when N=2. In this case there is no answer. We can see that this solution needs long arithmetic. If we choose first n prime numbers as p1, p2, …, pn then the maximal number in the answer for all N<=50 contains less than 100 digits.

 

Of course, there are other solutions. For example, if N=3 numbers 15, 10, 6 are the answer, and for N>3 numbers 15, 10, 6, 6*2, 6*3, …, 6*(N-2) are the answer.

Problem E

First of all we divide our problem into 2 parts: consider stations from which we can start if we are moving in the clockwise direction and stations from which we can start if we are moving in the counterclockwise direction.

Obviously, if we know the solution of one of these problems, we know the solution of another problem.

So, we may assume that stations are located in the counterclockwise order and we are moving in the counterclockwise direction.

Consider the following differences:

D1=a1-b1,

D2=(a1+a2)-(b1+b2),

D3=(a1+a2+a3)-(b1+b2+b3),

Dn=(a1+a2+…+an)-(b1+b2+…+bn);

Obviously if one of Di’s is less than a zero, then we cannot drive one round along the road. Let D = min(Di) – we will use it later.

Obviously, if D<0 then the first station cannot be the start station.

Now, we can check with complexity O(n) whether the first station can be used as the starting point. Next, we want to show how we can check this for the second station with complexity O(1).
To show this, consider:

E1=D1-(a1-b1),

E2=D2-(a1-b1),

En=Dn-(a1-b1).

Next, substitute Di in these equalities. We get the following:

E1=(a1-b1)-(a1-b1)=0=(a2+a3+…+an+a1)-(b2+b3+…+bn+b1) – (a1+…+an=b1+…+bn=X)

E2=(a1+a2)-(b1+b2)-(a1-b1)=a2-b2

E3=(a1+a2+a3)-(b1+b2+b3)-(a1-b1)=(a2+a3)-(b2+b3)

En=(a1+a2+…+an)-(b1+b2+…+bn)-(a1-b1)=(a2+…+an)-(b2+…+bn)

But it’s easy to see that number E1 has the same meaning for the second station as number D1 for the first one. So, we just have to check min(Ei)>=0. But Ei=Di-(a1-b1), so we have to check min(Di-(a1-b1))>=0. Now, we can see that if min(Di)=Dk, then min(Di-(a1-b1))=Dk-(a1-b1). So, if we know Dk, that we can check whether the second station can be the starting point with complexity O(1). Similarly, we can check this for the third, the fourth, …, the nth stations.

Now we should check the same things but assuming that the car is moving in the clockwise direction.

Read more »

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

By Seyaua, 9 years ago, translation, In English,
Hello!

I invite you all to take part in significant round! Today will be the first round for second division in Codeforces history, when it will be rated for blue coders!

This time the problems are written by me and sdya
We thank Artem Rakhov, Maria Belova and Dmitry Matov for help in preparing of this round.

Good luck for all!

UPD #1: Congrats to Kepnu4, who won the second division and to cerealguy, who won this round!

UPD #2: Link to editorial.

Read more »

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

By Seyaua, 9 years ago, In Russian,
Задача A. Определите цвет

Здесь все понятно. Достаточно рассмотреть несколько случаев. Первый — когда расстояние от 
точки до начала координат — целое число, тогда ответ black. В противном случае, пусть d 
- это расстояние от нашей точки до начала координат. Тогда будем работать с [d]. Теперь 
осталось два случая: 1) если наша точка лежит в 1-ой, или 3-ей четверти; 2) точка лежит во 
2-ой, либо 4-ой четверти. В случае 1) имеем, если [d] нечетно, то ответ white, иначе 
black; в случае 2) если [d] четно, то ответ white, иначе black. Подразумевается, что 
[d] — целая часть d.

Задача B. Перекрашивания

Первое, что надо заметить, так это то, что на i-ом шаге все перекрашенные клетки будут 
лежать в прямоугольнике с вершинами в клетках (i,i), (n-i,m-i) (если считать, что (1,1) - 
левая верхняя клетка, а (n,m) — правая нижняя). Тогда отсюда уже следует решение: нужно 
подсчитать количество клеток такого типа, что минимальное расстояние до стороны в точности 
равняется x. То есть для клетки (a,b) должно выполняться 
min(min(a, b), min(n - a + 1, m - b + 1)) = x.

Задача C. Берляндская площадь

Идейно эта задача не очень сложная, но было много хитрых случаев. Авторское решение предполагало следующую идею. Сначала заметим, что наше множество окружностей на плоскости может быть несвязным. Тут есть два случая, когда есть хотя бы одна точка пересечения окружностей и когда нет ни одной. Если их нет, то ответ N+M+1. Иначе, если есть хотя бы одна точка пересечения, то мы можем удалить некоторые окружности таким образом, чтобы оставшаяся фигура из окружностей была связной. Тогда для этой фигуры можно применить формулу Эйлера. Таким образом, нам здесь нужно посчитать количество точек пересечения и количество дуг-ребер. Нетрудно видеть, что каждая точка пересечения добавляет две дуги. Таким образом, мы можем найти количество частей, на которые разделилась плоскость без удаленных окружностей. Теперь достаточно заметить, что каждая удаленная окружность добавляет ровно 1 к ответу. Весь вопрос в том, чтобы посчитать, сколько точек пересечения. Это можно сделать за O(N+M), если считать для каждой окружности, точки пересечения, которые принадлежат ей. Для этого достаточно заметить, что все окружности, с которыми наша окружность пересекается будут иметь радиусы l, l+1, ..., r. Также, с некоторыми из этих окружностей наша окружность будет иметь не две точки пересечения а одну. Это необходимо учесть в решении. После этого остается лишь аккуратно реализовать эту идею. 

Задача D. Интересная последовательность

Здесь нужно было погенерировать разные последовательности, которые могут получаться и внимательно смотреть на полученные значения. Основное наблюдение, это то, что каждое из чисел, которые встречаются в последовательности имеет вид 12k + 12m, при этом это число может встречаться лишь на позиции (k + m + 1). Теперь, когда известен общий вид, можно по методу математической индукции доказать, что на x-ой позиции могут встречаться все числа вида 12k + 12m, такие что, k + m + 1 = x. После этого можно было реализовать простое в написании решение за O(N3), где N — длина входного числа. Для этого перебираем все x от 1 до 600 и проверяем, существуют ли такие k и m, что k + m + 1 = x и 12k + 12m = A. Но также есть и решение со сложностью O(N2).

Задача E. Таблица из чисел

Первое, что должно было броситься в глаза, это то, что клеток, изначально не пустых — совсем мало. Из ограничений следует, что всегда есть пустая строка либо пустой столбец. Без ограничений общности можем считать, что у нас есть пустая строка и она последняя. Тогда выберем какой-либо столбец (к примеру, последний) и зафиксируем его одновременно с пустой строкой. Тогда по оставшейся таблице размера (n - 1) × (m - 1) клетки в последнем столбце и в последней строке заполняются однозначно. Но есть одно замечание, в последнем столбце уже стоят какие-то числа. Тогда нам надо для каждой строки, кроме последней подсчитать, сколько существует вариантов этой строки, таких, что произведение чисел в этой строке равно -1. В авторском решении, эта часть считалась при помощи динамического программирования. После этого нужно перемножить полученные ответы для каждой строки. Тогда ответ на задачу — это полученное произведение, либо 0 — если сумма n + m нечетна.


Разбор задач был подготовлен мной и sdya

Read more »

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

By Seyaua, 9 years ago, translation, In English,
I invite you all to take part in the next Codeforces Round!

This time the problems are written by me and sdya. Some information about us: we both are second year students of The Faculty of Mechanics and Mathematics of Kharkiv National University named after V.N. Karazin, and we are twin brothers. We began studying programming in the 10th form, about 2.5 years ago. We do not have any significant achievements in programming competitions yet, but we hope we still have time to get some :)

We would like to express our gratitude to Artem Rakhov who helped us to arrange this contest, and to Maria Belova who has translated the problems statements into English.

We wish good luck to everyone and hope you will find the problems interesting!

UPD: The contest is over, congratulate tourist, who won this round.

Link to results.

Read more »

Announcement of Codeforces Beta Round #39
Announcement of Codeforces Beta Round #39
 
 
 
 
  • Vote: I like it
  • +66
  • Vote: I do not like it