Vovuh's blog

By Vovuh, history, 12 days ago, In English,

1256A - Payment Without Change

Idea: MikeMirzayanov

Tutorial
Solution

1256B - Minimize the Permutation

Idea: Vovuh

Tutorial
Solution

1256C - Platforms Jumping

Idea: MikeMirzayanov

Tutorial
Solution

1256D - Binary String Minimizing

Idea: MikeMirzayanov

Tutorial
Solution

1256E - Yet Another Division Into Teams

Idea: MikeMirzayanov

Tutorial
Solution

1256F - Equalizing Two Strings

Idea: Vovuh

Tutorial
Solution
 
 
 
 
  • Vote: I like it
  • +41
  • Vote: I do not like it

»
12 days ago, # |
  Vote: I like it +9 Vote: I do not like it

For Problem C,I imimplemented in O(n). 64249894

Main idea is like the tutorial:First place the platform as rightmost as we can ,if the rest positions can't place later platforms,we need move current platform to left.Maybe I am lucky enough to pass all tests.

»
12 days ago, # |
  Vote: I like it +34 Vote: I do not like it

Very Greedy Contest.

»
12 days ago, # |
  Vote: I like it +1 Vote: I do not like it

C in O(n). It's just placing the platforms leftmost you can at first. Got hacked for a simple mistake unfortunately. here 64283716

»
12 days ago, # |
Rev. 6   Vote: I like it +3 Vote: I do not like it

My solution for C is very simple $$$O(n)$$$ 64233289 Idea is following:

  • Set positions of all platforms with space in between exactly $$$d-1$$$. Just don't care about width of river.

  • Now, if beginning of next "virtual" platform is $$$n+1$$$ or greater, then answer is YES otherwise is NO.

  • Last step, we need to pack all platforms back into river. It's very easy to do. Let $$$n+1$$$ to be beginning of "virtual" platform, now iterate over all platforms from the last to the first, and if the platform overlap "virtual" platform, them align end of the platform to beginning of virtual platform. Now, set virtual platform to be this aligned (or not) platform and continue.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is awesome, thank you!

  • »
    »
    8 days ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    This is Python, Python is a very dangerous language, none of my colleagues think well of it

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Python is so dangerous that it will kill you at night

»
12 days ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

I think there is missing part of editorial for F.

Regarding case when all characters in both strings are distinct. Suppose that there is way to make them equal. It means, that if you apply all operations for first string instead of doing them simultaneously, and then apply all operations on the first string that was supposed for the second string in reverse order, you should get second string. In other words, steps to make the second string from the first string is: operations of first string in normal order plus operations on second string in reverse order. But count operations of same length is even, because each simultaneous operation produce two operation of same length. Thus, you need to change parity even times, which means no parity change is possible.

What I don't understand though, is how you can prove that you always can do that when parity is same. All I did is prove that you can't make it if parity is different.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    If the parity is the same, you can always do a swap twice in the same position in one string (making a no-op), while making two arbitrary swaps in the other.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    actually we can run a bubble sort algorithm in the case of distinct characters and count how many swap you needed to do. Let's say swap counts are p and q. if p and q has same parity, then we can perform (p -q) operation extra in the first string(let's say p > q). and we would do every operation twice in an interval to make the sorted string unchanged. if we have same parity, we can do that. else, we can't as we need to perform one last operation only once and that would change the sorted string.

    Sorry for my poor english.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Parity of swap count is changing. I didn't got this task during contest only because of that. After contest I've changed swaps count into inversions count and got AC. So, something is tricky there about it.

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Every swap changes the number of inversions by one. So they have same parity.

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh! Thanks, indeed. I found mistake. It was == 64254819 instead of = 64352150. So, I lost AC just because of that :)

    • »
      »
      »
      5 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for sharing~

»
12 days ago, # |
  Vote: I like it +2 Vote: I do not like it

In problem E, Why the maximum size of a team is 5??

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    For example,after sort we have a team: a1 a2 a3 a4 a5 a6

    if divide them in one team the diff is a6-a1

    if we divide them in two team the diff is a3-a1 + a6-a4

    as you know,a3<=a4 so the later diff is better.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if team size is 6 then you can split it into two. Thus minimize the ans.

»
12 days ago, # |
  Vote: I like it +2 Vote: I do not like it

it's hard to see when you have 11 correct hacks ( for the first time ) but still no hacking leaderboard Vovuh

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

from the solution of[problem:1256D] problem D can anyone explain what we do if s[i]=='0' but k<cnt?

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We will move the zero to the left as far as possible. Briefly we will swap it with the character to the left k times.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what does cnt denote ?

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      count of ones. see the solution given in the tutorial you will understand.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For question A, why do we need to do S % n? I mean what would we get by doing this? I know it would be quite basic but still, I didn't get it. Thanks in advance

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$S\ \%\ n$$$ = the amount of 1-value coins you need to get the exact number. Like, imagine if $$$S = 54$$$ and $$$n = 10$$$, that's like needing to make 54 cents out of 10-cent coins; you can't unless you have at least 4 1-cent coins.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't understand Then let's sort the second string also by swapping adjacent characters but choose the pair of adjacent equal characters in the first string (it always exists because the first string is already sorted). for problem F.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

You can solve E with segment tree & DP,but just DP solution is way more easier.

»
12 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
// simpler code for D
int main() {
    int q;
    cin >> q;
 
    while (q--) {
        int n;
        long long k; 
        string s;
        cin >> n >> k >> s;
 
        int p = 0;
        string ans(n, '1');
        for (int i=0; i<n; ++i) {
            if (s[i] == '0') {
                int bp = min(i+0ll-p, k);
                ans[i-bp] = '0';
                k -= bp;
                p++;
            }
        }
 
        cout << ans << endl;
    }
}
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone give better solution of B.tutorial is not clear

»
12 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

problem c

i tried to find the required number of gaps(i.e. 0) in answer then found per gap(0's) between two planks by (total gap/(m+1))and made a contigous plank within the gaps.but its not working . can anyone help? https://codeforces.com/contest/1256/standings/friends/true#

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I think Problem B can be solved in $$$O(n)$$$, it's too late at night to code it though

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah i did in O(n)

  • »
    »
    12 days ago, # ^ |
    Rev. 8   Vote: I like it 0 Vote: I do not like it

    Here's my code for $$$O(n)$$$: 64340316

    Explanation
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain problem E with an example ?

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is O(n) solution for problem C: 64232235

Approach
»
12 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

$$$O(n)$$$ solution for C: I didn't put the board greedily. I tried to break the gaps between the boards evenly.

My Submission: 64221433

»
12 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem F, How does one get an idea to consider the parity of inversions ? I mean it is not at all obvious to me . If this is a popular idea , can someone give some problems related to it ?

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E , how would we approach if we have to minimise the number of teams as well?

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You would combine all consecutive teams into one team where it does not make a difference in the diversity. ie the ones where the score of the highest member of the team is one less than the score of the lowest member of the next team.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E. help help me... My code is a little different from the offcial solution, but I think they are roughyly the same. However, it is TLE. Here is the central part of my code.

for(int i = 2; i < min(5, n); i++) { dp[i].first = wd[i].first — wd[0].first; dp[i].second = i + 1; }

int len = 0;int temp = 0;
for (int i = 5; i < n; i++)
{
    if(dp[i - 3].first + wd[i].first - wd[i - 2].first < dp[i - 4].first + wd[i].first - wd[i - 3].first) 
    {   len = 3;    temp = dp[i - 3].first + wd[i].first - wd[i - 2].first;}

    else
    {   len = 4;    temp = dp[i - 4].first + wd[i].first - wd[i - 3].first;}

    if(temp > dp[i - 5].first + wd[i].first - wd[i - 4].first)
    {   len = 5;    temp = dp[i - 5].first + wd[i].first - wd[i - 4].first;}
    dp[i].first = temp;
    dp[i].second = len;
}
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I got a detailed prove for F. Regarding case where the characters of both string are distinct. let's consider the pair in string a, a(i) > a(j) and i<j, and there are t characters between them, so it's easy to know that we need 2*t+1 times swap to get a(i) and a(j) swap while keeping others unchanged(t+1 for a(i) to reach j, t times for a(j) to reach i), so the cost is always odd. if we have parity of the number of inversions odd in both string, then we can say both need odd times to get the string sorted, and the difference between two times if even, also we can always do even times adjacent swap and keep string unchanged, finally two strings become the same. and so the even situation.

»
11 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

for the problem B the first testcase is $$$[5 4 1 3 2]$$$

My approach is:

$$$[5, 4, 1, 3, 2]$$$
$$$[5, 1, 4, 3, 2]$$$
$$$[1, 5, 4, 3, 2]$$$
$$$[1, 5, 3, 4, 2]$$$
$$$[1, 3, 5, 4, 2]$$$

and the answer is [1, 5, 2, 4, 3], but clearly my answer is lexicograhically smaller, so anyone can tell me where is the problem?

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is mentioned that for a particular index i you can swap only once. For i=2 you can swap (4,1) after that you cannot swap number at position i=2. i.e.(5,3)

    Second paragraph of question: " You can perform at most n−1 operations with the given permutation (it is possible that you don't perform any operations at all). The i-th operation allows you to swap elements of the given permutation on positions i and i+1. Each operation can be performed at most once. The operations can be performed in arbitrary order. "

»
9 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

a more general solution for E:

  1. sort by skill
  2. let dp[i] = minimum diversity that we can do starting at index i
  3. then dp[i] = min(dp[k+1] + a[k] − a[i]) for all k, such that i + 2 <= k <= n − 4
  4. since a[i] is independent of k, dp[i] = − a[i] + min(dp[k+1] + a[k]) for all k, such that i + 2 <= k <= n − 4

if we want to implement this it would take o(n^2), but we can notice something by looking at dp[i + 1]

dp[i+1] = − a[i + 1] + min(dp[k + 1] + a[k]) for all k such that i + 3 <= k <= n − 4

thus dp[i] = − a[i] + min(a[i + 1] + dp[i + 1], a[i + 2] + dp[i + 3])

the idea is that dp[i+1] would already have the minimum for all k >= i + 3, so we only need to test for k = i + 2 and then compare it with dp[i +1] + a[i + 1]

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Your text to link here...

I have some problem in D.I think my code is correct and the error message seems useless。

»
8 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Challenge B question: Why is it p = [4, 5, 1, 3, 2] not considered as a correct permutation for q = [5, 4, 1, 3, 2]? There is i = 0 where p[i] < q[i]. Exactly the same we have in the correct permutation p = [1, 5, 2, 4, 3]

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because in p = [4, 5, 1, 3, 2] p[0] equals 4, and in p = [1, 5, 2, 4, 3] p[0] equals 1. 1 < 4 hence the latter permutation is correct.

»
8 days ago, # |
  Vote: I like it -11 Vote: I do not like it

Why do such easy contests take place when I'm not there?

»
7 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem A, if the values are as follows :- a=5,n=2,b=3 and s=9 Then we cannot give the exact change amount, but by going through the solution in the editorial it prints YES. Isn't it that the solution fails in this case ??

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In fact we can. Take 4 coins by 2 (from a coins), it is 8. And then 1 coin by 1 (from b coins) and we get 9 in total

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If a =5 and n=2 then it means that we have 2 coins of denomination 5 each. How can we take 4 coins by 2 (as suggested by you). Correct me if I am wrong.

      • »
        »
        »
        »
        7 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Please double-check the task, it says that a is the number of coins and n is the value of each coin.

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help me??? in binary string minimisation it shows runtime error out of bounds

include <bits/stdc++.h>

define ll long long

using namespace std; int main() { int t; cin>>t; while(t--) { int l,k; cin>>l>>k; string s; cin>>s; int arr[l]; for(int i=0;i<l;i++) arr[i]=1; int j=0,v; for(int i=0;i<l;i++) { v=i; if(s[i]=='0') //--------> error out of bounds { if(i-j<=k) { arr[j]=0; k-=(i-j); j+=1; } else { arr[i-k]=0;

break;
            }
        }

    }
    for(int i=0;i<l;i++)
    {
        if(i<=v)
        cout<<arr[i];
        else
        cout<<s[i];
    }
    cout<<'\n';
}

}

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1256/submission/64739565 Can't figure out, where is the mistake?