SashaT9's blog

By SashaT9, 7 months ago, In English

We thank everyone who participated in the round.

1968A - Maximize?

Author: SashaT9

Hint 1
Hint 2
Hint 3
Solution
Implementation
Rate the problem

1968B - Prefiquence

Author: FBI

Hint 1
Solution
Implementation
Rate the problem

1968C - Assembly via Remainders

Author: SashaT9

Hint 1
Hint 2
Hint 3
Solution
Implementation
Rate the problem

1968D - Permutation Game

Author: FBI

Hint 1
Hint 2
Solution
Implementation
Rate the problem

1968E - Cells Arrangement

Author: SashaT9

Hint 1
Hint 2
Hint 3
Solution
Implementation
Rate the problem

1968F - Equal XOR Segments

Author: SashaT9

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Implementation
Rate the problem

1968G1 - Division + LCP (easy version)

Author: SashaT9

Hint 1
Hint 2
Solution
Implementation
Rate the problem

1968G2 - Division + LCP (hard version)

Author: SashaT9

Hint 1
Hint 2
Solution
Implementation
Rate the problem
  • Vote: I like it
  • +93
  • Vote: I do not like it

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

any good resources or blogs to explain Z-function?

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I was thinking too complex at the problem D

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

Can someone make clear how did the first question really work, I mean I thought about doing it in the same way as you've explained but I saw that some of the test cases doesn't work by that implementation on the test cases 1000 => 750 and on some other test cases, how please???

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

    It says to print out any possible(maintaining the statement) value of y. so printing out 750 or 500 or even 999 will be allowed in this case.

»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Should Problem B be just a 2 pointer problem with a time complexity of O(min(a, b))?

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

    Yeah,that is one of the possible solutions. However, it is easier to explain the dp solution)

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

There exists an $$$\mathcal{O}(n \log^2 n) $$$ solution with a very good constant factor for G2, reply to this if interested.

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

    I just thought of one too. Does it involve sorting and parallel binary search?

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

      You don't need any of that. You could simulate what you do in G1 with a set/segment tree by iterating over the lengths, and it works. The time complexity came from harmonic series and the log from DS.

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

        There also exists an O(n log n) solution using DSU.

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

      Not sure what “parallel binary search” means, but it is nested binary search. I don't sort anything.

      Basically, we still have our nice $$$z$$$ function, however, we will also store an RMQ which can get the maximum value of $$$z_i$$$ for all $$$i$$$ in a range $$$[l, r]$$$.

      Let's precompute the value $$$mx_i = \text{maximum number of disjoint substrings with length } i, \text{which are all equal to the prefix of length } i$$$

      If we want to check if $$$k$$$ disjoint substrings are possible with $$$\text{LCP}$$$ $$$l$$$, we just check if $$$mx_{l} \ge k$$$.

      Now the problem is the computation of $$$mx$$$.

      For length $$$i$$$, there can be at most $$$\frac{n}{i}$$$ disjoint substrings with that length. Let's use the fact that $$$\sum_{i=1}^{n}\frac{n}{i}=\mathcal{O}(n \log n)$$$.

      Using our RMQ, we can, instead of calculating $$$mx_i$$$ in linear time in the length, we can calculate it in $$$\mathcal{O}(mx_i \log n)$$$, simply binary search on the next $$$j$$$ such that $$$z_j \ge i$$$ (here, we binary search and use a sparse table to get this next $$$j$$$ in $$$\mathcal{O}(\log n)$$$, alternatively, you can walk on a segment tree in $$$\mathcal{O}(\log n)$$$).

      The complexity of this computation is $$$\sum_{i=1}^{n}mx_i\cdot \log n = \log n \sum_{i=1}^{n} mx_i \le \log n \sum_{i=1}^{n}\frac{n}{i}=\mathcal{O}(n \log^2 n)$$$

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

Can somebody tell how to do G1 using KMP? I don't know KMP well enough to manipulate it.

»
7 months ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

FOR G2: answer f(x) is decreasing function, so i just modified simple binary search solution for G1, by just changing the upperlimit as previous answer.
Code: 259245908
I am not able to prove this tho... please help me.

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

Thanks for your brilliant problems! Round was fun enough to spend full competition time just solving the problem.

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

Can anyone explain why Sasha is the winner in the second test of problem D?

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

    k -> 8; pb — 2; ps — 10 path -> 3 1 4 5 2 7 8 10 6 9 score-> 5 10 5 1 3 7 10 15 4 3

    If both play optimally: Bodya sticks to his current position. Score -> k*score[i] -> 10*8 -> 80 Sasha moves the highest score possible and sticks there. Score -> 3+4+7+10*(15*4) -> 84

    Thus, Sasha is the winner. I hope you understand:)

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

Can someone please tell me what's the rating of problem D? I'm asking because the rating is not updated on the problem tag.

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

For B: Optimise Answer

void solve() {
    int n, m; cin >> n >> m;
    string a, b; cin >> a >> b;
    
    int j = 0;
    for(int i = 0; i < m; i++) {
        if(a[j] == b[i]) j++; 
    }

    cout << j << endl;
}
»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Made video editorials for C,D,E for whoever wants to refer

C : https://www.youtube.com/watch?v=oEx5rR4wAKw

D : https://www.youtube.com/watch?v=XBUN4LwolEM

E : https://www.youtube.com/watch?v=DObsk_Rlhg8

language => Hindi

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

In problem F, my submission 259182179 has been hacked. But I resubmit it and got AC... Could anyone tell me why???

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

    Testset hasn't been updated yet, all AC solutions will be retested during some hours with updated tests

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

    Your resubmission will soon give WA verdict after system testing. In current System's all testcases are those that were during the contest [where u got AC]. Now, all the testcases that could hack other's solution, will be added in the System testcases[including the testcase that could hack ur F no. solution] and System test will run again. Then, u will get a different verdict.

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

    Uphacked as per your wish :) now it should be automatically added to the tests already.

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

      :((((((((((

      btw, is other solutions (259304100 and 259314753) hackable?

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

        259304100: Probably yes 259314753: No

        It's all about smashing unordered_map, you can check the generator I used once system test is done.

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

    fine... new submission has been uphacked :(

    i should use map replace unordered_map

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

G1/G2 can be solved without any fancy algorithms as in my rust solution in C++ too: 259314092

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

    My G1 C++ submission was the same but it was hacked

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

    CAN YOU explain how it works

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

      Count number of non-overlapping occurrences of prefix of length lcp in s. Then binary search lcp, then cache it, then find ans for every k in $$$[l..r]$$$.

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it -7 Vote: I do not like it

    I also solved G1 without using any string algorithm during the contest, but after main tests I got TLE :(

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

      And TLE in main test:(

      We may use kmp or hash or other algorithm to search a substring in $$$O(n+m)$$$ time, and a simple brute force can become $$$O(nm)$$$ in the worst cases.

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

        Yes, the built-in find in c++ is too slow for it.

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

          Yes. Also, what is funny is that your solution that passes on G2, doesn't pass on G1. They probably forgot to add the same test case on G2 and no one hacked it.

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

            I assumed G2 includes all tests from G1, but then checked it on G1 and finally got my TLE :)

            Interesting that Rust uses Two-way matching and passes easily. The same algorithm is said to be used in std::strstr, I tried it: 259358346 and it doesn't even pass G2.

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

            Just bc G1 had TL 2sec when G2 had 3sec. I'll remember this for next contests :(

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

              That's not the root cause, for sure. G2 AC in 1.7sec: 259346859 (while doing much more work) and exactly same code TLEs in G1: 259347015

              I think it's ok that simpler problems have lower time limit.

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

        Doesn't kmp takes overlapping patterns into consideration as well? How to remove that?

»
7 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Is this solution for G2 hackable? Using two heurestics:

1) Memoising the value of cnt calculated in f(mid)

2) Since the answer always decreases on increasing k, keeping the value of hi from previous k(not setting it to n again).

Not able to proove it's time complexity.

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

    I have done the same thing, and I was able to prove the complexity to some extent. It's easy to see that my code is $$$\mathcal{O(n\cdot\text{number of distinct values of } mid})$$$.

    First let's assume $$$l=1$$$ and $$$r=n$$$, the binary search ranges are $$$[1,n],[1,\frac{n}{2}],\dots,[1,\frac{n}{n}]$$$.

    The main observation is this, the range $$$(\frac{n}{2},n]$$$ is exposed to $$$1$$$ binary search, the range $$$(\frac{n}{3},\frac{n}{2}]$$$ is exposed to $$$2$$$ binary searches. Similarly, the range $$$(\frac{n}{i},\frac{n}{i-1}]$$$ is exposed to $$$i-1$$$ binary searches.

    It is clear that with this, we have a very loose upper bound of $$$O(n\cdot\sum_{i=2}^{n}\min((i-1)\cdot\log(n), \frac{n}{i-1}-\frac{n}{i})$$$. However, as i said, this is very loose, as the sum $$$\sum_{i=2}^{n}(i-1)\cdot\log(n)$$$ is quite a bit more than $$$n\cdot\log(n)$$$ (the total number of checks).

    We can make this tighter.

    Let's consider the ranges $$$1$$$ by $$$1$$$, first we have the range $$$(\frac{n}{2}, n]$$$. We have $$$2$$$ cases, the first case is that $$$\log(n)$$$ is smaller than the range, in which case (for the sake of an upper bound), we should assume that we take all the $$$\log(n)$$$ checks from that range, becuase we will never see that range again, so it is best to take as much as we can from that range, hence decreasing the number of times the other ranges can be chosen by $$$\log(n)$$$.

    However, if the range length is less than $$$\log(n)$$$, then all the next ranges are also smaller than $$$\log(n)$$$. So in fact, a better upper bound is $$$\mathcal{O(n\cdot\sum_{i=2}^{n}\min(\log(n),\frac{n}{i-1}-\frac{n}{i}))}$$$, this value is $$$733800000 \approx 7\times 10^8$$$ for $$$n=2\cdot 10^5$$$.

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

      The point where the minimum changes from $$$\lg n$$$ to $$$n/(i-1)-n/i$$$ will be $$$i\approx i_0=\sqrt{n/\lg n}$$$, so this analysis gives a runtime bound proportional to around $$$n\cdot ((n/i_0)+(\lg n)\cdot i_0)=2 n \sqrt{n \lg n}$$$.

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

Can someone please explain D as why greedy works. like can't a player stay at position for more than 1 time and then move to next one to get best answer. Its's confusing to think that he will move only by staying once or either staying all rest of left moves on that positions.

Won't it also depend on array A's elements as to loose some chances in low points in pursuit of bigger points to get maximum answer.

i still can't get how greedy gets right answer

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

    If you move from your current position cur to another position nxt then It should be a[nxt]>a[cur], else it's optimal to stay at your current position.

    I hope you understand.

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

      Yeah I get it now. I was stuck on dp approach making it complex and wasn't able to think greedy.

      Thanks

»
7 months ago, # |
  Vote: I like it -16 Vote: I do not like it

第四题出的太好了

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

For G2 there is also solution using the problem:

-we can deactivate an element

-we need to find the closest active element to the right

That can be done using dsu

Then we'll increase lcp. When we increase it by one, we deactivate elements, so we're left only with elements with $$$z_i \ge curLCP$$$ where $$$z_i$$$ is z-function.

To find maximum $$$k$$$ that can achieve at least $$$curLCP$$$ we will start at the beginning and then jump to the next active element of $$$i + curLCP$$$. Since the answer for $$$curLCP$$$ is at most $$$\frac{n}{curLCP}$$$, $$$O(ans)$$$ solution works in $$$O(n log n)$$$, and dsu gives us either $$$\alpha(n)$$$ or $$$log n$$$

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

In G2, shouldn't the time complexity of the case when $$$k > \sqrt{n}$$$ be $$$\mathcal{O}(n \sqrt{n})$$$? (the editorial says it's $$$\mathcal{O}(n \sqrt{n} \log{n})$$$)

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

    I agree. The total complexity is ($$$n\sqrt{n}\ logn$$$), but when $$$k>n$$$,it works in ($$$n\sqrt{n}$$$).

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

    Thanks, fixed:)

»
7 months ago, # |
  Vote: I like it -8 Vote: I do not like it

approx. rating of G2? 2100+ right?

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

For G2 I had a similar idea to use the fact that the answer only changes a few times and I calculated the answer for each segment with new n/l.

However, this got WA, not sure why, so I replaced it with an O(n*log^2(n)) (please someone correct me if I'm wrong).

You first binary search for the leftmost index with an answer less than the last one.

Here's the submission 259255876

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

    It TLE'd on the general test. :(

    shouldn't O(N log^2 (N)) <= O(N sqrt(N))

    I'll try analyzing the complexity and if someone can correct me...

    1- Calculating the Z function is done in O(N)

    2- Then there's the check which is also O(N)

    3- Both binary searches are log(N)

    4- is there a sqrt(N) I'm missing maybe?

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

    My friend had an $$$O(n \log^2{n})$$$ solution that ACed (which I believe uses a similar idea to your $$$n/l$$$ thing), if you wanna check that out.

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

      I don't quite understand tbh. if you could explain it to me please... unforgettablepl

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

        In my code, the calc function is pretty much the same as the check function in your code. The got variable in your code stores the maximal k such that the answer is >= len. In my code, the calc function returns the got variable. Now I make an array called ans where ans[i] = maximal k such that the answer is >= i using this function. For answering queries I just binary search over this answer array.

»
7 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Use hash to check whether two string equal again.

And be hacked again (((

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

    I used hashing too, but I wasn't hacked since I used mersenne twister to randomly select mod for hashing.

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

      Can you share your hashing template?

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +4 Vote: I do not like it
        mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
         
        struct Hash {
            int n;
            string s;
            const ll p = 31;
            ll mod = uniform_int_distribution<int>((int)(1e9+7), (int)(1e9+1e8))(rng);
            vector<ll> pw, hash;
         
            Hash(string _s) : s(_s) {
                n = s.size();
                pw.resize(n+1);
                hash.resize(n+1);
                pw[0] = 1;
                for(int i=1; i<=n; i++) pw[i] = (pw[i-1] * p) % mod;
                hash[0] = s[0] - 'a' + 1;
                for(int i=1; i<n; i++) hash[i] = (hash[i-1] + pw[i] * (s[i] - 'a' + 1)) % mod;
            }
         
            ll getHash(int l, int r) { return (hash[r] - (l ? hash[l-1] : 0) + mod) % mod; }
         
            bool equal(int l1, int r1, int l2, int r2) {
                if(r1 - l1 != r2 - l2) return 0;
                if(l1 > l2) swap(l1, l2), swap(r1, r2);
                return (pw[l2-l1] * getHash(l1, r1) % mod) == getHash(l2, r2);
            }
        
            bool isPal(int l, int r) {
                return equal(l, r, n-1-r, n-1-l);
            }
        };
        

        Here you go.

        Also be aware that the function isPal only works if the to the string is appended its reverse.

        For example, let's say we will call isPal for the string s = "cabad".

        To chech is substring from "aba" is palindrome, you have to initialize the hashing structure with the string "cabaddabac"

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

          Does this line returns a prime number?

          ll mod = uniform_int_distribution<int>((int)(1e9+7), (int)(1e9+1e8))(rng);

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

            No. It return random integer in the range $$$[10^9+7, 1.1*10^9]$$$.

            The mod doesn't need to be a prime number.

»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Why such tight constraints on G2, $$$n \leq 2\cdot 10^5$$$ when the intended time complexity is $$$O(n\sqrt{n}log(n))$$$??

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

    There is (in my opinion) easier $$$O(n log^{2}n)$$$ solutions too.

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

Hey,

  1. G2 is solvable in O(NlogNlogN): checking the maximum number of intervals one can separate in such that the common prefix has length at least k is doable in O(N/k logN) if we store the valid indices with Z[i]>=k in a set.

  2. Can someone understand why the solution to F gives TLE if we use unordered_map<int,vector > instead of map<int,vector >? My solution using unordered_map was TLEd in the main tests, and the official solution has the same issue when we use unordered_map. This seems unintuitive as we never use the key ordering.

Thanks!

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

    For the 2nd point, I think even from the main tests have some exploits on unordered_map to cause enough hash collisions for $$$\mathcal{O}(n)$$$ access. It's been a common exploit for quite a while, and it's due to hash table's nature itself, as long as its hashing could be reverse engineered.

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

now I get it

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

Is there any tutorial for that Z function used in G1?

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

Can anyone refer me more problems like E?

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

    Check out constructive algorithms

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

      of what range?

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

        Range? I’m not sure what you mean.

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

          Problem rating like 1600-1700?

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

            There’s a wide range of difficulty for constructive algorithms, so I’m not sure what to suggest. Just choose the difficulty range you would normally do, I suppose?

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

why do we usually use a segment tree for finding xor on segments and not just how it was described in the problem f? or we just do this only when elements don't change?

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

    Correct. We can do prefix XOR to evaluate range XOR in case that there are no updates (That is, no change). But if there are updates, then we use a Fenwick or segment tree.

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

      how can we use segment tree pls tell??

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

        In the same way how it is used for sums, but you change each node to store the XOR of the interval instead.

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

I think there's an error in the editorial for problem F. It says "we may find the largest t <= r" but it should be t < r since if t == r then the segment [t+1, r] would not make sense. I tried a solution with this change in mind and it got AC. 259369531

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

Looks like I have to practice more to recognize patterns in problems like in E!

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

For Problem C, if we want to find the lexicographically smallest sequence $$$a_1, a_2, a_3, ..., a_n$$$ what would be the approach?

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

Anyone has an idea why this one gets TLE https://codeforces.net/contest/1968/submission/259216131 ? it is exactly the same complexity as the editorial solution.

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

On problem F i am not convinced with the solution , can anyone provide with a better approach here , because i see the statement that

Observation: any division on more than k>3 segments can be reduced to at most 3 segments. Doesn't hold the biequivalence , that if the segment can be divided into atmost 3 segments then it can be divided into k segments

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

    The equivalence is not needed, we simply require that k > 1.

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

    We are only required to show an injection in one direction. I think we can't show bijection here, because it is not always true, that we may divide from $$$3$$$ segments up to $$$k$$$.

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

Easy observation solution for E. Put two dots at (1,1) and (n,n) One dot at (2,1). and the remaining(n-3) on the first row starting from the third column. The intuition behind this is to get all possible Distances for N >= 4. To get all distance I first choose (1,1) and (n,n) which gives distances 0 and 2*n-2. then put one at (1,2) to get the distance of 1 and 2*n-1. We can get the remaining in pairs if we put them on the first row. for ex- (1,3) will give distance 2 and 2*n. and so on for (1,4), (1,5) ... .

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

could someone please explain the bfs solution for problem D, also what will be maximum number of steps to reach a cycle in a permutation of length n where we move from a random number x in permutation to permutation[x] 1 indexing similalry moving forward

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

    In a permutation of length n, the max number of steps to reach a cycle is always n.

    example : 4 3 1 2

    Here, whatever starting position you had, you will need to perform 4 moves to end up at the starting position

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

      for 3 2 1 and if you are at 3 you go to p(3) that is 1 and then p(1) that is 3 it took only two steps right

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

I have a general doubt, on how to build a constructive approach + thinking in problems like E. I generally find it difficult to find a pattern. So in general what should be my approach while tackling such problems. (Ig having the right intuition at the beginning is very important.) If possible please do suggest me something on this :)

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

    (Disclaimer) I haven't solved E since lack of time. I think everyone has it since there is no generalisation in such problems :) What I find helpful for myself is to look into the properties of data structures and operations used in problems. For example, it's clear u can get max Manhattan distance by putting cells into corners. It gives u unique combination and also a range of all possible distances. Than u can see, that putting cells into the lines/diagonals gives u lots of other combinations since u have more unique values in the formula. The hardest part is to notice that u lack some values in the range and how to adjust it. I would say that examples in the problem allow u to reverse engineer the idea of leaving one empty column and putting 2 cells into one.

    Another example is a task C where solution based on one property of modular arithmetic. Tutorial used one property, I used similar one (a mod b = a b > a), which allowed me to take as ai just xi if condition is satisfied and if not i still took ai as xi only with an adjustment of ai-1 by ai-2 as many times as needed.

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

problem E as per the tutorial: Interesting fact, that in such way we generate all possible Manhattan distances. Odd distances are generated between cells from the main diagonal and (n−1,n). Even distances are generated between cells from the main diagonal and (n,n)

but I guess if total x manhattan distances exist then we only get x-1 , how to prove we can get max x-1 distances only ?

if I am wrong please correct me

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

    SashaT9 Please help !!

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

      ohh I understand, we get all the distances both even and odd except in the case of 2,3.

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

        Could you please explain the idea behind problem E solution? I am not quite sure

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

          First, try to find all possible distances, Try to put all the pieces diagonally, see what distances are covered, and then what happens if you move a piece. What distances are covered now?

          There are other ways like placing in the first row and last column, you can try to find these patterns also.

          we have only a single clue what distances we can cover, and if all, then how? If not, how do you cover max number of distances?

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

In problem F, what is wrong in the following logic: (Here a represents the prefix xor array and mp is mp[xor] = vector)

while(q--){
   int l,r; cin>>l>>r;
   if(a[r] == a[l-1]){
        cout<<"YES"<<endl;continue;
    }

    int x = *lower_bound(mp[a[r]].begin(), mp[a[r]].end(), l);
    int y = *lower_bound(mp[0].begin(), mp[0].end(), x+1);


    if(y<r && y>x && x>=l)cout<<"YES"<<endl; else cout<<"NO"<<endl;
   }
  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    1. You need to look for the sum a[l - 1], not 0.

    2. The result of the second call to lower_bound() may not be dereferenceable.

    3. You don't have to check whether $$$y>x$$$ or $$$x\ge l$$$, since these things are automatically true.

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

Why is O(nlogn) approach exceeding time limit in B question? Normally O(nlogn) works with n<2x10^5 and time limit = 2 sec.

(i tried to write a solution using upper bound 259169919)

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

    You are using upper_bound incorrectly: the way set is structured isn't linear, thus it will make your command $$$\mathcal{O}(n)$$$.

    Instead, use the class method built for set, something like this:

    auto x1 = ons.upper_bound(lst);

    auto x2 = zrs.upper_bound(lst);

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

How else can G1 be solved ?

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

Binary Search on Prefiquence felt more intuitive. https://codeforces.net/contest/1968/submission/259543727

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

Could someone tell me what is wrong with my submission https://codeforces.net/contest/1968/submission/259550793

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

are there any problems similar to F

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

Can someone please explain to me the solution for problem D cause, I can't understand the editorial clearly

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

    Let me explain my idea:

    Let $$$f_s(p)$$$ be the total score of a player when he starts at the position $$$s$$$, always moves from his current position until he reaches $$$p$$$, and after reaching $$$p$$$, always stays at his current position. Bodya and Sasha's maximum score will be $$$\max_{1 \le i \le n}{f_{P_B}(i)}$$$ and $$$\max_{1 \le i \le n}{f_{P_S}(i)}$$$ respectively.

    This claim is correct because, a player will always move from his current position only when there lies some better position with higher $$$a_x$$$, somewhere in the future along the path of his $$$k$$$ moves. Now we will prove why it is always better for him to move now instead of staying at the current position for some turns and then move.

    If his current position is $$$x$$$, and he decides to stay at $$$x$$$ for some (one or more) turns, and then move to $$$p_x$$$, there are the following three cases:

    1. $$$a_x < a_{p_x}$$$: It is obviously better to move to $$$p_x$$$ immediately and not waste turns at $$$x$$$ with lower score.
    2. $$$a_x = a_{p_x}$$$: Staying and moving doesn't really differ here. So there is no loss in moving.
    3. $$$a_x > a_{p_x}$$$: When he moves after some turns, he moves definitely in the hope of reaching some position $$$y$$$ from $$$p_x$$$ (through one or several moves in between) where $$$a_x < a_y$$$. So it is always better to spend these turns at the position $$$y$$$ than wasting them on $$$x$$$.

    So the optimal move for a player will be — some number of moves (possibly zero), followed by some number of stays (possibly zero), until he completes his $$$k$$$ turns. So we basically iterate over his final position to know the maximum possible score.

    For all $$$1 \le i \le n$$$, $$$f_s(i)$$$ can be calculated in $$$O(n)$$$ by keeping track of how many turns it takes to reach $$$i$$$ starting at $$$s$$$ and the total score obtained along the path.

    So overall running time of the solution is $$$O(n)$$$.

    You can check my submission for better understanding: 259185280.

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

Why my solution is failing for G1? I have used the same idea stated in the editorial but instead of z-function, I have used rolling-hash. My Code

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

About the problem F , I have a question. According to the formula $$$X ^ X ^ X = X$$$ , why reduce k to three , instead of further reduce one? Could help me ?

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

    $$$one$$$ subarray is not allowed in the problem.

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

      Thank you for your reply! I actually forget the detail , $$$k > 1$$$.

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

I implemented the solution described by the editorial for G2 during contest but got TLE...

https://codeforces.net/contest/1968/submission/259238179

I am posting this so late because I was trying to upsolve with a smarter solution, but couldn't come up with one. It's pretty frustrating that my approach was correct but failed because of the constant factor.

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

for f what is the different between "--lower_bound(id[a[l-1]].begin(),id[a[l-1]].end(),r)" and "lower_bound(id[a[l-1]].begin(),id[a[l-1]].end(),r — 1)"

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

    You don't find lower_bound $$$>=$$$ in the first case instead you find the first value that is $$$<$$$ $$$r$$$

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

I don't get why simple binary search doesn't work on G1. Can anyone explain? Why my code gets WA on 3 test? https://pastebin.com/SnQmt9qk

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

problem D was awesome.

can you suggest more problems like that one?!

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

Good tutorial, thanks! But I want to ask that In problem F, why we should do mp[0].push_back(0) ?

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

For G2: I would be glad if any one help understand why author's O(n√n log(n) ) solution is passing where n=2e5 and time limit 3s.

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

Can somebody help me with Problem D submission ? i seem stuck here. 260790899

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

Can someone please tell what mistake am I doing in G1 ?

https://codeforces.net/contest/1968/submission/260861542

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

G2 卡常 厳しすぎ!! (Constant factor for G2 too tight!)

I implemented the solution described in the editorial, with KMP instead of Z-function, but all my submissions ended up TLE41 (261016696) and I couldn't get the log^2 solution right.

By dividing the submission into $$$>\sqrt{n}$$$ and $$$\le\sqrt{n}$$$ parts I found my solution would finish in 3.2 seconds and I tried my best to squeeze in but still couldn't.

Could anyone help me optimize the constant factor further, or is KMP unable to pass?

BTW I don't think a $$$2e5$$$ data range for a $$$O(n\sqrt{n}\log n)$$$ intended solution is quite appropriate.

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

    if we divide the first part into < root(N / log(N)) and > root(N * log(N)) we can have a time complexity of n * root(n * log(n)). Maybe you can try this.

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

In G2 I submitted 2 solutions one wit time complexity O(N * sqrt(N) * log(n)) and other with O(N * sqrt(N * log(N))). The former solution passed whereas the later gave TLE. Does anyone have any idea why this is happening?

Former solution: https://codeforces.net/contest/1968/submission/261653053

Latter solution: https://codeforces.net/contest/1968/submission/261652536

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

what is the need of permutation in the problem D

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

E was too easy to be E

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

hi i have employed pretty much same logic as given in editorial in problem C , but in reverse sense but it is not giving right output for last test case (1 5) can u help what is wrong with it

void solve(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin >>n;
        vector<int> x(n+1);
        for(int i=2 ; i<n+1 ; ++i)
            cin >>x[i];
        vector<int> a(n+1,1);
        for(int i=2 ; i<n+1 ; ++i){
            if(a[i-1]<=x[i]){
                a[i-1] = a[i-1]*(x[i]/a[i-1] + 1);
                a[i] = a[i-1] + x[i];
            }
            else if(a[i-1]>x[i]){
                a[i] = a[i-1] + x[i];
            }
            debug(a)
        }
        //debug(a)
        for(int i=1 ; i<=n ; ++i)
            cout << a[i] << " ";
        cout << nline;
    }
}            Your code here...
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
2 months ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

G2 can be easily solved with z-function in O(nlogn^2). We find the maximal k for each answer i in increasing order. Use ordered set to maintain list of all indices in z-function that are greater than or equal to i and binary search for each next index. This allows us to binary search for each answer. Code