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

Автор BledDest, история, 5 месяцев назад, По-русски,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Разбор задач Educational Codeforces Round 25
 
 
 
 
  • Проголосовать: нравится  
  • +68
  • Проголосовать: не нравится  

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

У задачи Д есть решение немного проще:

Изначально заведем массив А в котором мы будем хранить для каждой буквы количество ее вхождений в строку T.

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

Также у нас будет функция check которая проверяет можем ли мы составить целую строку T из текущего набора букв. Если можем, то обновляем массив B.

Теперь идем по строке S, если встречаем знак вопроса — делаем check и перебираем букву которую мы хотим поставить, если текущее значение B[буквы] меньше чем необходимое нам значение A[буквы], то ставим на текущую позицию эту букву и делаем ++B[буквы].

O(N*26)

Поправьте, если решение неправильное...

p.s. check на каждой итерации вызывается не более одного раза.

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

    Test:

    aaa?bbbb

    ab

    Ur answer — 3, correct — 4

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

      No, my answer is 4.

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

        Обновить массив — вычесть из него изначальное количество каждой буквы?

        Вроде, жадное решение действительно работает.

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

          В чеке мы для начала проверяем для каждой буквы, которая есть в строке T, что B[буквы]>=A[буквы], если для какой-то буквы это не так, вылетаем.

          Попутно запомним минимальное значение B[буквы]/A[буквы]. Далее пройдемся по буквам которые есть в строке Т и отнимем от B[буквы] это мин. значение умноженное на A[буквы].

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

In problem F The length of the smallest period is (|t|-plast) instead of |t|/(|t|-plast).

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

in problem E , why does this logic fails ?
1 : pick vertex with zero in-degree (and with minimum node number ,in case of tie in degree)
2 : remove this vertex from the graph and update degree of all other nodes attached to this.
3 : assign label to this removed vertex
4 : repeat above steps while there are nodes in graph

labels are assigned from 1 to N

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

    Becouse then you firstly attach one to first vertex it might have parents. You need to do it from the other side. Label highest leave n and remove it.

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

    Try this:- 10 2

    3 1 4 1 The problem here is the algorithm tries to allocate the best position for value 1,2,... and so on.But this greedy algorithm forces you to place a bigger number at the more significant position.

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

    counter example

    4 -> 1

    2 -> 3

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

For problem A, why the accepted output of input '100' is '100', shouldn't it be '10'? (Because first we meet 1 and then terminate of first digit with 0 and then we meet 0, thus the output is 10) sorry for my bad english

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

    I also can't understand this one

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

    The problem said that 0 character separates blocks consists only character 1, and the length/size of each block is the digit it represents.

    For the input 100, we can rewrite it like this: (1)0()0(). So there are 3 blocks. First block has size 1 and the other 2 have size 0. So the output is 100.

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

      I'm too have written solution with using split as you have, but in Java blocks with zero-length lines skips.

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

        yes, it is like the difference between .split() and split(' ') in python

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

    We divide line using '0',start,end. Then print count of '1' in every segment.

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

      Thanks for your explanation by image. Initially I thought all zeros themselves were separators which separate the digits before each of it and the digits after each of it, and zeros appeared only when there were at least three zeros, for instance, 11000111, in which the first and the third zeros respectively separate 11 & 0 and 0 & 111, meaning the result is 1+1 and 0 and 1+1+1.

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

Can somebody explain problem c I find it diffcult to understand

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

    The problem is saying that you have a person who has to solve the problems in the Decoder contest, and he has only solved difficulty k problems before. He will only be able to solve a problem if its difficulty is <=2k. So in some cases, he needs to go solve harder problems outside until he can get high enough to finish the original problem.

    For example, k = 3. If one problem is difficulty 10, he can't solve it. First, he needs to solve a difficulty 6, and then he can solve 10.

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

In problem F, why the answer for the string kbyjorwqjk is 11 and not 12 (test case 4)?

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

WA in test 14 prob D but i can't check what that test is

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

In problem D, If i make a count map for all characters for string t and then consider window length of strlen(t) in string s.

Now in each window, there is map count for all characters and then a variable storing count of number of empty characters -> '?'. Now we match the count array of t with count array of window and see if there is a match considering empty characters with all unmatched characters.

Lastly, if i get a match , I jump from i->i+strlen(t) otherewise i->i+1.

Will this algorithm work..??

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

In problem D, If i make a count map for all characters for string t and then consider window length of strlen(t) in string s.

Now in each window, there is map count for all characters and then a variable storing count of number of empty characters -> '?'. Now we match the count array of t with count array of window and see if there is a match considering empty characters with all unmatched characters.

Lastly, if i get a match , I jump from i->i+strlen(t) otherewise i->i+1.

Will this algorithm work..??

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

    It should work. Here's my solution, though I think it's slightly different from yours. I stored all positions of '?,' then iterated through them. For each position keep going through all letters in t while subtracting it from a count map if it is already in string s (not a '?'). If a letter isn't in s, we set the current '?' to that letter and repeat for all other positions. Ignore the variables 'bad' and 'mx.' I forgot to delete them but they are unused. 28608658

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

UPD : SOLVED

Problem D : i AM Getting WA on test 14 . my solution : http://paste.ubuntu.com/25112777/

can you please help me to find out the bug .

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

in problem E :

I have not understood why doing the same as the editorial but from the other side is wrong yet, I mean why labeling from 1 to N starting from the nodes with in-degree equals to zero is wrong.

I applied the proof in the editorial on that and I didn't find anything wrong, could anyone please tell where is my mistake ?

thanks in advance.

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

    I thin there is a bug in your code, when you are trying to do something with unconnected nodes. In the test you fail judge is waiting for 13, while where is no information given about 13. And you print 15, you should print 13, becouse it is unconnected and can be smaller than 15.

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

      sorry if it seemed like I was defending my solution , I know it's wrong !!

      maybe the code has some bugs. However, you can see that this approach is wrong here by the counter examples that were mentioned in the above comments.

      what I want to know is why the proof in the editorial can not be applied on my approach, where does it fails!!!!!!

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

        It works, you just fail to implement it

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

          take this counter testcase:

          4 2

          3 1

          2 4

          if you apply our approach on this test you will choose 2 first, then 3,then 1,finally 4. which will give you this permutation :

          3 1 2 4

          but the correct solution is to choose 3 first, then 1, then 2, finally 4. which will give you the correct permutation:

          2 3 1 4

          if I made a mistake, hope you clarify where it is

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

    From the set of nodes of in-degree equals to zero: picking node V, the one with smallest index to be labeled '1' will not always give the lexicographically smallest permutation.

    Let's apply the same approach of the editorial: let node V be labeled X (X > 1), this labeling may result that other node U (U < V) get labeled Y (Y < X) which result in lexicographically smaller permutation.

    So applying the same approach won't result in a contradiction.

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

    Look at this testcase: n = 3, m = 1; An edge from 3 -> 1. Ur algo gives 3 1 2 as the output whereas 2 3 1 is the lexicographically smallest.

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

и если |t| делится |t| - plast (plast — последнее значение префикс-функции), тогда длина минимального периода равна

Она же в этом случае равна |t| - plast, нет? Я, дурак, на голубом глазу это сразу в код перевел, а потом час думал-гадал, буквы на листочке рисовал...

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

Sorry for the incorrect formula in F, it is fixed now.

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

Can someone explain reason for MLE in my code?

Code : 28646208

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

    Same problem as here. Your binary search may find incorrectly a big number as answer. So this vector that you create to build the answer will exceed the memory limit.

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

Can someone help me with my solution for D ? I'm getting WA

Code : 28647476

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

    The problem was overflow inside your check function. If the frequency of some letter is big and you test a big number at the binary search the result of multiplication may exceed by far the int limit.

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

Could anyone please explain problem D clearly?I don't get that clearly.Thanks in advance!

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

Could someone please explain problem D more clearly?I didn't get that.Thanks ins advance :)

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

Can anyone tell me What is qsum in 825D?

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

In 825F how the prefix sum is calculated? How the complexity is reduced from s^3 to s^2?

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

Can someone please help me find the mistake in my code for 825F?? Getting wrong answer on test case 13. submission/28674792

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

Hi :) I have read that problem E can be solved with a "somewhat standard approach, involving advanced data structures and quite tedious to implement" (Petr words xD).

I understand that the intended and best solution is the one described here, but I would like to know what is this other solution? :)

Could anyone elaborate on this? Thanks

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

    I have a basic idea however not sure how to optimize it.

    1. Reverse the edges first.
    2. Choose the smallest index that is yet to get a number, mark all the nodes reachable from it. We can assign a number to this index only after assigning number to all the nodes reachable from it.
    3. Among the nodes reachable from this index, choose the smallest index that is yet to get a number and repeat the process.
    • »
      »
      »
      5 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Yes, that's the question haha, is it possible to optimize those kinds of naive algorithms?

      Another similar way will be:

      Reverse the edges.

      Go over the nodes in increasing order. For a node v, count x = the number of nodes reachable from it (including itself), v's label has to be  ≥ x, so we can choose the smallest free label among those  ≥ x and assign it to v.

      No idea if this can be done better than in O(N2)

      upd: this doesn't work as pointed by MrDindows, thanks

      The obvious bottle neck for these algorithms is to get the size of the "reach" of a node, I wonder if there's a way to optimize that, or if the other solution uses a different approach.

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

In the problem C : 825C - Multi-judge Solving
Are we supposed to find the number of questions that are to be solved only from some other judge?

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

Can anyone explain test case in G?

What i understand that graph is 1-2-3-4 and queries are:

1)set 2 vertex black

2)set 2 vertex black (again?)

3)get answer for vertex x=2.
we have only one black vertex (=2), so the only path between 2 and black vertex is zero path from 2 to 2. so the answer is 2. Where am i wrong?

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

For problem C, why not choose the most hard problem like with difficulty 10^9 to solve at first? Then we can solve all other problems , isn't this the best way?

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

can anyone please explain what is wrong with my solution of F http://codeforces.com/contest/825/submission/28946671

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

Can someone please help me debug this code ?.I have checked it many times and it seems correct to me.