awoo's blog

By awoo, history, 4 years ago, translation, In English

1400A - String Similarity

Idea: BledDest

Tutorial
Solution (adedalic)

1400B - RPG Protagonist

Idea: adedalic

Tutorial
Solution (adedalic)

1400C - Binary String Reconstruction

Idea: Roms

Tutorial
Solution (Roms)

1400D - Zigzags

Idea: adedalic

Tutorial
Solution (adedalic)

1400E - Clear the Multiset

Idea: Roms

Tutorial
Solution (Roms)

1400F - x-prime Substrings

Idea: BledDest and Roms

Tutorial
Solution (pikmike)

1400G - Mercenaries

Idea: BledDest and Roms

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

| Write comment?
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Editorial for E is not visible, can you please fix it.

»
4 years ago, # |
Rev. 3   Vote: I like it -18 Vote: I do not like it

You can see nothing

»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it

In the contest page, the tutorial link redirects to neal's blog of Unofficial editorial. Maybe you should add this blog as tutorial, and neal's blog as extra tutorial.

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Any similar problems like B for practice ?

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can someone explain what's wrong with my solution for B?

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

    You aren't checking the cases when Follower can't pick enough items because Protagonist didn't leave for him. You are running two loops totally exclusively, but in reality they aren't mutually exclusive, and instead, dependent on each other. x swords picked by protagonist means Follower is only left with s-x and he has to choose from them.

»
4 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Can someone give a binary search approach to problem B, I am not able to implement it, and not getting the function that can be used to find different numbers satisfying the given condition i.e x*(no_of_swords) + y*(no_of_war axes) <= p(or f), or this can't be implemented? Thanks a lot in advance!!

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

    You mean problem B? LINK

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

      Can you explain this please

      you are doing r=mid-1 for first BS l=mid+1 for second BS

      Why not together? How did u come up this unique in time of contest??

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

        Basic idea : There are 2 people : me and my follower. I will brute force on the number of $$$swords$$$ that I take, binary search on the number of $$$swords$$$ my follower takes, and there will be some space left for both of us, we will use that to take as many $$$axes$$$ as we can.

        Problem with binary search : While doing binary search transition to the left or right is the most important thing. In our code $$$mid$$$ represents the number of $$$swords$$$ my follower is trying to take at this moment. If he can't take that much obviously he will try to take less, hence $$$r = mid-1$$$. If he can, then which direction you go next time? You try to take more swords and do $$$mid = l+1$$$, or do you try to take even lesser swords and do $$$r = mid-1$$$? We don't know. That is why I just decided to do both in separate binary searches.

        Doing it in one binary search : Do we try to take more swords or less? Actually we know the answer. If the weight of a sword is greater than the weight of an axe, taking more swords only reduces your chance of getting more items. So a simple greedy will allow you to do it in one binary search. LINK.

        It's just in contest I instantly had the idea of doing 2 binary searches so I just sticked with it.

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Roms awoo In Problem E, what is the meaning of "closed", "open", "unclosed" operation?

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

    The operations of the first type are applied to some segments. An "unclosed" operation means that we have started a segment corresponding to some operation of the first type earlier, but haven't finished it yet. To "open" an operation is to start a segment, to "close" it is to end a segment.

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

      So what does it mean to "close" some operations of the second type and "open" a new operation of the second type?

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

i cannnot understand the DP solution to problem E, can somebody help me ?

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

    In case you need other solution than DP.

    Consider a range [l,r].

    For first type of operations: Consider an index x (l<=x<=r) such that a[x] is minimum in that range. If we apply the first operation a[x] times, then each element would be reduced by a[x]. And a[x] becomes 0. Now we can break this range in two parts [l,x-1] ans [x+1, r] and do the same thing.

    When there is a 0 in the range.
    When there are multiple indices whose values are minimum in the range

    For second type of operation: We can delete all elements in this range in no more than r-l+1 operations of second type.

    Code : 91083858

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 11   Vote: I like it +14 Vote: I do not like it

      Problem E . explain the Tag "DP & sorting"

      Now i've get the process by checking out the top div.1 programmer jiangly's solution. It's an implement of The line chart .

      At first, assume the second option is banned .

      This problem == CF1392C — Omkar and Waterslide.

      it indicates that when we go up from the (i-1)th positon to the (i)th position, the new cost =the difference betweem a[i-1] and a[i] ,formally,** a[i]-a[i-1]**. when we go down from the (i-1)th positon to the (i)th position, the new cost =0;

      now consider the second option, it means we can change the num in ith position,(the raw a[i]) to any num less than or equal to a[i], the cost=(new_num<a[i]?1:0)

      note that though we can change a[i] to any new_num<=a[i], but only the n+1 number {0,a[1],a[2],a[3]...a[n]} is effctive. and we sort_unique them to ** m different numbers.**

      denote dp[i][j] as : ** on the ith position of array a[], the cost of the process of 0.1.2....i,** after which we change the number to the jth biggest number(same number not inclusive) in array {a[],0};

      dp[n+1][0] is the answer ,(we make a[n+1]=a[0]=0,then the restrict "all num==0" is matched )

      and then we implement the dp process. simple implement can be O(n^3)

      consider MAX_N==5000;

      we Change the form of the raw dp equation, and use suffix minimum , preffix minimum,the O(n^2) solution can be implemented.

      reference material https://codeforces.me/contest/1400/submission/90933891

      jly&&EI 99

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

      For the second type of operation, you are considering r-l+1 operations but if there are already elements with zeros what about them. Shouldn't we just count the number of non zero elements and use that instead. Or Maybe that case is handled by recursion?

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

        If there is a 0 in range [l,r], then the range would be divided into two without using any operation. Read the first spoiler.

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

      Why does greedy work?

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

In problem B, why we should take at first min(s,w)?

»
4 years ago, # |
Rev. 7   Vote: I like it -24 Vote: I do not like it

Problem D: Can anyone please tell me what is wrong with my solution? it is not working for this test case:

30

28 30 29 29 30 30 29 30 30 30 30 28 28 28 28 29 29 28 29 29 29 30 29 29 30 28 30 30 28 29 expected : 2618 received output : 41212

#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i,n) for(int i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define PI 3.1415926535897932384626
typedef pair<int, int>	pii;
typedef vector<int>		vi;
typedef vector<pii>		vpii;
typedef vector<vi>		vvi;

int n,c;

void solve() {
  cin >> n; int a[n];
  int lef[n+1] = {0}; 
  int rig[n+1] = {0};
  fo(i, n) cin >> a[i];
  c = 0;
  
  for (int j = 0; j < n; j++) {
      for (int k = n - 1; k > j; k--) {
          c += rig[a[j]]*lef[a[k]];
          rig[a[k]]++; 
      }
      lef[a[j]]++;
      fo(i,n) rig[i] = 0;
  }
   cout << c << "\n";
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
      solve();
    }

    return 0;
}
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    fo(i,n+1).... in the loop where youre clearing the rig array...

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

In problem E answer does not exceed $$$n$$$ because we can use $$$n$$$ operations of the second type so we can consider second parameter up to $$$n$$$.

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

For people interested, 3b1b-styled visual editorial for D. Zigzags this time with narration and as always, with visual dry-run of a testcase.

»
4 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

after reading editorial i feel D was easy i don't know what i was thinking during contest.

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

After seeing the MOD value for problem G, I was wondering, where/how FFT should be applied here. :)

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

I loved this contest, specially the problems D, E and F, learned a lot of thouse!! DP with Aho-Corasick blow up my mind but after understand it was awesome!!

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

    Can you please explain the DP part(see below) of problem F x-prime substring?

    forn(i, s.size()) forn(j, trie.size()) 
    	  if (dp[i][j] != INF){
               dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
               int nxt = go(j, s[i] - '1');
               if (!trie[nxt].term)
                  dp[i + 1][nxt] = min(dp[i + 1][nxt], dp[i][j]);
              }
    
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry, I didn't understand the autor's solution, I write my own recursive approach that think is easier to understand [http://codeforces.me/contest/1400/submission/91095834](my solution) PD: Also my Aho-Corasik is another implementation

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

        I hand run your code for the input s = '116285317' and x = 8. I was to able to understand finish and cnt array, but can you please explain the "out" and "link" arrays as they both remain zero for the aforementioned input? I know how Aho-Corasick algorithm works and it would be great if you could relate out and link arrays to equivalent arrays used in the Aho-Corasick link provided would really help me. Can you provide a better input(than mentioned at the top) which can make your solution more clear to me?

        Thank you!!!

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

          Sure, these are the values that stores each array of my Aho-Corasik implementation:

          cnt[n] -> amount of words that end in node n
          finish[n] -> id of the word that end in node n (not important in this problem)
          fail[n] -> suffix link of node n
          out[n] -> end word link of node n (also not important in this problem)
          

          As you can see the BFS named buildf() calculate these values, so ALL possible transitions of the automaton are calculated beforehand.

          Hope this help you...

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

            Thank you Johnny. I have drawn a trie(see below) for 8 prime set (5,3) (3,5) (8)

            xprimed2b930d3445b77c4.jpg

            Suffix link of every vertex is 0 except vertex 4 with suffix link 1 and vertex 2 with suffix link 3. Please correct me if I am wrong.

            When I ran the code for same input s = '116285317' and x = 8, I get :

            Fail[4] = 1 which is perfect.

            My question is why fail[2] = 0 ? Is it because in original string we have substring '53' and not '35'?

            I thought fail[2] should equal 3.

            May I know why you have taken MAXN=1e5+5 ?

            Again thanks Johnny for your time.

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

              Man I just ran my code and got fail[2] = 3, don't know why you got 0. Anyway my advice is focus in the dp instead of the Aho-Corasik implementation (I've used it many times and it works fine to me, but you can use whatever you like)

              PD: The MAXN is just a value large enough, nothing special...

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

                Oh ok. Glad to hear that. It must be a manual error(as I hand run the code) by me. I am so sorry about that.

                The dp part looked magical at first but breaking it into smaller steps really helped.

                Finally, I got it.

                I have learnt a lot from this problem.

                I don't know how to thank you.

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What language are adedalic's solutions written in?

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

*****************Why a O(2n) code getting TLE in problm C****************

Can anyone tell me please why this submission 90966915 is showing TLE? It was accepted till final standing and after final standing I've submitted the same code in offline also & which was accepted, see here 91082748. I can't understand whats wrong with me. advance thanks. awoo Roms

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

    91117140

    I copy-pasted your submission 91117140 and it ran in $$$1918 ms$$$ and then I submitted it again with some comments and got TLE on test 7 91117335.

    Basically your code is slow because of the for loop you make to ans+='0'.

    Instead, using resize makes it run on $$$31 ms$$$.

    You got lucky that your code got accepted at all after the contest. These are minor fluctuations in judging time say ~$$$150ms$$$. Your code is basically slow.

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

      I was unable to identify the bug. thanks for your cooperation. But I've a little bit more to know. If you tell me some more details why ans = ans + '0' in the loop makes my code slow? Isn't it happening in O(n) time complexity? antontrygub

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

        When adding (concatenating) strings (and almost any object) using the + operator, each operand is copied, after which they are summing and the result is copied to ans. So O (ans.size()) for each addition, due to copying. If you use the += operator, then only the right operand will be copied, push_back works the same way, it will work in O (1) on average.

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

if the edge <= 10 I will solve it...

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

worst contest ever

»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Yet another solution for G:

There will be at most $$$2m$$$ nodes with nonzero degree, let's call this set of nodes $$$V'$$$, and let $$$k = |V'|$$$. We'll take this part of the graph and solve it independently from the rest. Namely, for each $$$s \in [1..n]$$$, we'll find the subset $$$V_s \subseteq V'$$$ such that these are exactly the nodes $$$v$$$ for which $$$l_v \leq s \leq r_v$$$. For each such subset, we can use meet-in-the-middle and sum-of-subsets DP to calculate, for each $$$j$$$, the number of ways to choose $$$j$$$ independent nodes from $$$V_s$$$, and then multiply this with the corresponding binomial coefficient $$$\binom{z_s-|V_s|}{s-j}$$$, where $$$z_s$$$ is the number of nodes $$$x$$$ satisfying $$$l_x \leq s \leq r_x$$$ in the whole graph. Fortunately, over all $$$s$$$, there can only be $$$2k$$$ different values of $$$V_s$$$, so we do the second phase only a small number of times. Also the sum-of-subsets DP of the first phase needs to be done only once.

Code

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

In problem G, how to calculate $$$c_s$$$?

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

    The cnt array serves that purpose in the editorial code.

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

      Thank you very much. But the tutorial didn't mention it. I hope the author can add this to the tutorial.

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

During solving this round, I understood that problem 1400E - Clear the Multiset is similar to 448C - Painting Fence. It's just rephrasing of the problem statement.

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

    But we should notice that: when the input is: 1 0 the output should be 0,instead of 1 This is why I was hacked when I submit the same code as what I submitted in the 448C.

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

In Problem F, how about the string 2222222232222222232...(1000 characters long)? Doesn't it have about 1000 19-prime substrings, each with length 9? Their total length would then be about 9000. What is wrong here?

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

    I thought the total length <= $$$5000$$$ remark is discussing the set of all possible distinct $$$x$$$-prime strings, and not the multiset of all $$$x$$$-prime substrings of the input or anything of that sort. But that can't be the case, as it is easily calculated with a small dp that there are $$$2399$$$ distinct strings which are $$$19$$$-prime, and their total length is $$$13739$$$. But the Trie generated from the $$$19$$$-prime strings still only has $$$4853$$$ nodes, because many prefixes are shared among those strings, and it is this number that determines the number of values of $$$y$$$ and the state space of the dp.

    A short Haskell program that calculates these numbers
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You're right. I misunderstood the remark. Thanks for the explanation!

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

There is a small typo in problem G (the factor of $$$(-1)^{|E|}$$$ is missing from the summation) . Other than that, it is a very nice writeup :)

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

With exact same approach as C, but using Java is giving me TLE. Anything I have missed to optimise? Any solution? My submission: 91120981

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

    Instead of filling w with -1, fill it with 1. Update it's value only when you need to, i.e. when s[i]=0 and you have to make w[i-x] and w[i+x] 0. I copy/pasted your code and made these changes and it got accepted!

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

In zigzag the explanation should be i<j(l>k), right?

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

I am not able to understand the DP solution of problem E, can somebody help me ?

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

In problem E, I have implemented a recursive solution where I compare the second operation ($$$r - l + 1$$$) with applying the first operations — subtracting minimum value of the range which splits the range into possibly multiple ranges with all positive elements and recursing further into those ranges. It passed all tests with 202ms in Java and implementation-wise, it's quite easy. I'm wondering if it's the tests were weak or the solution in practice runs faster. Anyone can reason about the complexity? Here's my solution.

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

    The complexity is correct.Every time you visit the solveForAny function,the segment(l,r) is split into at least two parts.In the end,there are no more than n segments,so the total number of visits is no more than n.So the total complexity is O(n^2).You can refer to the blog,there's a clear explanation in it.

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

Can someone help me with Question D, its giving me TLE on the 6 test case but i am not able to find where i am going wrong, even though my code almost matches the editorial. my code

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

I can't figure out when will the answer be "-1" in C. Can anyone help me out please?