BledDest's blog

Educational Round 110 — Editorial
By BledDest, history, 4 years ago, In English

1535A - Fair Playoff

Idea: BledDest

Tutorial
Solution (Neon)

1535B - Array Reodering

Idea: BledDest

Tutorial
Solution (Neon)

1535C - Unstable String

Idea: BledDest

Tutorial
Solution (Neon)

1535D - Playoff Tournament

Idea: BledDest

Tutorial
Solution (Neon)

1535E - Gold Transfer

Idea: adedalic

Tutorial
Solution (adedalic)

1535F - String Distance

Idea: BledDest

Tutorial
Solution (BledDest)
  • Vote: I like it
  • +83
  • Vote: I do not like it

Comments Comments (43)
| Write comment?
»
4 years ago, # |
  Vote: I like it +42 Vote: I do not like it

The round was really educational. thanks!

→ Reply
»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Solution to problem c was much simpler . Just use basic DP . Here's my solution ->

ll dp[n+1][2];

    dp[0][0] = 0;
    dp[0][1] = 0;
    ll ans = 0;
    for(ll i = 1 ; i <= n; ++i){
        if(s[i-1] == '?'){
            dp[i][0] = dp[i-1][1] + 1LL;
            dp[i][1] = dp[i-1][0] + 1LL;
        }else if(s[i-1] == '0'){
            dp[i][0] = dp[i-1][1] + 1LL;
            dp[i][1] = 0;
        }else if(s[i-1] == '1'){
            dp[i][1] = dp[i-1][0] + 1LL;
            dp[i][0] = 0;
        }
        ans += max(dp[i][0] ,  dp[i][1]);
    }

    cout << ans << endl;
→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +18 Vote: I do not like it

    Without DP Time Complexity — O(N) Space Complexity — O(1)

    int main() {

    int tc;
cin>>tc;
while(tc--)
{
    ll i,c1,c2,f,ans;
    string s;
    cin>>s;

    c1=0; c2=0;
    f=0; ans=0;
    for(i=0;i<s.length();i++)
    {
        if(s[i]-'0'==f || s[i]=='?')
            c1++;
        else
            c1=0;
        if(s[i]-'0'==1-f || s[i]=='?')
            c2++;
        else
            c2=0;
        ans+=max(c1,c2);
        f=1-f;
    }
    cout<<ans<<endl;
}

return 0;

    }

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am trying to solve the problem C with dp ,but unable to solve. Can you explain how you came up with the solution. What is the logic for dp relation?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The logic for dp is such

      If character at ith index is '0' you can't do anything but take transition from previous index's '1' that is dp[i-1][1] where dp[i][j] stores the number of valid substrings if the ith index ends with j (0 or 1).

      Similarly the same has to be done if the ith index is '1'

      Now if the ith index is '?' you would want the the alternating string ending at '?' to be as huge as possible therefore u pick dp[i — 1][0] or dp[i — 1][1] depending which is bigger.

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    why so many down votes! It's such a good soln.

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

    Can be solved with 1D dp as well 238914676

    → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can u explain it

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

    why aren't you taking the if(s[i-1] == '?'){ dp[i][0] = max(dp[i - 1][0], dp[i-1][1] + 1LL); dp[i][1] = max(dp[i - 1][1], dp[i-1][0] + 1LL); }. because, you might get better answer by replacing it with the last character ???

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +42 Vote: I do not like it

I accidentally solved a harder version of problem E where you're given not a path from $$$v_i$$$ to the root in the second query type but ANY vertical path. I think it might be fun for you to solve if you're interested.

UPD: Oh yeah, btw, I can modify this solution a little bit so that it works not only for vertical but for arbitrary paths.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -13 Vote: I do not like it

I Loved problem D, the first time I got a chance to use Segment tree in a CF contest and the editorial also good. Thanks to the team behind the contest.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You already commented the same before ¯_(ツ)_/¯

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Both posts are regarding the same contest and the same problem so I think it's fair to post the same comment.

      → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Thanks for such an interesting contest! I really enjoyed the problems, especially B and C. Actually, I think problem A was a little bit too easy in comparison with the last contest. I hope the next contest will be more and more exciting! :)

→ Reply
»
4 years ago, # |
  Vote: I like it +109 Vote: I do not like it

I have a solution to problem F in $$$O (n * m * log n)$$$ (where $$$m$$$ is the length of the string). Similarly to the author's, we split strings into equivalence classes. We only need to quickly calculate the number of pairs of strings with a distance equal to 1. Divide each string into the minimum number of blocks so that the characters in each block are sorted. Note that for the string $$$s[i]$$$ this partition is unique and is specified only by those positions $$$j$$$, where $$$s[i][j] < s[i][j - 1]$$$. Suppose we have two strings $$$s1 < s2$$$. Note that we can sort in $$$s2$$$ only a segment nested in some block in $$$s1$$$. Then, in fact, we can expand this segment to the size of the block. That is, for each block $$$[l, r]$$$ in $$$s1$$$, we need to find the number of such $$$s2$$$ so that if we sort the segment $$$[l, r]$$$ in $$$s2$$$, then $$$s2$$$ becomes equal to $$$s1$$$. Note that in this case $$$s1[:l-1]$$$ = $$$s2[:l-1]$$$ and $$$s1[r + 1:]$$$ = $$$s2[r + 1:]$$$. Let's iterate over $$$l$$$ for the equivalence class and split into new equivalence classes by prefixes of length $$$l$$$. Now, note that if some block $$$[l, r]$$$ of string $$$s[i]$$$ begins in $$$l$$$, then we need to find out the number of such $$$s[j] > s[i]$$$ in the new equivalence class $$$s[i]$$$ that the length of the common suffix $$$s[i]$$$ and $$$s[j]$$$ $$$> = m - r$$$. This is easily done by simply sorting all the reversed strings and doing a binsearch using a sparse table on the lcp array. Further, going through the strings in descending order, add 1 to their position in the new array, for beginning of the block find out the amount on the segment using any convenient data structure.

My submission — 118431979.

P.S. If you don't understand something, ask questions. Sometimes even I don't understand myself.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    "Let's iterate over l for the equivalence class and split into new equivalence classes by prefixes of length l"

    How do you split into new equivalence classes ?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Strings $$$s1$$$ and $$$s2$$$ in the same new class, if the length of their common prefix is ​​at least $$$l$$$ and their multisets of characters are the same. Therefore, when incrementing $$$l$$$ by 1, you only need to create subclasses using the character at position $$$l + 1$$$ (numbering from 1).

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Can you explain about vector<vector<int>> to(m, vector<int> (sz)) in your code?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      $$$to[j][i]$$$ — the number of the equivalence class of $$$s[i]$$$, if $$$l$$$ (which I described earlier) is equal to $$$j$$$. It is not hard to see that the equivalence classes form segments in the sorted array of strings.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it 
    vector<vector<int>> bup(sz, vector<int> (lg, -2));
        for(int i = 1; i < sz; ++i) {
            int a = ord2[i];
            int b = ord2[i - 1];
            while(rs[a][bup[i][0]] == rs[b][bup[i][0]]) {
                bup[i][0]++;
            }

    I wonder what this initiation means. Isn't this -2 out of bound?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      lol really. You are right, this is out of bound. :) I was lucky that there was no RE.

      → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I think I found an easier solution to problem B (I am not saying it is faster — just easier). There's simply no need to move the even numbers to the beginning, just check for each pair (i < j) if __gcd(a[i], 2 * a[j]) > 1 or __gcd(a[j], 2 * a[i] > 1.

Here is my submission: 118428074.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

my submission = https://mirror.codeforces.com/contest/1535/submission/118565398

pls help me. I can't find the reason of runtime error

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 4   Vote: I like it +8 Vote: I do not like it

    try to rewrite your cmp function like this Link

    this is a common RTE mistake you can search on CF,some blogs has been written about this

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

MikeMirzayanov, I just got a message that my solution Kal-El/118413234 for 1535C coincides with low_profile/118412998,K0000/118413793, shakeitbaby/118414205, O_BhosDiwale_ChaCha/118414232, madarakaguya1234/118414304, XENOX_GRIX/118417732, codeforcesalt11/118418351, yash_agarl_/118423400

I think this is either coincidence(I used a simple 2 pointer approach for it) or the people mentioned above are indulging in cheating. I have never indulged in leaking my solution or copying someone else code (you can have a look at my profile to confirm it), and looking at the timestamps it is clear that I did not copy paste someone else code.

If u look at template of my other submissions on Codeforces it is similar to my submission for 1535C but for the people mentioned above their code style is not same as their submission for 1535C. I do not know how they got access to my code or was it just a mere coincidence.

I sincerely participated in the contest and it is a humble request to you to not skip my submissions for the contest.

→ Reply
»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Can anyone tell why my solution for problem B giving TLE

ll gcd(ll a, ll b){ if (b == 0) return a; return gcd(b, a % b); }

int main(){

ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int t;
cin >> t;

while(t--){
    ll n;
    cin >>n;
    vector<ll> v;
    ll a[n],h=n-1,ans=0;
    for(ll i=0;i<n;i++){
        cin >>a[i];
        if(a[i]%2==0){
            ans+=h;
            h--;
        }
        else{
            v.push_back(a[i]);
        }
    }
    for(ll i=0;i<v.size()-1;i++){
        for(ll j=i+1;j<v.size();j++){
            if( gcd(v[i],v[j]) > 1){
                ans++;
            }
        }
    }
    cout<<ans<<"\n"; 
}

return 0;

}

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for(ll i=0;i<v.size()-1;i++){

    Since v.size() is unsigned that loop can run very long.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What data structure has the model solution used in the solve_short() function in the last problem? Is it Aho Corasick or something similar?

→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it -34 Vote: I do not like it

ok

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    If o is empty, then o.size() - 1 will evaluate to 2^64 − 1 since size_t is unsigned.

    → Reply
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Trying to implement something "smart" in F I accidentally got Accepted with "stupid" $$$O(n*n)$$$ (or even $$$O(n*n*m)$$$) solution. After removing all unnecessary trash it has only several lines of code: 118716718

In particular it uses the following code:

	rep(i, n) rep(j, i)
		ans += ...;

where $$$n$$$ — the size of a current equivalence class.

It seems C++ is too fast :) and, probably, the tests do not cover the worst case for this solution. Also please note, that all string are different, so the maximum size of an equivalence class is $$$200000/8 = 25000$$$.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In python 3.8 i used my own implementation for gcd (mod euler) and it got time limit exceeded using the math.gcd method it got accepted.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem 1535C - Unstable String Can anyone explain is it necessary for a beautiful string to contain the character ? ? Also how does 0?10 has 8 beautiful substrings ?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    0, ?, 1, 0, 0?, ?1, 10, ?10 are the 8 beautiful substrings in the first sample test case

    And no, it is not necessary for a beautiful string to contain the '?' character. A better description of a beautiful string in my opinion would be closer to something like "The string is already unstable or can be made unstable through switching all '?' characters to '1's or '0's".

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      0, ?, 1, 0, 0?1, ?10, 10, 0?10 are beautiful substrings , you wrote some substrings wrong!

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for question B, i got TLE for https://mirror.codeforces.com/problemset/submission/1535/126669391 this submission but the same was done afterwards, it got accepted, https://mirror.codeforces.com/problemset/submission/1535/126670783 Can anyone explain the behavior of Codeforces here??

→ Reply