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

Автор awoo, история, 2 года назад, По-русски

1989A - Поймай монетку

Идея: BledDest

Разбор
Решение (awoo)

1989B - Подстрока и подпоследовательность

Идея: BledDest

Разбор
Решение (Neon)

1989C - Два фильма

Идея: BledDest

Разбор
Решение (Neon)

1989D - Кузнечное дело

Идея: BledDest

Разбор
Решение (adedalic)

1989E - Расстояние до различных

Идея: BledDest

Разбор
Решение (BledDest)

1989F - Раскрась одновременно

Идея: BledDest

Разбор
Решение (awoo)
  • Проголосовать: нравится
  • +96
  • Проголосовать: не нравится

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

Fast tutorial

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

Interesting problemset

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

For problem D I kind of simulated the process by brute force, submission: 267758186

Notice that

  • if crafting and smelting cost $$$a_i - b_i$$$ of 2 kinds of weapons is equal, then it's never better to craft a weapon with a higher initial material cost $$$a_j$$$
  • if crafting and smelting cost $$$a_j - b_j$$$ of one kind of weapon is greater, it can only be useful to craft it if its material cost $$$a_j$$$ is lower

In my solution I simulate the process by going from lower operation cost $$$a_i - b_i$$$ and higher material cost $$$a_i$$$ to higher operation cost and lower material cost. On each step remaining metals with amount of ingots $$$c_k \lt a_i$$$ are useless for me, and any metals with $$$c_k \geq a_i$$$ will be reduced to metals with remaining quantity less than $$$a_i$$$, but at least $$$b_i$$$.

I was expecting this solution to get hacked or fail system tests, but somehow it's still standing (although I've seen some similar solutions getting hacked). After pondering on why did it not get TLE, I realized that each unique remaining value of $$$c_k$$$ will be considered at most once, and since there are at most $$$10^6$$$ unique values of $$$c_k$$$ the total time complexity will be amortized.

This solution is a result of me gaslighting myself that there are no more than $$$O(\sqrt{max(a_i)})$$$ unique differences $$$a_i - b_i$$$ (which is obviously not true).

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

    I did exactly the same, also waited to be hacked and then understood..

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

    can you please explain why you were able to use each value of ck atmost once? also, why does using lower_bound work here, shouldn't you use maximum amount of ingots for the best case (minimum difference)

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

      Let's go over from a brute force solution to a more optimized one step by step:

      • Iterating over all kinds of weapons and then for each weapon iterating over all kinds of ingots is $$$O(N \cdot M)$$$

      • Now let's group different kinds of ingots with the same remaining quantity together, since if you can calculate the amount of xp for a single kind of metal with remaining $$$c_k$$$ ingots, you can do the same for $$$X$$$ kinds of metals with $$$c_k$$$ remaining ingots. You could store counts in an array or in a map. Since there could be $$$M$$$ unique values of $$$c_k$$$ you still would be iterating over all kinds of metals, leading to $$$O(N \cdot M)$$$ complexity

      • Now get rid of the values which we cannot smelt anything from, on each step it's useless to consider values $$$c_k$$$ lower than $$$a_i$$$, this is where lower_bound comes in. Also notice that after each smelting operation all values $$$c_k \geq a_i$$$ will get mapped to some values strictly less than $$$a_i$$$. Picture it like this: you pick the largest $$$a_0$$$ first, you erase all values $$$c_k \geq a_0$$$, then you pick second largest value $$$a_1$$$ and erase all values $$$a_1 \leq c_k \lt a_0$$$, so on and so forth. In total you will not iterate over more than $$$max(a_i) = 10^6$$$ unique values of $$$c_k$$$ (probably even less under given constraints).

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

    I did what you stated in 267754245, but it got hacked :( Could anyone tell me what I missed in my solution?

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

    yeah, i also do the same thing and waited to be hacked. As the blogger said, this complexity is hard to think through on the field. But as long as we find this similar to the monotone queue optimization DP property, coupled with memory search, it is easy to amorize the complexity. If you were a hack, you would have to make each a minus b different and find a number, and then take the remainder of each of these A minus b's different, which is obviously impossible to do.

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

Detailed Video Editorial | English Language

B : https://youtu.be/izeasCQM6Mc

C : https://youtu.be/K9Lj5WFtwXc

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

Can anyone explain me why lcs was not working in problem B I was able to solve but still confused where it could have gone wrong

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

    lcs does not work because as per the question we need to find the longest contiguous substring of b that occurs as a subsequence in a. for example if a="ab" and b="sasb" the lcs is "ab" with length 2 but as we can see it is not useful for us as in our final string there must be a 's' between 'a' and 'b'. the answer string would be "sabsb" with length 5.

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

    Actually you needed to find the longest contiguous substring of b that occurs as a subsequence in a. It can be done using LCS algorithm only, it just need 1 little modification in the else part. Instead of finding max(dp[i — 1][j], dp[i][j — 1]), we can do this

    for (int i = 1; i <= n; i++) 
    {
        for (int j = 1; j <= m; j++) 
        {
            if (a[i - 1] == b[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1];
            else dp[i][j] = dp[i - 1][j];
        }
    }
    for (int i = 1; i <= m; i++) mx = max(mx, dp[n][i]);
    
»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +1 Проголосовать: не нравится

I don't understand, why not use greedy for values ​​of x <= A in D?

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

I calculated the string using a bruteforce. It seems to be missing a testcase. What is it that I am missing in this: https://codeforces.me/contest/1989/submission/267683386

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

problem B test case sample can drive you insane they can work with any wrong algorithm you come up with

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

As usual, BledDest blesses us with high-quality problems!

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

Are D tests weak? My solution uses memoization with a vector of maps and passes in 2.8 seconds. My solution relies on the fact that if the net costs are very high or very low, then all of the metal is expended quickly. For this reason I think the worst case would be on the order of O(log n sqrt(max) n)? Submission: https://codeforces.me/contest/1989/submission/267939272

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

tried solving B using dp, why doesn't it work?

https://codeforces.me/contest/1989/submission/267759332

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

    Actually you needed to find the longest contiguous substring of b that occurs as a subsequence in a. It can be done using LCS algorithm only, it just need 1 little modification in the else part. Instead of finding max(dp[i — 1][j], dp[i][j — 1]), we can do this

    for (int i = 1; i <= n; i++) 
    {
        for (int j = 1; j <= m; j++) 
        {
            if (a[i - 1] == b[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1];
            else dp[i][j] = dp[i - 1][j];
        }
    }
    for (int i = 1; i <= m; i++) mx = max(mx, dp[n][i]);
    
»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

For people why LCS is not working for problem b actually you needed to find the longest contiguous substring of b that occurs as a subsequence in a. It can be done using LCS algorithm only, it just need 1 little modification in the else part. Instead of finding max(dp[i — 1][j], dp[i][j — 1]), we can do this

for (int i = 1; i <= n; i++) 
{
    for (int j = 1; j <= m; j++) 
    {
        if (a[i - 1] == b[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1];
        else dp[i][j] = dp[i - 1][j];
    }
}
for (int i = 1; i <= m; i++) mx = max(mx, dp[n][i]);
»
2 года назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

F can be solved by using the well-known Radecki algorithm

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

For problem D i have written same solution as given in tutorial but it is giving TLE on test case 9

267975922 can anyone justify?

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

Can anyone tell me how to do B by graphs?

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

Appreciate the Todd Howard reference in Q4

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

Hey can someone give me a case for which my solution fails My solution — a.size + b.size — longestCommonSubsequence(a,b)

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

Amazing editorial of D!!!

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

Was it intentional that O(nlogn) solutions of D Fail or is my implementation just garbage? python code

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

In question C. Can I not do dp here. Like checking for all the possibilities and then taking the most appropriate solution.