Don't you like ranked contests? Are you racist?

Так вся Россия оффлайн писала региональный этап в том году. В этом году есть шанс, что будет онлайновая регионалка.

Press X then it will load.

Scoring have been published. Best luck to all participants.

When it was moved last time, servers were showing they are busy almost all the time, hopefully today it will be better...

This time, I am glad the contest got delayed. Forgot to register earlier.

same problem here :D

Just when you will have the quality to acquire it. Best luck to you in this round. :D

Because the contestants in codeforces are increasing exponentially.

best of luck to you :)

Wish granted ;)

lucky man. contest will start with delay.

Yes, I hope no more delays!!

hmm, you are right.

Really? It depends on number of problems? I don't think so...

All my hacked solutions were exactly the same. My test was s = '9' 10^6 times, a = 9, b = 2

Если искать НВП за O(log(n)) и делать "откаты" когда уже поднимаемся с вершины, то сложность будет O(n² * log(n)). И да, это проще делать при обходе в глубину.

Сначала закореним дерево где угодно.

Динамика за O(N^2).

Параметры: текущая вершина(v), в какой последней вершине был концерт(last).

Переходы: Переберем все ребра из текущей вершины, узнаем, можем ли мы сделать переход в вершину на другом конце ребра. Как это узнать? Допустим, v — предок last. Тогда нам можно идти по всем ребрам, кроме того, которое ведет в поддерево с last. Допустим v — не предок last. Тогда нам можно идти по всем ребрам, кроме того, которое ведет вершину v к ее родителю. Еще всегда нужно учесть два случая — проводим концерт в вершине v или нет.

Почем это работает быстро? При фиксированном last каждое ребро переберется не более двух раз. Ребер O(N). Следовательно, всего переходов по всем состояниям O(N^2).

ну это заходит, мб с лидирующими нулями накосячил?

А если все разряды текущего и предыдущего неизвестны, то что делает твоя программа?

Я так и делал. У меня был WA9, подобрал такой контртест:

3 1236788 123?58? 1237889

Смотрел справа-налево и забывал обнулять предыдущие знаки вопросов, если встречаю бОльшую цифру.

так верно же, но много разных подводных камней, так и не успел написать код, легко напутать в мелочах.

The answer should be "No"? As your test doesn't differ from

120 12 1

Wanted to hack solution C by TL with test.

1...1 (1 repeats 1e6 times)
5 1

But this test file has size (1e6 + 5) Bytes! And this is more then 256KB. Why does system not allow to upload big tests???

Lost my hack because of this.

A generator is a program which outputs the hack input in the correct format. I don't think that you can test it without a contest. Just write one and check if the generated input is ok.

The two parts must be positive integers
is zero considered to be a positive integer ?

По мне в D-шке слишком простые тесты

Решение проходило претесты, если оно для всех суффиксов за линию проверяло делимость на число b?

The number is too large, look at constraints. Has to be less than 10^8.

Because b ≤ 10⁸

Because b must be in range [1..10^8] It clearly said in problem statement

you have extra 9 at the begin of second number

Because there is the answer for string "604": "60 4" where both of numbers are divisible by 6 and 4 respectively

Some nations do not have static IP.

IP based check is bad idea. But I have same feelings... Mbaybe solution could be that when there is no Div 1 competition, they will have same problems in and they can compete in speed typing... Or separate ranking can be created for such contests...

try to check forward and backward (will be almost the same like forward )

the idea starts from the observation:

lets say you have the number 78541

78541%x = ( (7*10^4)%x + (8*10^3)%x + (5*10^2)%x + (4*10^1)%x + (1*10^0)%x )%x

if you dont get the further idea for the solution i will add the next part :D

Do people like downvoting stuff just for fun? This community should be a little more mature.

don't use strlen(s), it has O(n) complexity, where n is length of s.

strlen() has a complexity of O(n), not O(1).

So your overall complexity is O(n^2).

you repeatedly called strlen, which has n complexity;

just use c/c++

It depends, what is the solution, for example this ona — http://mirror.codeforces.com/contest/490/submission/8818849 have to end with TLE and problem is not in python...

Traverse a string in both directions and keep two arrays ad, bd.

For ad[i] we traverse the string from the left to the right and find the reminder s[1: i]%a. There is a formula for this: ad[i] = (ad[i - 1] * 10 + s[i] - '0')%a.

For the bd[i] we traverse string from the right to the left and find the reminder s[i + 1: n]%b. Also we keep the variable bten_i which is equal to 10ⁱ %b. So there is a formula for bd: bd[i] = (bd[i + 1] + (s[i] - '0') * bten_i)%b.

Finally we traverse the arrays ad, bd and search for such index i, that ad[i] = bd[i + 1] = 0.

http://mirror.codeforces.com/blog/entry/14826#comment-198073

If we divide the sequnence into two parts: 1, 2, ..., i and i + 1, ..., n, then we need to check s(1, i) % a and s(i + 1, n) % b. Since s(1, i) % a = (s(1, i — 1) * 10 + s[i]) % a, s(i, n) % b = (s(i + 1, n) + 10^(n — i) * s[i]) % b, we can compute every s(1, i) and s(i, n) within O(n) time firstly. Now, we can check s(1, i) % a and s(i + 1, n) % b within O(1) time.

I Will explain it using an example:

consider the number 116401024(call it N)

we can split it as

(1*10^8)+(1*10^7)+(6*10^6)+(4*10^5)+(0*10^4)+(1*10^3)+(0*10^2)+(2*10^1)+(4*10^0)

   a8       a7       a6       a5       a4       a3       a2       a1       a0 

If this number is divisible by a number M then the modulus must be 0(i.e. N%M==0), to check this we can do:

rem = 0;
rep i from 0 to 8:
    rem = ( rem%M + ai%M )%M;
if(rem == 0)
    the number is divisible by M

Coming to the actual problem

The possible ways we can split the number into two parts are :

1 16401024
11 6401024
116 401024
1164 01024
11640 1024
116401 024
1164010 24
11640102 4

now for each of this splits we want to check if the first part is divisible by "a" and second part is divisible by "b".

Now we can modify the above for loop by storing for each index i, whether the part of the number from 0 to i is divisible by a, like this:

n = Number of digits in N;
rem = N[0]%a;
rep i from 1 to n-1:   --------------------------------> O(N)
    rem = ((rem*10)%a + (N[i]%a))%a
    if(rem == 0)
        divisible_by_a[i] = true;
    else
        divisible_by_a[i] = false;

Similarly, we can do for b starting from least significant digit of the number.

and once we have divisible_by_a and divisible_by_b, we can easily check if we can divide the number into two parts for each index i by the logic:

(divisible_by_a[i] == true) && (divisible_by_b[i+1] == true)  && (N[i+1] != 0)    -------> O(1)

Call the large number s and let n be its length.

For every prefix, compute x[i] = s[0..i] % a. For every suffix, compute y[i] = s[i..n-1] % b. Now scan s from left to right and check if x[i] == 0 and y[i+1] == 0 and s[i + 1] != '0'. If this condition holds, we have an answer.

There's also the weird thing, that it shows my output (which I think isn't supposed to be there, because I shouldn't have time to it), but there is no Answer...

Don't use ansistring. Try to use array of char instead.

1280 can not be reached

Because you cant get 1280 from 2160

My approach:

1. If we determine the first two elements, we can determine the rest uniquely. -> Make an array X such that X[A[i]]=B[i] for every i. Then answer[i+2]=X[answer[i]] for any i.

2. The student ID of the second person is X[0]. The first person in the line has a = 0, b = (second person's ID).

3. The student ID of the first person is A[i] which does not appear in array B. Let id = the first person's ID. There's no student such that b_i = id, because there's no one in front of him! And conversely, the first person is the only student with such property.

We can uniquely determine the first two persons, which determine the rest uniquely.

The total run time is O(n).

My submission

Just find the smallest feasible number every time. I'm not sure what is the best algorithm to find this, but my solution is: First, compare the length of the string with the one of last string, and there are three cases: 1. s[i].size()<s[i-1].size(): impossible, print "NO" 2. s[i].size()>s[i-1].size(): set all '?' to 0 (If it's the first number, set it to '1') 3. s[i].size()==s[i-1].size(): Find the first digit j where s[i] and s[i-1] is different. There are two cases: 1. j==s[i].size(Can't find) or s[i][j]<s[i-1][j]: Find the rightest '?' before digit j whose corresponding digit 'k' in s[i-1] is not '9'(because no digit is larger than 9). If you can't find it, also print "NO". Otherwise, set the '?' to 'k+1'. Then set all '?' before this digit exactly the same as their corresponding digit in s[i-1], and all '?' after this digit to '0'. 2.s[i][j]>s[i-1][j]: Similar to the case 1, but don't need to do the first step because this digit is already larger.

I used binary search to solve E.
Here is my submission.

Every time Polycapus eats the chocolate, he set one of the number to 2/3 or 1/2. So what you should consider is, whether these two products is the same after dividing all 2 and 3. If it is, you can set the power of 3 to the same number by performing several 2/3 cuts to the one which has more 3, and then set the power of 2 to the same number by 1/2 cuts.

Use bigmod. I think your solution is N^2

throng -> through

That's really offensive thing to say. They spent a lot of time to write/test problems and put them together.

Can you be more specific? Can you describe what was silly for each problem?

In your example you have n=4, but 5 different ids in the list. Change n to 5 and add a line with "2 4" — then you will get 1 2 3 4 5.

Your test is wrong not enough information while n == 4 if n == 4 you test data be like this 4 0 2 1 3 2 4 3 0 if n == 5 4 0 2 1 3 2 4 3 5 4 0 try again