Блог пользователя AGrigorii

Автор AGrigorii, 3 года назад, По-русски,

676A - Николай и перестановка

Все, что нужно сделать в этой задаче — найти индексы в массиве чисел 1 и n. Пусть это будут p1 и pn соответственно, тогда ответом на задачу будет максимум из следующих значений:

abs(n - p1),  abs(n - pn),  abs(1 - p1),  abs(1 - pn).

Асимптотика решения O(n).

676B - Пирамида из бокалов

Ограничения в задаче были таковы, что можно было просто промоделировать процесс. Предлагаем вам следующий вариант: заведем емкость бокала равную 2n единиц. Утверждается, что тогда излишки шампанского, которое польется на уровень ниже, будут всегда соответствовать целому числу. Итого, выльем в самый верхний бокал t * 2n единиц объема, а далее действуем следующим образом: если в текущем бокале больше шампанского, чем его емкость, то surplus = Vtek - 2n, а еще нужно не забыть добавить surplus / 2 шампанского в два бокала на уровне ниже.

Асимптотика решения: O(n2).

676C - Вася и строка

Эта задача хорошо решается методом двух указателей. Пусть указатель на левую границу l, а на правую r. Тогда для каждой позиции l будем двигать правую границу до тех пор, пока на подстроке slsl + 1... sr можно провести не более k операций замены, чтоб эта подстрока была симпатичной. Для проверки потребуется завести частотный словарь размером с алфавит строки, который будем пересчитывать вместе со сдвигом границ.

Асимптотика решения: O(n * alphabet).

676D - Тесей и лабиринт

Можно легко понять, что состояний лабиринта всего 4. Допустим, в этой задаче нет никакой кнопки, как ее решать? Ответ очевиден: это обычный поиск в ширину на гриде. Что нам дает наличие кнопки? Нам нужно дополнить наш граф еще 3 дополнительными уровнями, а нажатие на кнопку сассоциировать с переходом на следующий "уровень" лабиринта. Вертикальные переходы необходимо зациклить. Тогда запустим бфс уже на таком трехмерном гриде и выберем минимум из значений по уровням в клетке с Минотавром, либо поймем, что пути до этой клетки нет.

Асимптотика решения: O(n * m).

676E - Последняя битва человека против ИИ

Пожалуй, самая интересная задача этого раунда. Необходимо разобрать два случая: k = 0,  k ≠ 0.

  1. Случай k = 0. Тогда делимость многочлена на x - k будет определяться лишь значением коэффициента a0. Если a0 уже известен, то нужно сравнить его с нулем. Если a0 = 0, то это уже победа человека, иначе поражение. Если же a0 еще не известен, то все зависит от того, чей сейчас ход. Кто ходит — тот и выигрывает, поставив на позицию a0 нужное ему значение.

  2. Случай k ≠ 0. Тогда опять же есть два случая: все коэффициенты уже известны, и нам нужно проверить, является ли x = k корнем получившегося многочлена (например схема Горнера), или есть неизвестные коэффициенты. Если есть неизвестные коэффициенты, то поймем почему выигрывает при оптимальной игре тот, кого последний ход. Допустим известные все коэффициенты, кроме одного. Пусть при xi. Тогда обозначим за C1 сумму по всем j ≠ i ajkj, а за C2 = ki ≠ 0. Тогда уравнение ai * C2 =  - C1 относительно ai всегда имеет решение. Если ходит человек, то в качестве коэффициента ему нужно вписать корень, а если ходит компьютер — что угодно, лишь бы не корень.

Асимптотика решения O(n).

 
 
 
 
  • Проголосовать: нравится
  • +63
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится

I crossed the road, walked into a bar, and changed a lightbulb.

Then I realized that my life was a joke...

just like this editorial

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

Thanks for fast editorial and the nice contest!

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

а почему заминусовали?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone give an intuitive approach for problem C . I can't understand the editorial.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I thought this problem in this way: You have N numbers (a_i = {0,1}), find the maximum consecutive sum (only whit ones) if you can convert at most K zeros into ones. ?

    It can be solved using two pointers. Now you can repeat this algorithm for each letter. I hope it helps you.. (Sorry for my poor english)

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

    I'll explain C using the example: "abbaa" , k = 1

    First, find out how many consecutive a's are possible in "abbaa" if we can swap no more than one 'b':

    We're going to have "pointerLeft" and "pointerRight" describing the substring we're looking at during the execution. Both pointers start from -1.

    pointerRight++ 
    -> "a" possible
    pointerRight++;
    -> "ab" possible by swapping 1 b
    pointerRight++;
    -> "abb" not possible, we cant swap 2 b's
    pointerLeft++;
    -> "bb" not possible
    pointerLeft++;
    -> "b" possible by swapping 1 b
    pointerRight++;
    -> "ba" possible by swapping 1 b
    pointerRight++;
    -> "baa" possible by swapping 1b, also the longest possible substring so far
    

    We have now looked into all relevant substrings of consecutive a's. Next we would do the same thing for consecutive b's.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks a lot!

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Hey @baobab, I have implemented this problem using two pointers but I'm not able to understand how binary search will be used in this problem ?

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I implemented it with two pointers only, haven't looked at the binary search solution.

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        hey you can look into my solution : http://codeforces.com/contest/676/submission/30375778

        i know that this is an easy problem but can't think of it in this way...after two hours i land on this solution :)

        idea : first make blocks of a's and b's and then find presums for a and b separately(for_A and pre array represents these). Now, take the first a and find the position upto which you can go ..(this can be done with the help of binary search in pre array (for a) and for_a array(for b)) and then simply update the answer and at last take the max for the two cases.

        complexity = NlogN

        but the editorialist solution is really cool :)

    • »
      »
      »
      13 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      can u give me ur solution link i liked ur way simple and easy to understand

    • »
      »
      »
      10 месяцев назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      hey man i am using a similar approach but it times out on 12 test case do i need to optimise it

      here is the link https://codeforces.com/contest/676/submission/48301769
      • »
        »
        »
        »
        10 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Hey, I took a quick look at your code and it looks like you're sometimes decreasing pointer r. You want to only increase both pointers, never decrease them. That way you can guarantee O(n) time complexity.

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thx, that was very helpful

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Pick one of the alphabet (a or b in this problem) and do the following: - Consider every character other than the picked character as a bad character. You need to find the maximum subarray that contains at most k bad characters because we can replace them with the picked character. Finding Maximum subarray with at most k bad characters can be computed with two pointers

    Check this submission

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

    Me too, but I can give you alternative solution. Lets do binary search for answer — can we get "good" substring with such length. Left = 1, right = n + 1. In search we will look all substrings with middle = (left + right) / 2 length. At first we look at s[0:m — 1] and count "a" and "b" on it. Then we look at s[1:m] and so on, recounting "a" and "b". If we have min("a", "b") <= k at any moment, return true. Else return false. Answer is Left. O(n * log(n)). http://codeforces.com/contest/676/submission/18085847

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you m8! This solution is much more beautiful ( because I hate pointers )..

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks @CRAZY_POMIDOR , I was looking for a binary search implementation. Can you please explain it little more? I'm not able to understand counting from S[0-m-1] and then from S[1-m].

  • »
    »
    3 года назад, # ^ |
    Rev. 8   Проголосовать: нравится 0 Проголосовать: не нравится

    algo:

    1. record the positions of the characters in different vectors( resizeable array). suppose,vector A for char 'a' and vector B for char 'b'.

    2. base case: if the size of A or B vector <= K then answer is n

    3. i) loop with k' th index of array A till the end of A and question one thing, " what is the maximum size if we change the previous k 'a' characters?"

    ii)then, " what is the maximum size if we change the last k 'a' characters?"

    Do 3 for array B also.

    Maximum size is the answer.

    C++ solution:18097109

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You've to change k no. of same characters to optimise the substring length. Now suppose I take an array and assign 1 to the indices where character a occurs in the string and 0 where b occurs. Here marking the index as 1 implies we've changed an 'a' to 'b' .Now take the prefix sum of an array(array is a[]) . Considering two indices i and j (j >= i) , (a[j] — a[i-1]) represents the no. of characters changed for a substring starting from i and ending at j. so for every index i from 0 to n-1 find the upper_bound j such that a[j]-a[i-1] = k and the length of the string becomes j-i+1. Do this for all the b's also and take the max at each step.

    Hope it helps!

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think my solution may be a little better and more elegant. :) Please take a look and leave your comment.

    My solution used kind of greedy idea.

    First, we record the possible places could be changed. By possible places, I mean the positions of the letter which appears less. For example, in "aabaabab", we record the positions of 'b's. (Without loss of generalization, we assume number of 'a' is always larger of equal to number of 'b'.) In this example, we record 2, 5, 7. Then we add -1 at the beginning and 8(the length of the string) at the end. So we get <-1, 2, 5, 7, 8>.

    Then, we notice that, if we can change 'k' times, to get the longest string. These 'k' changes should be consecutive. In our example, let's say k = 2. Then, the change happens at either 2&5 or 5&7. It won't happen at 2&7 because this is like just change 2 or just change 7 when k = 1.

    Haven noticed above two points, we can do the iteration with different k = 0~maxK. (In fact, only use maxK is enough. I didn't realize this when I was implementing it but now it seems true to me.)

    The question left is, how can we quickly get the result after we made 'k' changes? Suppose we changed the i'th position in all possible changes(Namely, the vector <-1, 2, 5, 7, 8>). Then, the answer is vi[j+k] — vi[j-1]. Namely, we changed the ith position, the (i+1)th, ... (i+k-1)th. Then the break happens at (i+k)th and (i-1)th position, for i = 1 ~ ((i+k) < vi.size()).

    Submitted code here. The complexity is O(vi.size()^2). The code can be further improved as I mentioned use only maxK. Thus can be reduced to O(vi.size()) = O(n).

    Please leave your comment.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I like to think about two pointers this way:

    Without the time limit, we could solve the problem by testing each of the n possible solutions, each one starting from each position of the string. This would give us O(n^2) complexity with the naive approach.

    However, we can find the solution for a given position with the solution of the position before. How? Well, the first difference between the two solutions is the first characters. By removing it from the first solution it relaxes the constrictions of the second. It is obvious that every character of the first solution will also be present in the second. That means that, after removing the initial character, we just need keep inserting the following until it breaks the condition.

    We can implement this solution with two pointers, one for the beginning and one for the end of the string. Note that each one of them will only increase, moving to next position, never regressing. This gives us O(n) complexity.

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    My approach :-> Let us assume that if we are given beauty 'x' , can we find a sub-string by changing the K characters in the string , if we can find it using 'x' — beauty then we can also find using a beauty value of x-1 or for any y such that y<=x. So we can binary search the answer.

    The sub-problem is now defined as for a given value x can we find a desired sub-string by allowing k changes. this sub-problem can be solved in linear time by using sliding window and maintaining the count for letter a and letter b separately.

    https://codeforces.com/contest/676/submission/51955698

    Please correct me if i am wrong.

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

А можно более подробно про проверку корня алгоритмом Герона?

»
3 года назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

Nice editorial, clear explanations!

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В задаче E я просто сравнивал по модулю в лоб, но использовал простой модуль порядка 10^13 и оно зашло. Проверял после контеста 1е9+7 и он валился на 62-м.

»
3 года назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

Todays C was same with 660C - Hard Process problem.

»
3 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

In problem A, the statement, Print a single integer — the maximum possible distance between the minimum and the maximum elements Nicholas can achieve by performing exactly one swap Exactly seems to imply that one swap is necessary, so shouldn't answer for the case

3

1 2 3 be 1.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I had a nice contest today because the problem C was like 660 C and 660 C is the problem that I made it for the 11th educational round. I wish such good things for u in the next contests. :D

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

in problem E how to check if k is a root of the given polynomial? this is pretty much the hardest part in the problem :3

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    You have to check if f(k) = 0. First consider a0: it must be divisible by k otherwise f(k) != 0 because all the other terms are multiples of k. So you can add a0/k to a1. Now consider a1: it must be divisible by k otherwise f(k) != 0 because all other terms are multiples of k. So you can add a1/k to a2... and so on. Finally when only a_n is left, check that it is equal to 0.

    Code: 18087228

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Let the answer mod a large prime. If it is hacked, mod more primes.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I used integers in range [2e9, 2e9 + 200) as mod, and got accepted ;)

    18092407

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      You got lucky :-) Here is a hack: http://pastebin.com/XZ2za9Xw It should say No, but you say Yes.

      Basically the product (and lcm) of the numbers are still in the range of a degree 10000 polynomial. Either you need more numbers, larger numbers (why not 1e17,1e17+200?), or random numbers that the hacker can't easily take the lcm of.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    You have to check if f(k) = 0 as mentioned. However, f(k) may be very large and thus cannot be stored. I used a slightly different approach to calculating f(k).

    ll done = a[n];
    for(i = n - 1; i >= 0; i--) {
      if(abs(done) > 10000000000LL) {
        break;
      }
      done = a[i] + (k * done);
    }
    
    

    Finally, check if done is zero. The comparison with 10000000000LL works because of the following. When i = 0, abs(done) must be less than 10^4, since the problem specifies that abs(a[0]) < 10^4 and their sum must be zero. Now, when i = 1, abs(done) must be < 2 * 10^4, since abs(a[1]) < 10^4. Continuing so on, abs(a[n]) < 10^5 * 10^4 if n = 10^5.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Note that, for the same reason, simply using storing done as a long double works. You have sufficient precision to store numbers <= 10000000000LL. If it exceeds and becomes too large, you can't store the number perfectly, but it is good enough that it won't be equal to zero, so you can just check if done == 0.

  • »
    »
    3 года назад, # ^ |
    Rev. 4   Проголосовать: нравится +6 Проголосовать: не нравится

    One way to do it is the following: Notice that you can calculate the value of the polynomial as follows:

    xn = ank

    xn - 1 = (xn + an - 1)k

    ...

    x1 = (x2 + a1)k

    The value is then x1 + a0. Now notice that if any of the xi is too big in absolute value, then xi - 1 = (xi + ai - 1)k will also be too big and so on. Thus then k cannot be a root in this case. If none of the intermediate results are too big, all of them will fit in a 64-bit integer and we can just check whether we get zero in the end.

    The precise condition for 'too big' can be found to be the following:

    |xi| ≥ 10000|k| / (|k| - 1)

    Note: here I've considered only the case when |k| ≥ 2. When |k| ≤ 1, things are trivial.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

could someone please explain problem B more clearly. Thank you.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I replied to comment under, I explained "my" solution (actually I took idea, but I coded it later xD)..So if you are interested go and see..

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    int solve(int n, int t) {
            double[][] can = new double[n + 1][n + 1];
            can[0][0] = t;
            int filled = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j <= i; j++) {
                    if (can[i][j] >= 1.0) {
                        final double excess = (can[i][j] - 1.0) * 0.5;
                        can[i + 1][j] += excess;
                        can[i + 1][j + 1] += excess;
                        filled++;
                    }
                }
            }
            return filled;
        }
    
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone give a nice explanation for problem B ? please...

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone give a nice explanation for problem B ? please...

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    I had problems with understanding it, but I solved it after looking some other codes.. Here is my solution; Make array 10 x 10 and let array[0][0] be the top Glass. Give it value 2048 * (t -1) Now you ask: Why the hell 2048 * (t-1)?! Because you dont want to play with doubles,to every "child glass" you will add half of vine from its parents, so when you do operation /2, you dont want to lose precision, thats why you put 2048 ( 2048 = 2 ^ 10, you will always get integer). Then, array[1][0] is child with only one parent, array[0][0], so you set array[1][0] = array[0][0] /2 -2048 ( you substract 2048 because you save values which will be added to childs). Also, array[1][1] has same one parent so you will do same.. So you just go through matrix and fill needed cells by adding half of parents values to childs! If child is array[x][y] then there are two cases; 1. It can have only one parent ( if x == 0 or y == x, or by words if it is most left or most right glass in row) 2. It can have two parents — all other cells.. Also, if you get negative value in child, that means it wont be filled, so when you go through matrix you just ++counter when cell is >=0..

    I hope I explained well, But I dont think so xD

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

    Here is a way to solve it. It doesn't involve doubles.

    Let's say our current glass is located at row i and col j.

    Obviously if a glass ever gets full then it will add water to the two corresponding glasses below it:

    glasses located at (i+1,j) and (i+1,j+1)

    Now for each time we water a glass, we can simulate the process by watering to the top glass, and then the ones below it and so on.

    However, there is a problem, we need to know when a glass is full, so we can push water to the level below it. ( It can easily be done by a recursive code).

    If you trace it with the pen and paper for few samples, you can find that a glass is full when it is watered ( 2^(lvl) ) times. (The lvl is zero based ).

    So basically you need to maintain a 2D array, where arr[i][j] corresponds to how many times the cell located at arr[i][j] was watered.

    Set counter to 0.

    When you are watering a cell, if after watering it becomes full, increment the counter.

    If it doesn't get full, do nothing.

    If it is full before you water it, then water glasses below it. (i+1,j+1) and (i+1,j).

    Again, the formula of 2^lvl gets very clear why it works if you trace it with a pen and paper.

    Sample Code : http://codeforces.com/contest/676/submission/18082377

    • »
      »
      »
      9 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      A glass might be full even before the 2^(level) times water is poured due to the filling of the upper-level glasses getting filled and water reaching from the overflowing of these cups. 2^(level) times water is needed to completely fill all the cups in a given row.

    • »
      »
      »
      9 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I got it. Thanx. Wonderful answer brother !!

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Regarding the "two pointer algorithm", what is a necessary and sufficient condition for the "two pointer algorithm" to work (as opposed to check all subsequences in O(n^2))? My guess is if a longer length can only improve a solution if it is feasible and vice-versa but I have not been able to formalize this.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Monotonicity, i.e., right pointer increment increases the function value and left pointer increment decreases the function value.

    You can easily prove the two pointer technique in monotonic function works with contradiction.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Maybe we are saying the same things but I think your formulation is too strict. I think all we need is that f must be monotonic in length (i.e. for a longer length, the value is maximized if the value is defined). In slightly more precise terms, it would be something like the two pointer algorithm takes in an integer n and a partial function, f from interval to A where A is comparable and returns the largest interval in [0, n) at which f is defined and maximized.

      Also, I think the algorithm would work if we loosen the restriction on f a bit more too — I think it would still work if f is monotonic for overlapping intervals i,e. if f is defined at two intervals i and j and i overlaps j and len(i) <= len(j) implies f(i) <= f(j)

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Я не согласен с решением задачи B

В условии парень выливает объем одного бокала в секунду, а в решении ты выливаешь все сразу. И поэтому порядок наполнения сбивается. Центровые бокалы наполняются быстрее: они начинают уже переполнятся, в то время как крайней на том же уровне пирамиды еще недоконца наполнены.

Может кто объяснит...

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Центровые бокалы будут наполняться быстрее и в случае, если лить по одному

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

can someone please explain E "we have the equation ai * C2 =  - C1, it will always have solution" more specifically. — — I think -C1 can not be divided by C2. Thanks in advance.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Even with a given explanation I can't turn task B into code. Can someone show your solution, please?

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

In problem D, can anyone explain this "Because of buttons we need to add to graph 3 additional levels and add edges between this levels."..What are these 3 levels ?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    One for each rotation

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Each rotation is new level-every element changes(except '+' and '*'). So you need to make 3d array: matr[k][i][j], where k is current level(0<=k<=3)- there are 4 levels.And then you need to fill all array levels with changed elements('>' --> 'v', for example). Finally, just use bfs, where you can go to upper level or to closest neighbour cell(check if you can go there)

»
3 года назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

Господи, последняя задача — просто позорище, div2E уже не торт. Мне одному показалось, что это задача шутка? P.S. Какая ещё схема Горнера, что за стёб? Многочлен делится на (x-k), если k является его корнем — теорема Безу, алло!

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    У меня для вас плохие новости!

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А как проверить, что k является корнем многочлена?

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится -13 Проголосовать: не нравится

      По нескольким модулям посчитать

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Это, конечно, хороший прием, и знать его полезно, но в самом тупом варианте он здесь легко взламывается, а вычисление по нескольким рандомным модулям требует написания большого количества кода. У Горнера и кода мало, и взломать нельзя.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain me problem D in detail , i didn't understand the rotation part: Thanks in advance ..

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In probelm D, at the second testcase, my output is 4 in my visual studio. But system says my output is -1. Could anyone please explain why my output is different? http://codeforces.com/contest/676/submission/18111486

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My code for problem B is 18097517 I realized this approach later in the contest so I couldn't get AC during contest. But my basic idea is to use a 10*10 matrix and put t units on the top glass then take t-1 out of it and distribute to the glasses beneath.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Наконец-то руки добрались http://codeforces.com/contest/676/submission/18131834

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My code for Div2-C-Vasya_and_String gives correct result on ideone and my system. ideone solution

But, codeorces gives WA verdict on the same code on very 1st test case. My solution on CF[Both ideone and codeforces code are same]

Can somebody help me debug my code, if there is any ?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

hey can anyone look at my code for 676c...it is giving wrong ans on 12th case I'hve used binary search approach. http://codeforces.com/contest/676/submission/18114269

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

A question out of the blue: Can we solve problem D using Dijkstra approach on a 2D distance array?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

in problem B how does one conclude that 2^n should be the volume for each glass. Like in the editorial it mentions that so that the water that flows down in integer. but how do i conclude this in general during similar questions. in other words how to come up with such a strategy during contest

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think editorial's solution is not the only solution there. I just used brute force approach to solve it.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem D: My solution is O(4*n*m) and it is judged as TLE on test case 24. Can someone please have a look and suggest what's wrong? My Code

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В Е плохие тесты. Я такую фигню придумал и реализовал. Было пару ошибок в логике и реализации, но в итоге я добился ацептеда, подсматривая тесты. А потом прочитал разбор, и понял какой я глупец... Как минимум моё решение отдельно рассматривает все участки разделённые хотя бы двумя нулями. Поэтому моё решение на тест 1 1 1 0 0 ? при k = 100 выдаст No.

»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The tag for problem C div2 says dp. How can it be done with dp.

I've tried it using binary search and two pointers separately. How with DP? Kindly help !!