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

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

1400A - Похожие строки

Идея: BledDest

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

1400B - Главный герой RPG

Идея: adedalic

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

1400C - Восстановление бинарной строки

Идея: Roms

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

1400D - Зигзаги

Идея: adedalic

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

1400E - Очистите мультимножество

Идея: Roms

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

1400F - x-простые подстроки

Идея: BledDest и Roms

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

1400G - Наемники

Идея: BledDest и Roms

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

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

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

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

i found that cf problems are often shorter ... lol

Nice explanations!

How detailed it is, upvoted!

»
4 года назад, # |
Rev. 3   Проголосовать: нравится -18 Проголосовать: не нравится

You can see nothing

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

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 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Any similar problems like B for practice ?

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

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

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

    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 года назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You mean problem B? LINK

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

      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

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

    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

    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 года назад, # ^ |
      Rev. 11   Проголосовать: нравится +14 Проголосовать: не нравится

      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.com/contest/1400/submission/90933891

      jly&&EI 99

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

      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

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

      Why does greedy work?

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

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

»
4 года назад, # |
Rev. 7   Проголосовать: нравится -24 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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 года назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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

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

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

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

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

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

        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 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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 года назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What language are adedalic's solutions written in?

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

What language are adedalic's solutions written in?

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

*****************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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

worst contest ever

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

    The cnt array serves that purpose in the editorial code.

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

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

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

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.

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

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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