351F44's blog

By 351F44, 2 years ago, In English

Problem A is developed by mejiamejia.

1733A - Consecutive Sum

Hints
Solution
Solution Code
Challenge

1733B - Rule of League

Hints
Solution
Solution Code
Challenge

1733C - Parity Shuffle Sorting

Hints
Solution
Solution Code
Challenge

1733D1 - Zero-One (Easy Version)

Hints
Solution
Solution Code

1733D2 - Zero-One (Hard Version)

Hints
Solution
Solution Code
Challenge

1733E - Conveyor

Hints
Solution
Solution Code
Challenge
 
 
 
 
  • Vote: I like it
  • +124
  • Vote: I do not like it

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

Can someone explain/share the O(N) solution of task D2?

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

    If $$$x \geq y$$$, follow D1. Otherwise, for $$$x < y$$$, observe that for each mismatch, we can fix it by either performing a single $$$y$$$ operation with another non-adjacent mismatch, or we can perform a sequence of $$$x$$$-operations to either the next or previous mismatch. We can use a 1D DP as follows:

    $$$dp[i]$$$ represents the minimum cost for dealing with the first $$$i$$$ mismatches alone. If $$$i$$$ is even, then all mismatches should be fixed. If $$$i$$$ is odd, then $$$i - 1$$$ mismatches should be fixed while one mismatch remains. The $$$mis[]$$$ array stores mismatch indices.

    For even $$$i$$$, $$$dp[i] = \min (dp[i - 2] + (mis[i] - mis[i - 1])x, dp[i - 1] + y)$$$. We can fix the $$$i$$$-th mismatch through either an $$$x$$$-operation chain with the $$$(i - 1)$$$-th mismatch (first option), or through a $$$y$$$-operation with some earlier mismatch (second option).

    For odd $$$i$$$, $$$dp[i] = \min (dp[i - 2] + (mis[i] - mis[i - 1])x, dp[i - 1])$$$. Here, for the $$$i$$$-th mismatch, the first option is the same as before ($$$x$$$-operation chain with $$$(i - 1)$$$-th mismatch), but the second option is to let the $$$i$$$-th mismatch be the unresolved one. Note that $$$dp[i - 1] \leq dp[i - 2] + y$$$ (see even formula), so there is no need to consider using a $$$y$$$-operation for the $$$i$$$-th mismatch for odd $$$i$$$ (but it wouldn't change the result if this was added as a candidate).

    The last element in the $$$dp$$$ array (which must be an even index) is the answer.

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

      This is same as tourist solution.

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

      This solution looks more elegant!

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

      Very well explained, I understood it without trouble. This post should be in the editorial.

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

      Better than the editorial. Thanks!

  • »
    »
    8 days ago, # ^ |
    Rev. 4   Vote: I like it +15 Vote: I do not like it

    There is a solution with an $$$O(n)$$$ DP.

    For $$$x\ge y$$$ the solution is obvious (it's Problem D1), so I'll assume that $$$x<y$$$ then.

    First, pre-process $$$dif[i]$$$ which means the index of $$$i$$$-th difference between a and b.

    Let $$$f[i]$$$ be the minimum cost to make first $$$i$$$ differences became same. It's impossible when $$$i$$$ isn't even, so if $$$i$$$ is odd, $$$f[i]$$$ becames the minimun cost to make that there's only one difference in the first $$$i$$$ differences.

    Before we begin to solve, let $$$f[0]$$$ and $$$f[1]$$$ be $$$1$$$ first.

    Then, we can calculate $$$f[i]$$$ for all $$$i$$$ from $$$2$$$ to $$$n$$$ in order:

    If $$$i$$$ is even, $$$f[i]$$$ can be $$$f[i-2]+min(x\times(dif[i]-dif[i-1]),y)$$$. $$$f[i-2]$$$ means the cost when $$$dif[1\to i-2]$$$ are all solved, and $$$f[i]$$$ means the cost when $$$dif[1-i]$$$ are solved, so $$$f[i]$$$ need to add the cost to make $$$dif[i]$$$ and $$$dif[i-1]$$$ same.

    $$$f[i]$$$ can also be $$$f[i-1]+y$$$. $$$f[i-1]$$$ means the cost when there's only one difference in $$$dif[1\to i-1]$$$, and $$$f[i]$$$ means there's no difference, so it has to add the cost to make $$$dif[i]$$$ and $$$dif[j]$$$ same. Although we don't know the real $$$j$$$, we know the cost is $$$y$$$, because the condition that $$$j=i-1$$$ has already solve by the last paragraph, so we can assume that $$$j<i-1$$$.

    To sum up, the real $$$f[i]$$$ need to be the minimum cost between last two condition.

    When $$$i$$$ is odd, the reasoning process is similar. $$$f[i]$$$ can be $$$f[i-2]+min(x\times(dif[i]-dif[i-1]),y)$$$, or $$$f[i-1]$$$. You can try to independently calculate.

    Here is my code, you can refer to it.

  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Thanks for the explanation.

    I have seen another tricky solution: We will exclude the x>=y as we can solve it with D1 solution and the case where only 2 nearby mismatches( ans=min(2*y,x) ),

    (Option#1): So you will try to jump to any other mismatch with cost Y and goes to the next mismatch (dp[i] = dp[i+1] + y), I think this is valid because if you will take any mismatch with cost Y you will pair it with another mismatch.

    The problem with option 1 is calculating Y for every mismatch, so you have to count the number of mismatches taken by the first option and divide them by 2 , to avoid that, you can just multiply the second option (x) by 2 and divide the final solution by 2.

    (Option#2): The other transition is to chain with the next one(i+1) and transition to (i+2) so you solved i and i+1 mismatches with cost x*(mismatch[i+1] — mismatch[i+2]). option 2 is only valid if there exists (i+1<n). dp[i] = min(dp[i],dp[i+2] + x*(mismatch[i+1] — mismatch[i+2]))

    solution credits to IsaacMoris

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

    let v be the sorted vector of indices where a[i]!=b[i] (let size of v be vn) then the answer of the problem is f(0)

    where, cost(i,j)=min(y,|v[i]-v[j]|*x)

    f(vn-1)=y,f(cn-2)=cost(vn-1,vn-2)

    f(i) = min(((vn-i)%2)*y + f(i+1),cost(i,i+1)+f(i+2))

»
8 days ago, # |
  Vote: I like it +15 Vote: I do not like it

was this blog in 'draft' for 2 years?

»
8 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Hello Guys! For D2 I had this solution 172748609, I also don't no the reason that why its true.Can any one hack or say the reason behind it?

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

    First, we get all the positions which satisfy a!=b and save them in a new array C. Then we consider four positions which are adjacent in C. Let them be p1,p2,p3,p4 (p1<p2<p3<p4) . There is always min((p2-p1)*x,y)+min((p4-p3)*x,y)<=min((p3-p1)*x,y)+min((p4-p2)*x,y), which means that (p1,p3)+(p2,p4) can't be a part of answer. So you are right :)

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

Why do you say that a greedy solution does not work in D2. I think it's too bad that such tasks appear in the competition!

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

    Edited the phrase more clearly.

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

    LoL, what did u expect from the fifth problem?

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

      I'm pretty sure the post was to be interpreted with a "/s", considering the "not so unusual" hint (as it was before 351F44 edited it).

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

Hello guys, would really appreciate a little help with the B question. I thought that if we can make a combination with the 2 values of x and y that sums up to length-1 then we will get the right answer(was not sure so just tried). So I ran binary search between 0 and length-1 to search for the number of players that had x wins to find the answer and then print the player x times, but I got WA. here is the code:https://codeforces.com/contest/1733/submission/172718129 kindly guide me, thank you. EDIT:I found the error,it was a silly mistake in the printing part.THe code is working fine now. Code:https://codeforces.com/contest/1733/submission/172869494

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

    Binary search only works on monotonic searching space. Simple words, if x works either y > x or y < x should work. I am not sure how this problem is related to binary search. Maybe explain why you think binary search will do here.

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

      thank you for replying.Actually as i said in the post,I worked on the logic that if i can find a value k such that (k*x)+((length-k)*y) can form length-1(as we will have total wins as length-1) then we will have an answer. So the value of k can range from 0 to length-1. therefore to find that k i used binary search. I know I many have made some mistakes,therefore any tips are appreciated. Thank you

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

      Thanks a lot for your help. I had made a minor error in my code in the printing the other logic was correct. The solution do works correctly now. Code:https://codeforces.com/contest/1733/submission/172869494

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

    Take a look at Ticket 16198 from CF Stress for a counter example.

    This should help you figure out why binary search wouldn't work.

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

Does anyone have a solution for D2 using DP with memoization?

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

    You can check my solution: 172731715,

    The main part:
  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    you can see my solution of D2 using recursion+memoizatoin: https://codeforces.com/contest/1733/submission/172789187

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

    Let us say we have a vector of mismatched indices. We will be picking from this vector in pairs.

    In the DP, at any mismatched index, we have following options:

    • We can pair this index with the next mismatched index by continuously changing everything in between. Cost would be distance between mismatched indices multiplied by x.
    • We can pair with any previously unpaired index. Cost would be y.
    • We don't pair with anything, just create another unpaired index. It will need to be paired with later. Cost is 0 as we have not resolved anything.

    Here is my submission https://codeforces.com/contest/1733/submission/172860412

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

In D2(editorial), how is it possible to have $$$i+1$$$ ones in the first $$$i$$$ elements of $$$c$$$?

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

    i is correct. Now edited. Thanks for noticing me.

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

      I think there is one more problem with it.

      You recalculate dp for all $$$0 \le j \le i$$$, but in formulas where $$$c_i=1$$$ there is a condition $$$j=i+1$$$.

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

        Edited, thanks. There was some mistake while translating 0-based MCS into 1-based editorial.

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

What would be the expected rating of the first 2 questions?

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

    We estimated A as *800, B as *1000 or *1100. Let's wait.

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

      and C?

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

        I think *1500.

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

          Are you sure? I normally can't solve 1500s but C and even D1 were pretty solvable for me

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

            Same, I was guessing around 1300.

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

              Well, standing says it can be easier than *1500. It is what I estimated before the contest, maybe real difficulty is more easier? :/

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

                Yeah could be. Thank you for the contest tho! Great problems.

»
8 days ago, # |
  Vote: I like it +38 Vote: I do not like it

Great Problem E! Though its implementation isn't complicated, its idea is quite thought-provoking and requires insight. This is how CF problems must be. Truly nice problem!

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

If anyone feel that the editorial is too complex and you have solved longest palindromic subsequence or longest palindromic substring or https://codeforces.com/contest/1728/problem/D

Then see my submission for problem D: https://codeforces.com/contest/1733/submission/172855405

Very easy to understand and O(N*N) DP

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

My code for problem D2 is giving Time Limit Exceeded at test case 3, Please help me in optimising my Approach, suggest me with this intution only, please help.

ll f(ll i, string s, string s1, ll n, ll x, ll y,map<string,ll>&dp) {
    if(s==s1) return 0;
    if(i>=n) return 1e10+7;
    if(dp[s]!=0) return dp[s];
    if(s[i]==s1[i]) return dp[s]=f(i+1, s, s1, n, x, y,dp);
    ll p=(ll)1e10+7, q=(ll)1e10+7;
    for(int j=0;j<n;j++) {
        string s2=s;
        s2[i]=s1[i];
        s2[j]=='0'?s2[j]='1':s2[j]='0';
        if(j==i+1) p=min(p, x+f(i+1,s2,s1,n,x,y,dp));
        else p=min(p, y+f(i+1,s2,s1,n,x,y,dp));
    }
    return dp[s]=p;
}

void solve()
{
    ll n,x,y;cin>>n>>x>>y;
    string s,s1;cin>>s>>s1;
    map<string,ll>dp;
    ll ans = f(0, s, s1, n, x, y,dp);
    if(ans>=(ll)1e9+7) cout<<-1;
    else cout<<ans;
    cout<<ln;
}
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

hats off...!!

»
8 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Is the challenge for E solvable?

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

    I don't know.

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

    I think it's plausible. Consider the state of the conveyer after using exactly k slimes and look at each diagonal, regarding right arrow as 0 and down arrow as 1. For example, when k = 0, all conveyers have right arrows, so all diagonal's values are 0. When k = 1, all conveyers except the first row have right arrows, so all diagonal's values are 1.

    As k increases,

    1st diagonal's values are: 0, 1, 0, 1, ....

    2nd diagonal's values are: 00, 01, 11, 10, 00, ...

    3rd diagonal's values are: 000, 001, 011, 001, 101, 100, 110, 100, 000, ...

    4th diagonal's values are: 0000, 0001, 0011, 0111, 0011, 0001, 0011, 0111, 1111, 1110, 1100, 1000, 1100, 1110, 1100, 1000, 0000, ...

    It's not something I really proved, but it seems there's an obvious pattern here. I guess this pattern will allow us to find a path for k-th slime in O(N log k) for a N*N conveyer system.

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

I'm curious to know how to solve problem c challenge, any hints ?

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

A video editorial explaining the dp cases of D2 would be very helpful. Or maybe if someone can explain the cases here?

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

I think stress plays a lot of role during contests. I had a whole 1 hour and 22 mins. left to do problem C during contest but was not able to do it, today tried to upsolve it and solved it in 15 mins without looking at the editorial.

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

Please, share solution for Problem C challenge. Thanks.

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

    You can always make the whole array equal to the last element of the array in n-1 steps.

    First, apply the operation on the first and the last element. After this the first and the last element will become equal.

    Now just iterate through the array starting from the second element:

    Case 1. If the current element has the same parity as the last element apply operation to the current and the last element. This will make the current element equal to the last.

    Case 2. Otherwise, apply the operation to the current and the previous element. This will make the current element equal to the previous. But we know that the previous element is already equal to the last because we already iterated through it, so this will make the current element equal to the last.

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

      Oh! I see. So the editorial's solution of n-1 operations is the optimal solution. Thanks.

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

      This is the same solution as the orginal solution , however he asked about the solution of the challenge which asks to find minimum number of operations Test Sample : 2, 1, 3 according to your solution will cost 2 operations while the minimum cost is 1 operation we can apply the operation on second and third elements

»
7 days ago, # |
  Vote: I like it +13 Vote: I do not like it

Difference between E's solution I submitted in last two minutes and the AC solution

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

Hello, 351F44 can you please tell in the question D1 & D2, how you even have a intuition of starting with the XORs of both the binary strings a and b. At my last thought after so long I could only think of working on b trying making equalto a. But actually of no use because it's the same thing.

So how you even got the intuition of working on XORs of both the strings??

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

    It is one of the result of an observation. To do such observation, check if it can be transformed to be structurally identical.

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

There was an incorrect solution get accepted on D2 during the contest, and unfortunatly didn't get hacked. The idea was use range(or interval?) DP with some strange strategies to enumerate the decision. Code link

Hope to strengthen the data soon.

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

172746684 else cout << min((r — l) * x, y) << endl; isn't it redundant to check for the minimum?

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

any Recursive approach for D2?

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

For the problem E, is it possible to find out the periodicity of a particular roller in $$$O(1)$$$ time or precompute them after which we can simulate the process for the slime that arrived at $$$t-x-y$$$ in $$$O(x+y)$$$ ?

I don't have a concrete idea yet on how would one calculate the periodicity tho :( Any suggestions would be helpful! I feel one could exploit this to solve the challenge as well?

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

    So I tried to print the pattern of the state of each roller form t = 1 till t = 50 and 0 represents right and 1 represents down and in the beginning between {1,0} and {0,1} you see a good pattern. but in the diagonal (x+y = 2) There doesn't seem to be a pattern that is being followed, but there seems to be some similarity in {0,2} and {2,0} perhaps but {1,1} seems to show no similarity ? And when we try talking about the diagonal (x+y = 3) I can't spot any good pattern. So I'm skeptical of being able to find a pattern in the periodicity although I'm almost certain that the states of all rollers are periodic in nature.

    Pattern in the state of each roller
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

At E, I could think everything in time but the most important part, the simulation with x slime balls processes. How can I approach that process from the hints?

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

I wonder for D2, if we can just use DP to solve all the conditons? So if x>y, can we use DP instead of greedy algorithm? I try it, but got wrong answer.

#include<bits/stdc++.h>
using namespace std;
const int N=5010;
typedef long long ll;
ll z0[N][N],z1[N][N],c[N];
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _;
	cin>>_;
	while(_--){
		int n,x,y;
		cin>>n>>x>>y;
		string a,b;
		cin>>a>>b;
		for(int i=1;i<=n;++i) c[i]=a[i-1]^b[i-1];
		for(int i=0;i<=n;++i) fill(z0[i],z0[i]+n+1,1LL<<60);
		for(int i=0;i<=n;++i) fill(z1[i],z1[i]+n+1,1LL<<60);
		if(c[1]) z1[1][1]=0;
		else z0[1][0]=0;
		int d=min(x,y);
		for(int i=2;i<=n;++i)
		if(c[i]){
			for(int j=0;j<=i;++j){
				if(j) z1[i][j]=min(z0[i-1][j-1],z1[i-1][j-1]),z0[i][j]=min(z0[i-1][j-1]+d,z1[i-1][j-1]+y);
				z0[i][j]=min(z0[i][j],z1[i-1][j+1]+d),z0[i][j]=min(z0[i][j],z0[i-1][j+1]+y);
			}
		}
		else{
			for(int j=0;j<=i;++j){
				z0[i][j]=min(z0[i-1][j],z1[i-1][j]);
				z1[i][j]=min(z0[i-1][j]+y,z1[i-1][j]+d);
				if(j>=2) z1[i][j]=min(z1[i][j],z1[i-1][j-2]+y),z1[i][j]=min(z1[i][j],z0[i-1][j-2]+d);
			}
		}
		if(z0[n][0]!=1LL<<60) cout<<z0[n][0]<<endl;
		else cout<<-1<<endl;
	}
	return 0;
}
»
43 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

if the problem C ask us that they want to minimize the number of operation , how we can solve it ?

»
31 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain that in question B Rule of League, in sample test case 4 ans is 2 but it can also be 1 right. As this was stated there Each player has either won x games or y games in the championship. i can't understand it plz help.

5
5 2 0
8 1 2
3 0 0
2 0 1
6 3 0
  • »
    »
    27 hours ago, # ^ |
    Rev. 7   Vote: I like it 0 Vote: I do not like it

    yes , in test case 4 it can be 1 or 2 , both of them are correct . one of them won just one times and the second one won 0 times

    • »
      »
      »
      27 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      173387621 I have tried it but they say its wrong this is my submission.

      • »
        »
        »
        »
        27 hours ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        if(mi != 0) cout<<-1<<endl; but continue here to not complete after printing , you are wrong because you print extra -1 not because of whose the player

        • »
          »
          »
          »
          »
          24 hours ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks man that's a really rookie mistake.