AlexDmitriev's blog

By AlexDmitriev, 4 months ago, In English,

It seems something went wrong with updates to polygon certificate and it's now expired

Expired: Saturday, 22 July 2017 at 05:55:00 Moscow

@MikeMirzayanov

Read more »

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

By AlexDmitriev, history, 5 months ago, In English,

The next round is at 14:00 UTC today

Top20 advances to the on-site round in Dublin

Read more »

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

By AlexDmitriev, history, 5 months ago, In English,

Round starts at 14:00 UTC today and 25 participants will advance to final round in Dublin.

Read more »

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

By AlexDmitriev, history, 10 months ago, In English,

Starts in less than 3 hours

Top 200 from round 2 are allowed to participate and top 25 (aged 18+) will advance to onsite finals

Let's discuss problems here.

Read more »

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

By AlexDmitriev, history, 12 months ago, In English,

Tomorrow is GP of Dolgoprudny which is prepared by my colleagues and me.

Hope, you'll like the problems which we can discuss here after the contest.

Also, we've prepared mini-tutorial which I'll post here after the contest too.

Good luck!

Read more »

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

By AlexDmitriev, history, 16 months ago, In English,

Tomorrow, 16:00 UTC (well, at least if calculated correctly)

UPD: you have 10 more minutes to register

Read more »

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

By AlexDmitriev, history, 18 months ago, In English,

Today, at 6 PM MSK (3 PM UTC)

Read more »

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

By AlexDmitriev, history, 19 months ago, In Russian,

К чему бы это?

Read more »

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

By AlexDmitriev, history, 19 months ago, In Russian,

А именно ссылка на получение рейтингов: http://codeforces.com/api/user.ratedList?lang=en {"status":"FAILED","comment":"Internal Server Error"}

Read more »

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

By AlexDmitriev, 22 months ago, translation, In English,

624A - Save Luke

Width of free space is decreasing by v1 + v2 per second. It means that it'll decrease from L to d in seconds. The moment when width gets a value of d is the last when Luke is alive so t is the answer.

624B - Making a String

Sort array in descending order.

Iterate over all letters, First letter is added c1 = a1 times, each other letter is added ci = min(ai, ci - 1). Don't forget that if some letter is not added at all, then all next letters are not added too.

623A - Graph and String Note that all vertices "b" are connected with all other vertices in the graph. Find all such vertices and mark them as "b". Now we need to find any unlabeled vertex V, mark it with "a" character. Unlabeled vertices connected with V should be also labeled as "a". All other vertices we can label as "c"

Finally we need to check graph validity. Check that all vertices "a" are only connected with each other and "b" vertices. After that we need to perform a similar check for "c" vertices.

623B - Array GCD

At least one of ends (a1 or an) is changed by at most 1. It means that if gcd > 1 then it divides on of prime divisors of either a1 - 1, a1, a1 + 1, an - 1, an or an + 1. We will iterate over these primes.

Suppose prime p is fixed. For each number we know that it's either divisible by p or we can pay b to fix it or it should be in the subarray to change for a

We can use dynamic programming dp[number of numbers considered][subarray to change not started/started/finished] = minimal cost

Complexity is O(Nd) = O(Nlog(max(ai)), where d is the number of primes to check.

623C - Electric Charges

First of all consider cases where all points are projected to the same axis. (In that case answer is difference between maximum and minimum of this coordinate).

Now consider leftmost and rightmost points among projected to x axis. Let xL and xR are their x-coordinates. Notice that points with x-coordinate xL ≤ x ≤ xR may also be projected to x-axis and that will not increase the diameter. So, if we sort all points by x-coordinate, we may suppose that points projected to x-axis form a continuous subarray.

We will use a binary search. Now we will need to check if it's possible to project point in a such way that diameter is <= M.

Let's fix the most distant by x-coordinate point from 0 that is projected to x-axis. It may be to the left or to the right of 0. This cases are symmetrical and we will consider only the former one. Let xL < 0 be its coordinate. Notice that one may project all points such that 0 ≤ x - xL ≤ M and |x| ≤ |xL| to the x axis (and it'll not affect the diameter) and we have to project other points to y-axis. Among all other points we should find the maximum and minimum by y coordinate. Answer is "yes (diam ≤ M)" if ymax - ymin <  = M and distance from (xL, 0) to both (0, ymax) and (0, ymin) is not greater than M.

Let's precalculate maximums and minimums of y coordinates on each prefix and suffix of original (sorted) points array. Now iterate over left border of subarray of points projected to x-axis and find the right border using binary search or maintain it using two-pointers technique.

So we've got one check in O(M) or and entire solution in or

623D - Birthday

Let's denote qi = 1 - pi.

Main idea: first of all guess each friend once, then maximize probability to end game on current step. Let's simulate first 300000 steps, and calculate . , where ki — how many times we called i-th friend ().

Expectation with some precision equals . So it is enough to prove that:

1) Greedy strategy gives maximum values for all Pr(t).

2) On 300000 step precision error will be less than 10 - 6.

Proof:

1) Suppose, that for some t there exists set li (), not equal to set produced by greedy algorithm ki, gives the maximum value of Pr(t). Let's take some ka < la and kb > lb, it is easy to prove tgat if we change lb to lb + 1, la to la - 1, then new set of li gives bigger value of Pr(t), contradiction.

2) qi ≤ 0.99. Let's take set , it gives probability of end of the game not less than optimal. Then Pr(t) ≥ (1 - 0.99t / 100)100 ≥ 1 - 100·0.99t / 100. Precision error does not exceed . It could be estimated as sum of geometric progression. If N ≥ 300000 precision error doesn't exceed 10 - 7.

623E - Transforming Sequence

First observation is that if the sequence of prefix xors is strictly increasing, than on each step ai has at least one new bit comparing to the previous elements. So, since there are overall k bits, the length of the sequence can't be more than k. So, if n > k, the answer is 0.

Let's firstly solve the task with O(k3) complexity. We calculate dp[n][k] — the number of sequences of length n such that a1|a2|... |an has k bits. The transition is to add a number with l new bits, and choose those k bits which are already in the prefix xor arbitrarily. So, dp[n + 1][k + l] is increased by dp[n][k]·2k·Ck + ll. The last binomial coefficient complies with the choice these very l bits from k + l which will be present in a1|a2|... |an + 1.

Note now that the transition doesn't depend on n, so let's try to use the idea of the binary exponentiation. Suppose we want to merge two dynamics dp1[k], dp2[k], where k is the number of bits present in a1|a2|... |aleft and b1|... |bright correspondingly. Now we want to obtain dp[k] for arrays of size left + right. The formula is:

Here l corresponds to the bits present in the xor of the left part, and for each number of the right part we can choose these l bits arbitrarily. Rewrite the formula in the following way:

So, we can compute dp[k] for all k having multiplied two polynomials and . We can obtain the coefficients of the first polynomial from the coefficients of the second in . So, we can compute this dynamic programming for all lengths — powers of two, in , using the fast Fourier transform. In fact, it is more convenient to compute using the same equation. After that, we can use the same merge strategy to compute the answer for the given n, using dynamics for the powers of two. Overall complexity is .

We decided to ask the answer modulo 109 + 7 to not let the participants easily guess that these problem requires FFT :) So, in order to get accepted you had to implement one of the methods to deal with the large modulo in polynomial multiplication using FFT. Another approach was to apply Karatsuba algorithm, our realisation timed out on our tests, but TooDifficuIt somehow made it pass :)

Read more »

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

By AlexDmitriev, history, 22 months ago, translation, In English,

Round 1 starts in 10 hours

Note, that rules were changed:
To advance to Round 2 you need to score 30 points or more.

Read more »

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

By AlexDmitriev, history, 2 years ago, In Russian,

К сожалению, довольно часто авторы контестов не знают или не помнят, о том, что запись в блоге(разбор) можно прикрепить к соревнованию.

Например, к 315 раунду анонс добавлял я, у 313-314 тоже сейчас нет прикрепленного разбора. Это значит, что разбор придется искать дополнительно(в Гугле, например)

Было бы удобно, если бы это происходило автоматически, например, если пост называется Codeforces Round xxx [Editorial|tutorial], то предложить автору прикрепить его к контесту.

Read more »

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

By AlexDmitriev, 3 years ago, In English,

You need to get 20 points in order to advance to Round 1.

Post about entire GCJ

Read more »

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

By AlexDmitriev, 3 years ago, translation, In English,

Registration is started!

Schedule:

  1. Qualification April 10 23:00 UTC
    Discussion
  2. Round 1A April 18 01:00 UTC (anyone who get fixed number of points in qual).
    Discussion.
  3. Round 1B May 2 16:00 UTC (anyone who was allowed to participate in 1A, but didn't advance to round 2 yet)
    Discussion
  4. Round 1C May 10 09:00 (anyone who was allowed to participate in 1A, but didn't advance to round 2 yet)
  5. Round 2 May 30 14:00 UTC (Top 1000 from each 1X round)
    Discussion
  6. Round 3 June 13 14:00 UTC (Top 500 from Round 2)

T-shirts are for top 1000 in Round 2.

Distributed Code Jam is also introduced

Read more »

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

By AlexDmitriev, 3 years ago, In English,

Contest is over.

How to solve D ?

How to solve F correctly?

Read more »

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

By AlexDmitriev, 3 years ago, translation, In English,

509A - Maximum in Table

In this problem one needed to implement what was written in the statement: create matrix (two-dimensional array) using given rules and find maximal value in the table.

It is also possible to see that maximal element is always in bottom-right corner.

Easier solution with recursion also was enough to get AC:

def elem(row, col):
    if row == 1 or col == 1:
        return 1
    return elem(row - 1, col) + elem(row, col - 1)

One may see the Pascal's triangle in the given matrix and understand that answer is equal to

Prepared by: AlexDmitriev
Author of editorial: AlexDmitriev

509B - Painting Pebbles

Suppose there are two piles with number of pebbles differed by more than k, then there is no solution:

Now let M = max ai ≤ min ai + k = m + k.
There's a way to construct correct coloring:

  • Chose m peebles from each pile and assign first color to them.
  • In each pile assign different colors to all other pebbles (you may use first color once more) (It's possible bacause there are no more than k uncolored pebbles.

Now there are m or m + 1 pebbles of first color and 0 or 1 pebbles of any other color in each pile.

Prepared by: Kostroma
Author of editorial: AlexDmitriev

509C - Sums of Digits

The algorithm is greedy: first, take the minimal number with sum of digits a1 — call it b1. Then, on the i-th step take bi as the minimal number with sum of digits ai, which is more than bi - 1.

It can be easily proven that this algorithm gives an optimal answer. But how to solve the subproblem: given x and y, find the minimal number with sum of digits x, which is more than y?

We use a standard approach: iterate through the digits of y from right to left, trying to increase the current digit and somehow change the digits to the right in order to reach the sum of digits equal to x. Note that if we are considering the (k + 1)-th digit from the right and increase it, we can make the sum of k least significant digits to be any number between 0 and 9k. When we find such position, that increasing a digit in it and changing the least significant digits gives us a number with sum of digits x, we stop the process and obtain the answer. Note that if k least significant digits should have sum m (where 0 ≤ m ≤ 9k), we should obtain the answer greedily, going from the right to the left and putting to the position the largest digit we can.

Let us bound the maximal length of the answer, i.e. of bn. If some bi has at least 40 digits, than we take the minimal k such that 10k ≥ bi. Than between 10k and 10k + 1 there exist numbers with any sum of digits between 1 and 9k. If k ≥ 40, than 9k ≥ 300, which is the upper bound of all bi. So, in the constraints of the problem, bi + 1 will be less than 10k + 1. Than, similarly, bi + 2 < 10k + 2 and so on. So, the length of the answer increases by no more than one after reaching the length of 40. Consequently, the maximal length of the answer can't be more than 340.

The complexity of solution is O(n·maxLen). Since n ≤ 300, maxLen ≤ 340, the solution runs much faster the time limit.

Prepared by: Endagorion
Author of editorial: Kostroma

509D - Restoring Numbers

First we note that if the sequences ai and bi are a valid solution, then so are the sequences ai - P and bi + P for any integer P. This means that we can consider a1 to be equal to 0 which allows us to recover the sequence bi by simply taking the first row of the matrix. Knowing bi we can also recover ai (for example by subtracting b1 from the first column of the matrix) At this stage we allow ai and bi to contain negative numbers, which can be later fixed by adding K a sufficient amount of times. Now we consider the “error” matrix e: .

If e consists entirely of 0s, then we’ve found our solution by taking a sufficiently large K. That is: K > maxi, j(wi, j).

Otherwise, we note that ei, j = 0(modK) which implies that K is a divisor of g = gcdi, j(ei, j). The greatest such number is g itself, so all that remains is to check if g is strictly greater than all the elements of the matrix w. If that is the case, then we’ve found our solution by setting K = g. Otherwise, there’s no solution.

Prepared by: Kostroma, AlexDmitriev
Author of editorial: AlexDmitriev

509E - Pretty Song

We first calculate the prefix sums of vowel(si) which allows to calculate the sum of vowel(si) on any substring in O(1) time.

For all m from 1 to , we will calculate the sum of simple pretinesses of all substrings of that length, let’s call it SPm. For that purpose, let’s calculate the number of times the i-th character of the string s is included in this sum.

For m = 1 and m = |s|, every character is included exactly 1 time. For m = 2 and m = |s| - 1, the first and the last character are included 1 time and all other characters are included 2 times. For m = 3 and m = |s| - 2 the first and the last character are included 1 time, the second and the pre-last character are included 2 times and all others are included 3 times, and so on.

In general, the i-th character is included min(m, |s| - m + 1, i, |s| — i + 1) times. Note that when moving from substrings of length m to substrings of length m + 1, there are 2 ways in which the sum SP can change:

  1. If m > |s| - m + 1, then SP is decreased by the number of vowel occurrences in the substring from |s| - m + 1 to m.
  2. Otherwise, SP is increased by the number of vowel occurrences in the substring from m to |s| - m + 1.

This way we can easily recalculate SPm + 1 using SPm by adding (subtracting) the number of vowel occurrences on a substring (which is done in O(1) time). The complexity of this solution is O(N).

Prepared by: zemen
Author of editorial: zemen

509F - Progress Monitoring

Consider a tree with n vertices rooted at vertex 1 and let b be the pseudocode’s (DFS) resulting sequence. Then b[lv..lv + sizev - 1], represents vertex v’s subtree, where lv is the index of v in b and sizev is the size of $v$’s subtree.

Let’s solve the problem using this fact and Dynamic Programming. Let e[l, r] be the number of trees consisting of vertices a[l], a[l + 1], …, a[r] such that running DFS starting from a[l] will result in a sequence with vertices in the same order as their order in a.

The base case is when l = r and e[l, r] = 1. Otherwise, where the sum is taken over all partitions of the segment [l + 1, r], that is, over all k;pos1, ..., posk + 1, such that l + 1 = pos1 < pos2 < ... < posk + 1 = r, 1 ≤ k ≤ r - l, a[pos1] < a[pos2] < ... < a[posk]. Each such partition represents a different way to distribute the vertices among a[l]’s children’s subtrees. A solution using this formula for calculating e[l, r] will have an exponential running time.

The final idea is to introduce d[l, r]:  = e[l - 1, r], 2 ≤ l ≤ r ≤ n. It follows that: d[l, r] = ([statement] is equal to 1 if the statement is true, 0 otherwise) and e[l, r] = d[l + 1, r]. This way d[l, r] and e[l, r] can be calculated in linear time for any segment [l, r]. The answer to the problem is e[1, n]. Overall complexity is O(n3).

Prepared by: DPR-pavlin
Author of editorial: DPR-pavlin

Read more »

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

By AlexDmitriev, 3 years ago, In English,

Today at 19:00 MSK

We can discuss problems here after the contest

Read more »

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

By AlexDmitriev, 3 years ago, In Russian,

Было бы круто, если бы была подсветка синатксиса во взломах(такая же как при просмотре своих посылок).

Сегодня, например, я получил один из своих неудачных взломов из-за того, что не заметил, что у человека кусок кода закомментирован. Хорошая подсветка решила бы это.

Read more »

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

By AlexDmitriev, 3 years ago, In Russian,

Не знаю, кого пинать напрямую, но мне как-то передавали слова одного из членов жюри про мой комментарий(и): "Кто такой Алексей Дмитриев и какого черта он это пишет?", так что я надеюсь и это снова прочитают.

Нет, я понимаю задержки на старте, к этому все привыкли. Но почему ссылку на пробный тур уже после его запланированного начала можно узнать только через Снарка? К слову, к тому времени этот самый пробный тур еще не начался. В чем вообще проблема включить пробный тур да хоть за неделю до старта и забыть про него? Все равно там задачи те же, что были в прошлом году. Ссылку на основной тур нам вообще не сказали(!) (Благо наша команда догадалась еще на пробном туре перебрать id контестов в обе стороны на единицу).

Гвоздь программы — клар "В Москве можно печатать". Да какого черта?! Ладно, на секунду забудем о настройке печати с начала контеста, но почему нельзя включить эту функциональность одновременно? Ладно, благодаря тому, что Физтех (ровно как и некоторые другие вузы, включая МГУ) всегда имеет в топе достаточное кол-во команд, не меньшее своей квоты, никакого влияния на выход в ПФ это не поимело и весь Физтех был в равных условиях. Однако, когда в прошлом году встал вопрос о включении standings на больших мониторах, которые висят у нас в кабинетах, где проводится ЧФ, все окончилось на том, что "участники из МГУ не имеют такой возможности, поэтому — нет".

Кстати, о том, что печать заработало можно было бы послать клар/объявить в аудиториях. Мы случайно заметили, что кто-то печатает.

Кстати, почему нельзя настроить печать и на пробном туре? Собственно, пробный тур вроде не для того сделан, чтобы задачки порешать, а как раз протестировать все и участникам, и жюри. Может быть вам жалко по листику на каждую команду? (Тогда рекомендую не делать задачи типа K, целые 3 листа с команды экономии).

К слову о качестве печати: у нас, например, первые несколько символов в каждой строке не печатались. Если бы это можно было проверить во время пробника, то и пофиксить бы, наверно, можно было, а заниматься кларописанием во время тура — неудобно.

По поводу печати на половинках: там уже научились переносить длинные строки? Помнится у нас раньше были с этим проблемы, нынче вроде не столкнулись (печатали не много).

А вот за проблемсет спасибо авторам. Все, кроме задачи G, было хорошо понятно, а сами задачи были довольно интересными.

Read more »

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

By AlexDmitriev, 3 years ago, In English,

Hi, Codeforces.

Changelog:

  • 0.12
    • Support CLion 2017.1: fix detecting pragma once
  • 0.11
    • Support CLion 2016.3.2: return back to changing only settings for testrunner
  • 0.10
    • Support CLion 2016.3
      • Switch configuration now changes global setting AND setting for testrunner
      • Rewrite task saving so that random exceptions are not thrown
  • 0.9.2
    • Support AtCoder and CodeAcademy parsers
  • 0.9
    • Now includes inlined when they point to inside project (not when they are in quotes as before)

JHelper is plugin for writing contests in C++. You may inline code from your own prewritten library so that you can submit only used code. Besides, it allows to test on tests you've added. it's planned that you'll be able to parse a problem/contest and have all samples tests automatically added.

It's available for CLion

Plugin is completely free. IDE price is 89$/year, but it's free for students, have 30-days free trial and often you can use EAP(smth like beta)-versions for free.

You may download the plugin using JetBrains plugin repository or manually from their site

Some explanations how to use that on wiki. Fell free to ask what is unclear.

Please post bugs and feature requests here or in bug tracker.

Your contributions are also welcome. Possible ways to contribute:

  • Post bugs or feature requests
  • Make wiki more understandable
  • Implement something and create pull request.

It's still possible to make it multilingual (I mean add another programming languages). I am open to discuss that.

Thanks Egor for idea with his Chelper and abra for some code review.

Source code | known bugs | bugtacker | instructions

Read more »

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

By AlexDmitriev, 4 years ago, In English,

Round 1 will last 24 hours and start December 7, 2013 at 10:00 AM PT.

The top 500 people will advance to the Round 2. In addition, anyone that scores the same number of points as the person in 500th place will also advance to Round 2

Read more »

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

By AlexDmitriev, 4 years ago, translation, In English,

The Qualification Round starts on November 21, 2013 at 4:00 PM PT and will last 72 hours.

What are the prizes?

  • 1st Place: $10,000 USD
  • 2nd Place: $2,000 USD
  • 3rd Place: $1,000 USD
  • 4th-25th Place: $100 USD

Who gets T-shirts?

The top 100 finishers from Round 2 will get t-shirts.

Registration
FAQ

Read more »

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

By AlexDmitriev, 5 years ago, In Russian,

Всем привет. Где можно сдать длинное gcd? Или хотя бы задачу, в котором оно используется.

Спасибо

Read more »

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

By AlexDmitriev, 5 years ago, In Russian,

Кажется, в текущих версиях C++ компиляторов, абсолютно правильно работает %lld, в том числе, совпадая с %I64d

Мне кажется, стоит убрать предупреждение, мешающее отправлять такие решения и не добавлять спойлеры в задачах, о том, что нужен ввод/вывод 64-битных чисел.

Код


#include <stdio.h> int main() { long long x = 1ll << 60; printf("%lld %I64d\n", x, x); printf("%d %d %d\n", sizeof(int), sizeof(long), sizeof(long long)); printf("%d %d\n", sizeof(double), sizeof(long double)); return 0; }

Посылки в случайную задачу:

3143024 3143022 3143006

Read more »

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

By AlexDmitriev, 5 years ago, translation, In English,

Round 2 starts at 01:00 MSK

Top 100 will get t-shirts and will be advanced to round 3.

Link

Read more »