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

Автор vovuh, история, 4 года назад, перевод, По-русски

Я правда очень сожалею об ошибках, допущенных в задачах E и F. Не могу больше ничего сказать, так как не хочу оправдывать свои ошибки.

1433A - Скучные квартиры

Идея: vovuh

Разбор
Solution

1433B - Еще одна задача про книжную полку

Идея: vovuh

Разбор
Решение

1433C - Доминирующая пиранья

Идея: vovuh

Разбор
Решение

1433D - Соединение районов

Идея: MikeMirzayanov

Разбор
Решение

1433E - Два хоровода

Идея: MikeMirzayanov

Разбор
Решение

1433F - Сумма с нулевым остатком

Идея: MikeMirzayanov

Разбор
Решение

1433G - Уменьшение стоимости доставки

Идея: MikeMirzayanov

Разбор
Решение
Разбор задач Codeforces Round 677 (Div. 3)
  • Проголосовать: нравится
  • +115
  • Проголосовать: не нравится

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

Thank you Vovuh for all of your time and effort you put into these Div 3s, please don't stop :( Also, E is a good problem if OEIS didn't exist, I found it pretty constructive. F too hard for a brik like me

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

    How to solve E using OEIS? Never used OEIS before.

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

      OEIS is an encyclopedia for integer sequences. You can search by entering a sequence and you will find all others with formulas also. As, for problem E there can be only 10 inputs, and 4 of them are given, so simply searching with the sequence can be find from OEIS

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

      first, write a brute-force to generate the first few elements of the sequence or you can generate by hand in pen and paper, with those elements search in the OEIS. you will get all the sequences that start with these elements.

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

    Would have used some MOD, then it's not straight forward!

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

    without OEIS we can solve , by using simple math (n-1)!/(n/2) it's simple apply mathematics formula like combination of sitting in circular table (n-1)!/2

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

Nice round vovuh really enjoyed the round !! Thanks for the round , hoping to have more such rounds with the interesting problems again.

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

In problem E how can we find sequence on OEIS ?? since we do not know the ans for i/p :6??

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

"Let dp[x][y][cnt][rem] be the maximum possible sum we can obtain if we are at the element ax,y right now, we took cnt elements in the row x and our current remainder is cnt."

Shouldn't the current remainder be rem instead of cnt? I didn't AC this problem, and I want to know the solution. This round was fun, thank you. :)

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

Very nice problemset, these round really help us (beginners) to improve and let us see that you really take care of this platform :)

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

Amazing Editorial!

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

E is a good problem. I really like it.

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

typo in D:

"Let's find any district $$$i$$$ that $$$a_i \ne a_i$$$"

It should be $$$a_i \ne a_1$$$

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

Test cases for problem F were weak, like I just calculate the maximum sum I can get in matrix choosing m/2 element in each row lets call it sum then I print (sum/k)*k , its like greatest multiple of k just smaller then sum, and boom I got AC :). PS:: Later it got hacked (:.

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

In the editorial of F it's written our current remainder is cnt. whereas it should be our current remainder is rem.

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

I didn't understand one thing. In the first problem, why did he write 'dig=x[0]-'0'',basically,subtract the zero.

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

    x[0] is a character....to get the correct integer.. char of 0 is removed. for eg: let x[0] = '3' so x[0] — '0' = 51 — 48 = 3

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

in C answer will be index of maximum element why is it showing wrong answer

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

    The answer will be the index of maximum element adjacent to a non maximal element. If suppose, one prints only index of maximum then it could be right in between 2 maximal elements, such as index 1 in 4 4 4 3. Index 1 is maximum in the array but it is next to another maximum and cannot eat the number next to it.

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

The approach to sentence E is simpler 96159630: there are n people, calculate the number of ways to make 2 circles.

The first person has 1 choice (because he is the first person in the first circle), the second person has n-1 choice, the third person has n-2 choices, ..., the n / 2 person has n / 2 + 1 choice, n / 2 + 1 person has 1 choice (since this is the first of the second circle), the n / 2 + 2 person has n / 2-1 choice .. .

For example:

With n = 6, the number of ways to choose will be calculated as 1x5x4x1x2x1.

With n = 8, the number of ways to choose will be calculated as 1x7x6x5x1x3x2x1.

=> The general formula is (n-1)! / (n/2).

Sorry for my English not good.

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

Can someone please explain in problem E how we choose permutations as n!/(n/2)? (Sorry for the silly question)

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

In Problem E why we have to divide our answer by 2 ?

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

There is a simpler formula in Problem E. Since we need exactly different round dances, we can notice that all of them can be represented as permutations with a fixed first element (for example, with a fixed number 1 at the beginning). Then the number of such sequences will be (n-1)!, now we just need to divide this number by (n / 2) (I don't know exactly how to prove why this works, but it works XD).

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

Don't know why are you encouraging to find sequence on OEIS for E?It is bit surprising to see that

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

When will the changed rating be reflected in the account?

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

Can anyone help me to understand how to approach for problem F?

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

    In this dp problem, we are simply tracking the results on variation of every parameter(since constraints are low, seeing every possibility like Dr. Strange ;D).

    Firstly, we are traversing over every element in the matrix. Secondly, we are also traversing over all possible number of elements picked in a row. And also varying remainder of total sum. If a configuration with such properties (number of elements picked in that row and the total sum remainder) exists, $$$dp[i][j][cnt][rem]$$$ will have the max sum. Otherwise value will remain $$$-inf$$$.

    If you have solved dp problems before, you'll have an idea now. Otherwise, I urge you to practice basic dp problems, after which you'll solve this one.

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

In F , why the answer is stored at dp(n,0,0,0)?? Thank U

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

    dp[n][0][0][0] represents max sum, when we are at (n,0) [out of the matrix], i.e we have traversed the matrix and came out of it, with 0 elements picked in this row(obviously, because this row is not a part of the matrix), with the sum havin 0 remainder.

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

Это довольно стандартная задача на динамическое программирование. Пусть dp[x][y][cnt][rem] равно максимальной сумме, которую мы можем получить, если сейчас мы находимся на элементе ax,y, взяли cnt элементов в строке x и наш текущий остаток равен cnt (скорее всего хотели сказать rem).

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

Solution of problem G is giving compilation error given by you. Can you please recheck

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

I just spent whole 2 hours during the contest thinking on $$$F$$$ that $$$O(N^4)$$$ space solution won't work in $$$1$$$ second and wrote a $$$O(N^3)$$$ space + $$$O(N^4)$$$ time solution & kept debugging it till end and got AC when 7 minutes left. Yesterday i realised how bad i am at handling base cases in iterative dp.

Can anyone share how do they identify whether their solution will work or not when no. of operations & size of the array used is of the order more than ~10 million.

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

    in one second computer can do O(10^9) operations. since most of the times time limit is 1 second or 2 second you can do as below most of the cases. If an array is given the size of 10^5 . so you can apply o(N)(10^5) or O(NlogN) (10^5*log(10^5)) kinda algorithm in that cases. If array size is like 5000 somthing you can apply O(N^2) or maybe sometimes O(N^3) algorithm. if size~100 you can apply O(N^4) algorithm. So main thing is in one second you can do 10^9 operations keeping in mind , on seeing constraints calculate upper bound and think accordingly. And one thing is no of test cases. It should be also consider in taking time complexity. Hope this helps.

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

In G, if you use floyd with int values it will pass. But using long long is causing TLE.

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

There's a typo in the editorial of F. The current remainder is denoted by cnt instead of rem

»
4 года назад, # |
Rev. 4   Проголосовать: нравится -23 Проголосовать: не нравится

[DELETED]

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

    Asked for help only to get downvoted. What's wrong in asking for help politely :(

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

    Keep applying mod operation with function calls.

    I think this will be one of the easiest solutions of problem F to learn, I haven't use comments, but the code is clean though.

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

Has anyone seen more problems like F? Editorial says it's a standard DP.
Also, What are some other standard DP problems not commonly available?

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

In the problem F,

What happens when we initialize dp array with $$$0$$$ instead of INT_MIN or LLONG_MIN? I tried this and got wrong answer. But overall, the value of every state is going to become zero before we arrive that state during dp transition. So how does initialising values with zero go wrong?

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

    Never mind.

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

    int_min denotes that this state is impossible. If you initialise it as 0, you can distinguish between impossible states and states with sum 0.

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

      But, if the state is impossible, it will have 0 sum, as we won't be able to create an impossible state. Also, the minimum sum that can be created is 0, not $$$-inf$$$.

      You can check the Accepted submission, and the one with Wrong Answer. You can see, the code with zero initialised dp array creates a difference of 1 in the first testcase.

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

In problem E, why are we dividing by 2 in last step? Can Anyone explain in detail?

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

    Suppose we select n/2 members in first dance group and then the rest n/2 will automatically form the next dance group. But the formula here considers that the first n/2 and rest n/2 are 2 different cases. Hence we need to divide the value by 2 to make them identical.

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

    Every selection is accompanied by a rejection.
    For eg — S = {1, 2, 3, 4}
    There (6C2) ways to choose 2 elements. But suppose you select {1, 2} then {3, 4} is automatically selected. Now you don't want to select {3, 4} again and {1, 2}, because this will be counted twice. So to avoid counting again, we divide by 2.

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

    When we are taking C(n,n/2) we are counting how many ways we can take n/2 different elements from n elements.

    Let's say n = 1, 2, 3, 4, 5, 6, 7, 8

    we can take one round as (1, 2, 3, 4) and the other round will be (5, 6, 7, 8)

    we can take one round as (5, 6, 7, 8) and the other round will be (1 ,2, 3, 4)

    But both are the same configuration. So we are counting it twice, hence we need to divide the C(n, n/2) by two.

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

How much more time would be taken in reflecting the rating changes from this round 677? Or has the contest become unrated!?

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

Hello Everyone.... Can someone please explain why we multiplied with (n/2-1)! in E (two round dances) problem.

UPD : Solved

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

why does rating change for Div3 and educational rounds take sooooo long???

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

Can F be solved with a greedy solution???

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

    I don't think it can. I tried sorting every row, taking last m/2 elements and if the sum is not divisible by k than removing the element which difference from the previous in its row is the smallest, but this doesn't work. It also doesn't work if you simply try to remove the smallest element you find. So I don't think you can solve it with some kind of greedy.

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

      We could do it this way, sort all the elements then for each max val "a", get a max val "b" from any row such the (a+b)%k == 0 and number of numbers taken from rows of "a" and "b" is not more than m/2.

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

        It won't work, since it's possible for some "a", there does not exist "b" such that (a+b)%k==0 i.e, Cases where (a+b+c)%k==0, or sum of more number of elements will be div by k.

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

        I don't see how that would work. What if the number of elements you can take is not even. What if for example you can take only 4 numbers (2 from 2 rows) and you can't find pairs such that (a + b) % k == 0 but sum of all 4 is divisible by k 2 4 10 1 1 5 9 1 1 2 4 Here the answer would be 20 but your algorithm would not even find that. Also you would have to pay attention to how many numbers have you taken from which row. So I don't think that works

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

@vovuh start system testing so we can get our rating :P..

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

This contest is pretty easy. A speedrun is required like this contest.

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

for problem G, what is the disadvantage in this apporach: -> find shortest paths (not just lengths) for all delivery routes -> find the intersection paths among all and keep track of the largest weight -> set it to 0 then from the total cost , subtract , largest_weight*number_of_delivery_routes

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

    Your idea will fail in the 2nd sample. The largest weight will be 5 on the intersection paths but that's clearly not the edge we want to reduce to 0.

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

There is another way of thinking the partitioning of the given set in Problem E. Instead of dividing $$$\binom{n}{n / 2}$$$ by $$$2$$$, we can fix some arbitrary element, let's say $$$1$$$, and count in how many ways we can choose the other elements in $$$1$$$'s subset. That is $$$\binom{n - 1}{n / 2 - 1}$$$. This way, we don't have to worry about counting some configurations twice or more. And this idea can be applied in more complex recurrences involving set partitioning, like Bell Numbers, where the divide by $$$2$$$ thing won't work anymore.

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

vovuh there is a typo in F's Editorial, the first paragraph:

...., we took cnt elements in the row x and our current remainder is cnt.(this cnt should be rem)!

Thank you!

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

int idx = -1; for (int i = 0; i < n; ++i) { if (a[i] != mx) continue; if (i > 0 && a[i — 1] != mx) idx = i + 1; if (i < n — 1 && a[i + 1] != mx) idx = i + 1; }

In C ,I can't understand this iteration , can anybody please kindly explain this part ? or why does it work?

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

    This loop only looks at the largest elements because they can surely become dominant. For a pirana to be dominant it needs to have at least one pirana(left or right) that has smaller value. First if cheks for piranas on left. Second if cheks for piranas on right.

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

Wyh Dijstra work well in problem G?Is't it O(n^2 log m)?I think SPFA is faster.

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

When will ratings update?

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

dp[x][y+1][cnt+1][(rem+ax,y)%k]=max(dp[x][y+1][cnt+1][(rem+ax,y)%k],dp[x][y][cnt][rem]+axy)

I am not able to understand this transition. What does dp[x][y][cnt][rem]+axy exactly mean?

UPD : Understood. We are looking whether or not it is beneficial to take the current element or not.

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

vovuh What would be the Worst Case Time Complexity for the problem F using this DP approach.

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

Hi, for problem F, I submitted 2 codes.

One has dp array initialized to -1, other has it initialized to -2.

-1 works and gives Accepted but -2 doesnt.

Why so?

-1 => 96209145

-2=> 96263305

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

    memset(dp, -2, sizeof(dp)); does not do what you think it does.

    memset sets the value of every byte, not the actual element on the array. 0 and -1 works as intended because their binary representations have all zeroes and ones respectively.

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

      Ohhhhh..... thanks a lot. I understood now. so memset(dp, 5, sizeof(dp)) is also wrong?

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

        It's not "wrong", it will do what it's supposed to do- set all bytes to 1, 0, 1 continuously.

        It won't replace every elements with 5.

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

          oh so for array of bits of size 5 called dp, memset(dp,5,sizeof(dp)) will do-> 1,0,1,1,0 ??

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

            Bytes, not bits. So, every 8 bits of the array will be converted to 10100000.

            I'm not sure if that's reliable enough though.

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

    memset(dp, -2, sizeof(dp)); -2 is illegal, only 0, -1 or some Hexadecimal number like 0x3f3f3f3f

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

MyCode Can anyone help me? My code almost same as the standard solution, but get wrong answer on test 3

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

the tutorial for problem C is wrong for the example test case:

n=5; arr=[5,3,4,4,5];

resultant output=5 expected output=3

any helps regarding this?

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

    Both are correct!

    If the output is 5, 5 eats 4, 3, 2, 1.

    [5,3,4,4,5] -> [5,3,4,6] -> [5,3,7] -> [5,8] -> [9]

    If the output is 3, 3 eats 2, 4, 5, 1.

    [5,3,4,4,5] -> [5,5,4,5] -> [5,6,5] -> [5,7] -> [8]

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

96297177 code for F with comments

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

The problems were fine, but I don't think E is an appropriate problem, 2 reasons.

1)99% Math (Which is still fine, as most algorithm problems can be restated as Math problem, though this was a bit direct)

2) OEIS (I hate using OEIS, and I hate problems that allows to use OEIS, because there is literally no fun in it, and we don't learn anything new and you are caught when asked to do the same problem in onsite, but Div3 is a sprint race, when most of them use oeis and you don't, your rating suffers)

P.S. You don't even have to think of a few cases, you can copy paste 12164510040883200 in the OEIS search

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

    I have no problem with a little of combinatorics, but OEIS feels like cheating. And our friend 1000000007 would have easily done away with that.

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

If we are (i,j) then why are we taking the state dp[i][j+1]? Shouldn't we take dp[i][j]?

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

This is the second time I joined in the Codeforces contests. Such a nice one!

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

I don't understand why the answer is dp[n][0][0][0] in problem F

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

In problem F: The transitions from the last element of the row are almost the same, but the next element is a[x+1][0] and the new value of cnt is always zero.

Why cnt is equal to 0, even if we take the current element?

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

my solution for problem G is somewhat same as that given in the tutorial, however, I am getting TLE. any suggestion? link to solution — https://mirror.codeforces.com/contest/1433/submission/104609982