dalex's blog

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

Link to announcement and discussion.

And here is the problem analysis.

A div 2: 378A - Playing with Dice

Make three counters: for wins of both players and for a draw. Iterate over all six ways how they can throw a dice. For each way determine who wins or there is a draw and increment the corresponding counter.

B div 2: 378B - Semifinals

You can think a bit and understand that you should consider only corner cases: k = 0 and . All other cases will be something between them.

If k = 0, we should choose n biggest elements from two sorted lists, one of the ways is to use two pointers method. And if , we just mark first people in each list.

A div 1 / C div 2: 377A - Maze

Start BFS or DFS from any free cell. As the maze is connected, this search will visit all s free cells. But we can stop the search when it visits s - k free cells. It's obvious that these s - k cells are connected to each other. Remaining k cells can be transformed into the walls.

Solutions which every move transform the cell which has the minimal number of neighbours passed pretests. However, it's wrong. Here is the counter-test:

....
.#..
..##
..##

Top-left cell has no more neighbours than any other cell but we cannot transform it into the wall.

B div 1 / D div 2: 377B - Preparing for the Contest

It's obvious that the time needed to fix all bugs is the monotonic function: if we can do it for some time, we can do it for greater time. So we can use binary search in these problem. We should learn how to check if some time t is enough.

At first sort all bugs by their complexity and all students by their skills. Let's consider the hardest bug. Who can fix it? It can be fixed by student whose skills is not less that this bug's complexity. Push all such students into the priority queue (sorted by students' price) and pop the cheapest student. As we check time t, this student must fix t hardest bugs (he definitely can do it). Save that information and go to the next bug which has not been fixed yet. Again push all students which can fix it to the priority queue and pop the cheapest one. And so on. If at some moment priority queue is empty, time t is not enough. If we spent too much 'money' — it's not enough as well. Otherwise we get the correct schedule.

C div 1 / E div 2: 377C - Captains Mode

There are some observations that do the problem very simple. The first one is that we always should pick the strongest hero. But we cannot say something similar about the bans — in different situations different bans are the best. But the most important observation is that we should consider only m strongest heroes. Indeed, in every game where only strongest heroes are picked, no hero except m strongest can be picked. That's why we don't need to ban them and therefore we don't need to consider them.

So now we have only 20 heroes. It means we can solve the problem using the dynamic programming with bitmasks: dpmask will be the difference between the teams' strengths when only those heroes are picked or banned whose bits are set to 1 in the mask. At every state we try to pick or ban every available hero and go to the other state. The simpliest way to implement it is the recursion with memoization. The answer will be stored in dp2m - 1.

Unfortunately, we couldn't estimate the real complexity of this problem (despite it has the simple solution, this solution is not so easy to think of — standard 1500 points for problem C would be better) and set too big TL (many solutions written in C++ whose complexity is m2·2m passed — we should have been set TL to 1 second or even to 0.75 seconds). So if you solved it in m2·2m, you may assume that you're just lucky and your correct verdict is Time Limit Exceeded.

Why it can be solved in m·2m? There is no point of missing a ban — if we ban the weakest hero, nothing will change since the weakest hero won't be picked.

Also this problem has weak pretests so you could hack solutions without bitmasks with almost any big random test.

D div 1: 377D - Developing Game

Let's note that every answer is characterized with two numbers L and R so that max{li} ≤ L, R ≤ min{ri}, and L ≤ vi ≤ R. If we know L and R, we can check every person and choose those who satisfies the conditions above.

Let's imagine a plane with the coordinate axes: one of the axes will be L, and the other will be R. If the point (L, R) on this plane is the optimal answer, people included in this answer for sure satisfy the conditions li ≤ L ≤ vi and vi ≤ R ≤ ri. These conditions specify the rectangle on the plane. Since we should find the maximum number of people, we should find such point (L, R) that it is inside the maximum number of the specified rectangles.

Now it's the standard problem that can be solved using the scanline through one axis and the segment tree built on the other axis. The hardest part is to reduce the original problem to it.

E div 1: 377E - Cookie Clicker

First of all, throw away the buildings which cannot be used in any optimal answer: for each vi remain only one building that has speed equal to vi and minimal ci. Also throw away all buildings whose speed is less than the speed of the fastest building which has ci = 0.

It's fairly obvious that at any time we should use the fastest building. And if some building is used in the optimal answer, it should be bought and used immediately when we have enough money (I will use the word 'money' instead of 'cookies').

Let's imagine the plane (x, y) where x axis stands for the time and y axis stands for the money. We will maintain the graph of the function y = f(x) — 'maximal number of money that can be obtained at the time x' and process the buildings one by one, changing the graph. This function is the union of the line segments with the slopes equal to vi, and each of these line segments is active on a certain segment [xli, xri] of the axis x.

For example, at the beginning the graph is just the line y = v1x, where v1 is the speed of building that can be bought for 0 units of money. Let the next building's price is c2. Find the minimal point x02 where value of our function is greater or equal to y = f(x02) ≥ c2 and buy this building at the moment x02. Then we should make the line y = y02 + v2x where y02 = f(x02) - c2 is the amount of money remaining after the purchase. Now we have two lines. Till some moment the first line is better (not till x02, maybe later), but as v2 > v1 there exists a moment of time (it's ceil(x12) where x12 is the x-coordinate of the lines' intersection) when the second line becomes better. Now we know the segments where a particular line is better than the others.

Continue add all buildings to the graph this way. Line segments should be stored in stack, as in all problems with convex hull, and every step remove unnecessary line segments from the stack (these are the lines those position in the stack is after the line which has an intersection with the currently added line). After we process all buildings, we use our graph to find the minimal time when we have S untis of money.

If we also should say which building we must use, we can store for any line segment its 'parent' — the line segment which was active when the current one was bought. With such parent array it's not hard to restore the sequence of buildings in the answer. We removed this part from the problem to make it a bit easier.

Read more »

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

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

Hi all!

Authors of today's round are craus and dalex. We just couldn't miss the round with such a beautiful number, so at 19.30 MSK you will solve problems which were invented by Pavel and prepared by me.

We thank Gerald and Delinur for their help in contest preparation and MikeMirzayanov for creating Codeforces.

Scoring system and score distribution will be published when the round starts. Anyway this information makes no sense unless the round begins.

We wish you accepted solutions and successful hacks!

UPD. Contest is over, congratulations to the winners!

Div. 1:
1. Petr
2. tourist
3. Egor

Div. 2:
1. k3e18
2. cornell2011
3. Daniyar_7

UPD. 2 Problem analysis is published.

Read more »

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

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

As the admins don't want to fix the bug with two different Codeforces sites (1 2), I ask you to paste relative links.

It can be done this way:

If you click on such link, you won't be logged out. Thanks.

Read more »

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

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

On Satudray, Oct 12, at 12:00 PM another 5-hour contest in Codeforces Gym will be held. It's the second time we prepare qualification contest for Samara SAU teams to determine who deserves to participate in Southern Subregional Contest in Saratov (the previous such contest can be found here).

Maybe you know that team Teddy Bears is no longer able to take part in ACM ICPC. It resulted in renaming and renumbering the teams in the university. You have an unique opportunity to defeat new first team of Samara SAU and show them at what place they can finish in Subregional Contest. Don't miss this chance!

Contest is over. Now you can just solve the problems or take part in the virtual contest.

Many thanks to Xellos who made a tutorial.

Read more »

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

By dalex, 7 years ago, In English,

I just leave the test generator here: [Codeforces] [Ideone] [Pastebin]

UPD. The similar blog entry about Java 6: http://codeforces.com/blog/entry/2296 (it's only in Russian, but you can look over source code)

UPD 2. The link was updated. Generator's speed was increased a bit. However, it seems that something works wrong and for some array sizes it generates easy-to-sort array. Always check if sort really works slow.

UPD 3. Links were updated again. It works almost just as planned now. There is still one issue that I don't know how to fix, but in general it works and can be used.

Read more »

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

By dalex, 7 years ago, translation, In English,

Hi all!

Today, June 12, when Russia celebrates Day of itself, Euro 2012 second round starts and I_love_natalia has a birthday, we present you Codeforces Round #124.

Contest was prepared by team Samara SAU Teddy Bears (craus, dalex, Hohol) and I_love_natalia. Also thanks to Alex_KPR and Codeforces team (Gerald, Delinur, MikeMirzayanov). We think that contest is very easy, and your task will be prove of refute this assertion :)

Scoring system is dynamic (Learn more about dynamic problem scoring).
Authors think that problems are sorted by difficulty in non-descending order.

Accepted solutions and successful hacks to you!

UPD. Contest is over, congratulations to the winners!

Div-1 (full results):

  1. tourist — the only one who solved all problems!
  2. RAVEman
  3. aropan

Div-2 (full results):

  1. bmerry
  2. littlefriend
  3. gstsclq

UPD 2. Tutorial is available.

Read more »

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

By dalex, 8 years ago, In English,

One minute remaining! Don't forget to participate! :)

http://code.google.com/codejam/

UPD: Results: http://code.google.com/codejam/contest/1645485/scoreboard?c=1645485#

First 1000 contestants pass to the next round.

Read more »

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

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

Hello.

I and I_love_natalia just discovered a strange problem which came to me when I generated antiquicksort-test. I even got an unsuccessfull hack on today's round because of it. It was surprising to me that my victim's program had worked so fast on the antiquicksort test. But at the end of the contest I changed the size of array in the generator from 100000 to 99987, and the hack became successful!

I don't know why it happens. This is the test case:

  1. Run test generator from http://pastebin.com/99RwHR6w in Codeforces Custom Test interface.

  2. Server will output you something like Sorting ended in 1953ms

  3. Add two empty lines to the end of the code and run it again.

  4. Result is: Sorting ended in 0ms.

You can add and delete spaces and empty lines from random places of the code and the results will be different: array can be sorted in zero time or in about 2 seconds.

I uploaded a video with this issue, you can download and watch it: link (be careful, being unzipped, it is about 600 MB)

So what is it? A bug of Java virtual machine? Or Codeforces server tries to protect contestants from antiquicksort?

UPDATE: As it turned out, some Codeforces servers have Java 7. Java 7 has other implementation of sort, so that's why some runs on antiquicksort tests are fast. It is not good because I submit my solution under Java 6 but it can run under Java 7 instead. Please note it till admins fix that issue.

Read more »

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

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

I'd like to offer you two chess problems.
In both problems there is checkmate in 1, white to play.

If you think that any fool can solve checkmate in 1, these positions are for you!

   

Please post your answers under spoilers!

Read more »

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

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

At first I tell about the contest at all.

My problems in the contest were A-div2,  B-div2,  C-div2/A-div1,  E-div2/C-div1,  D-div1. I wanted to make only div.2 round, but then we decided to give you seven problems at both divisions. MikeMirzayanov prepared the problem about milk pouring and anonymous gave E-div1 problem. Also RAD gave some advices to complicate problems Azembler and Flags a bit.

And now let's start analysis.


Problem A (div.2) - Restoring Password

Password was very easy to restore. You should just iterate over groups of 10 characters in the first string and over all codes. Then, if some number's code is equal to the group - print that number.

Here's the example: http://pastebin.com/hMV0NcjN


Problem B (div.2) - Friends

Let's construct the graph where vertices correspond to the people and edges correspond to the relationships. Then paint each edge in this way: edge will be red if the men connected by it are friends and black otherwise. Now let's think what is "three pairwise acquainted people" and "three pairwise unacquainted people". We see that they are cycles of only red and only black vertices correspondingly, and the length of these cycles is 3.

Now we know the solution: write 3 "for" cycles, one cycle for one vertex, and check if the edges between these vertices are only red or only black.

Here's the solution: http://pastebin.com/gswaxGmM

Another way to solve it is to notice the answer is FAIL if and only if graph has exactly 5 edges and they all together form a cycle with a length 5. It's very funny solution, I think. Here's the code: http://pastebin.com/09T0ixrJ


Problem A (div.1) / C (div.2) - Frames

The problem is easy, but there were many tricky cases - and contestants show it successful :) I added almost all these cases to the pretests because I didn't want to arrange Beta Round 60.

So let's solve the problem. At first notice that the answer is not greater than 3 because we always can do three selections (maybe, some of them are empty): with first selection we select end of the first row, with second one - begin of the last row, and with last one - all remaining folders (they form the rectangle).

The best way is to find all cases with answer 1 and 2. Try to do it.

If the answer is 1, we can select all folders from a to b with one selection. There must be nothing hard to detect these cases:

  • first and last folders are in the same row (21 5 7 9);
  • first folder is in the first column, and the last folder - in the last column (21 5 1 15), сase m = 1 is included here;
  • first folder is in the first column, and the last folder is n (21 5 6 21). Case when we must select all folders is included here. I was very surprised when I saw that many contestants forgot about it.

And these are the cases with answer 2:

  • first and last folders are in the adjacent rows (21 5 8 14);
  • first folder is in the first column (21 5 6 13);
  • last folder is in the last column (21 5 4 15);
  • last folder is n (21 5 4 21);
  • and another tricky case: if the column where first folder is located is just at right from the column where the last column is located (21 5 3 12).

If no one of these conditions is true, answer is 3.

Here's the solution: http://pastebin.com/8QRytzzF


Problem B (div.1) / D (div.2) - End of Exams

Greedy algorithm solves this problem. We should consecutively try to pour milk from each bottle into each available cup and in maximal possible amount.

Also we always need to know, how much milk is in each bottle and each cup, for each cup - bottles from which we have poured milk, and for each bottle - cups into which we have poured milk.

Writing it is not hard. But where is one special moment - if we compare real numbers, we must use EPS, or we can get WA on test 12 (50 1000 49). Some programs write NO on this test while answer is YES, because of wrong comparing of real numbers.

It must be said that answer can be calculated in integers: just set the volume of milk in each bottle mn. And only when we will print the answer, we divide each volume by mn and multiply by w. All three jury solutions didn't think up this :)

Here's the solution: http://pastebin.com/HG5Nrxne (be careful, it's not as beautiful as previous ones)


Problem C (div.1) / E (div.2) - Azembler

I don't know why so few coders have solved it. Small limitations for n and big time limit - 5 seconds - hint that it's backtracking. Also, no need to be a soothsayer to understand that maximal answer is about 5.

Solving it is clear. You should keep all current registers at the vector and call some function that goes over all current registers and calculate new values, then calls itself recursively. In that process we can also save the program itself.

To avoid TLE you should not make recursive calls if the deep of recursion is larger than current answer, should not go to the states where you get a number larger than n or less than current biggest number. And if you reach exactly n, you should update answer and copy the program to the safe place.

There are some hacks to speed up this approach: for example, iterate over numbers in descending order (it works faster), but 5 seconds is such TLE that you can solve it any way. Or you can launch backtracking for the specific answer (increasing it) while the program won't be found (I don't know how this method is named in English). Also, some contestants have solved it using BFS.

Here are two solutions: standard backtracking (http://pastebin.com/Z6ZF36st) and backtracking for the specific answer (http://pastebin.com/viiYF9CB).


Problem D (div.1) - Flags

I think my solution is not optimal, it's too long. Many solutions submitted during the contest are shorter. But I tell you about my solution.

At first I solve the problem for the number of stripes equals N (or L = R).

Let is the number of flags with exactly N stripes where symmetrical flags are not identical. Try to get the answer using this designation.

At first sight it seems that answer is . But it's not true for the palindromes. For example, for non-palindromes WBWB and BWBW we should count only one of them, but for the palindromes, such as WBW, it leads to mistake, because each palindrome is symmetrical to itself.

So for the flags with even number of stripes formula is correct, because there are not palindromes among them. And if N is odd, the correct formula is , where is the number of palindromes with N stripes. Each palindrome is definited by its first stripes, and we can write that .

Now we can give an answer if we know how to calculate number of flags where symmetrical flags are not equal. Notice that if we know two last stripes of the flag, we can definitely say if we can add another stripe to its end.

Let's use dynamic programming. As a state we can take a vector with a length 8 where each its component keeps a number of flags with N stripes and definite two last colors (exactly 8 options). And is total number of flags with N stripes.

As start state we can take vector which consists of ones (because there are 8 flags with a length 2, one flag for one possible combination of two colors). And how to calculate ?

It turns out that there is some matrix A that . Its elements can be found even using pen and paper: for example, let's we have a combination of two last stripes WB. Then it's possible to add white or yellow stripe to the end, and the last stripes will be BW and BY correspondingly. It means that we can write 1 to the matrix where the row are BW or BY and the column is WB.

We're about the finish. It's obvious that . Power of matrix can be calculated with a logarithmic time - that's because our problem is solved. And don't forget if N = 1 then answer is 4 and there's no need to do these calculations.

But it was only problem where L = R. Let's find a solution for the segment .

I know two ways to do it. First way is to add a new component to the vector and new row and column to the matrix. This new component should keep the total number on the segment (if L = 1, we can write "if" somewhere at the beginning of the program). And the matrix A should be changed a bit: try to do it by yourself.

I like the second way. As we did it earlier, we will find a number of flags where symmetrical ones are different, but on the segment . It is equal to . Let's learn how to calculate the sum E + A + ... + AN quickly.

Let b is such maximal power of 2 that 2b - 1 ≤ N. We can write .

And apply some math magic to the first part of the previous formula: . And the expression in the brackets at the second part of that formula is... I think you've already understood it :)

We forgot about the palindromes, but it's very easy to calculate their number. Let's suppose that L and R are odd (if they are even, we can add one to L and substract one from R). Then .

That's all. Don't forget to apply "mod" operation after each operation and examine border cases carefully. And here's the solution: http://pastebin.com/wHu1tPgd (yes, "matrix" and "vector" type definitions are strange - I've totally forgotten how to write in Pascal)


Problem E (div.1) - Lostborn

This problem can be solved using inclusion-exclusion principle. If is the answer, then the following formula works: . But if you write only this recursive function, you get TLE. Many contestants got TLE and were hacked because they didn't run maximal test on their computers.

And the others who sensed that something was wrong memorized the answers for small n and all ai. For example, you can see solution by rng_58 who won the contest, or this solution: http://pastebin.com/4kcfJdAi.

anonymous, the author of this problem, wrote his thoughts about it there: http://codeforces.ru/blog/entry/2216 (but now there's only russian version). His solution works even if n = 1015 and it can be viewed here: http://codeforces.ru/problemset/status/93/E?order=BY_CONSUMED_TIME_ASC. It seems that any solution submitted during the contest would get TLE if n = 1015.


Sorry for my English :)

Read more »

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

By dalex, 8 years ago, In English,

Hi all!

My name is Alexey Dergunov, and I'm glad to present you the first "violet" Codeforces round. I hope the problems will not seem so "violet" to you :)

Many thanks to following people who helped me a lot with contest preparation:

Good luck!

UPD. Contest is over, and we know the winners!

Division 1:
Division 2:
Congratulations!

UPD 2. Analysis: http://codeforces.ru/blog/entry/2208 (English version is not full yet...)

Read more »

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