Anadi's blog

Codeforces Round #519 Editorial
By Anadi, history, 6 years ago, In English

1043A — Elections

Tutorial
Solution

Author: Anadi

1043B — Lost Array

Tutorial
Solution

Author: Anadi

1043C — Smallest Word

Tutorial
Solution

Author: Anadi

1043D — Mysterious Crime

Tutorial
Solution

Author: Anadi

1043E — Train Hard, Win Easy

Tutorial
Solution

Author: Rzepa

1043F — Make It One

Tutorial
Solution 1
Solution 2

Author: Anadi

1043G — Speckled Band

Tutorial
Solution 1
Solution 2

Author: isaf27

  • Vote: I like it
  • +113
  • Vote: I do not like it

Comments Comments (73)
| Write comment?
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Auto comment: topic has been updated by Anadi (previous revision, new revision, compare).

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

Superfast editorials!!!

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

Auto comment: topic has been updated by Anadi (previous revision, new revision, compare).

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

There's an appearance issue in C tutorial

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

Wow this G solution...

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

This solution of Problem G is saying, "You need an editorial for me? Meh, just take a look at me, I don't need one."

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

Author had solution for G, but this tutorial is too small to contain it.

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

Auto comment: topic has been updated by Anadi (previous revision, new revision, compare).

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

For F, you may have considered this right end part of formula: , right now it's confusing.

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

Auto comment: topic has been updated by Anadi (previous revision, new revision, compare).

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

There is one correct solution for G as scoreboard showes. Who is this one? Or it is error?

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

    I think LHiC solved it after contest.

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

      Thx. I think it is wrong behavior to show count of solutions that are not showing at table.

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

Auto comment: topic has been updated by Anadi (previous revision, new revision, compare).

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

What am I missing for problem D, 31th test case : 10 3

7 4 10 8 3 6 2 9 5 1

7 4 10 8 3 6 2 9 5 1

2 9 5 1 7 4 10 8 3 6

We have subarrays {2,9,5,1} and {4,10,8,3,6}, so I'm calculating number 26. (4*3/2+5*4/2)+length_of_array(when subbaray is one number)

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

    Well, if you observe more closely, you'll see that the second group contains the 7, too (it appears on all of the 3 permutations!), so you get 6 elements for the second group! Answer: 4 * 5 / 2 + 6 * 7 / 2 = 10 + 21 = 31 elements.

    (note that we can include the single elements when we are calculating the answer for each group, by adding one more number. Please note that if a group is single (only 1 element), the answer is 1, because we include only that element and note that 1 * 2 / 2 = 1. This makes the calculations easier! :) )

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

In problem F:

"Our answer is the smallest i such that dp[i][1] is non-zero. Since dp[i][j] can be quite big we should compute it modulo some big prime."

Can we be sure that if dp[i][j] % p is 0 then dp[i][j] must be 0 as well?

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

    As you only need to check seven numbers probability of collision is extremely low.

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

    You can take 2 DP arrays with different big primes, to reduce the chances of collision.

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

Why is the distance in a suffix array not greater than ?

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

    As i is defined as the maximum index, it means that s[i..r] has no suffix that is also a prefix. Thus the suffixes between l and i in the suffix array (they share at least the same prefix as l and i) must have indexes such that the distance between them is . An thus there are at most such indexes.

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

In G's solution, isn't aabc == aab and bcaa == baa or did I misunderstand something?

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

tex formatting is broken in G

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

what is a border?

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

    Equal prefix and suffix of the string

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

I am interested in how everybody solved D.

Personally, I did some prefix hashing and then binary search on maximum length substring starting at value k for a mnlogn solution.

Some ones I've heard:

1) Some type of Map solution (a lot of people did this)

2) O(nm) DSU solution (rotavirus mentioned)

3) Rolling hash (anyone else did prefix hash... ?)

I'm especially interested in DSU explanation, but also I've seen some variation in how people have used map, and want to hear how you guys approached that. For example, I saw radoslav11 make some suffix automaton, which unfortunately got TLE on 36, but with some constant optimization it could work.

Please tell me about your solutions for this problem!

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

    i made a dsu of size n, then for each pair of adjacent elements in the first permutation, i checked whether these elements are adjacent in all other permutations, if yes, i united them. So, if two numbers are in the same disjoint set, then they form a valid subarray, so i counted the number of pairs in each disjoint set and printed the sum of them.

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

    I had a vector consisting of all pairs of adjacent numbers in the permutation and used binary search to find the count of occurance of a pair instead of using a map for keeping track of the count. I prefer doing this instead of using a map generally when the time limits are strict. My Submission

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

    I used a revolutionary new data structure. For some people it can take years to master, but once you figure out how to use "array", you are set for life.

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

    I just keep track of the position of each element in each permutation for a linear-time solution. See the code.

    The only observation needed is that if the first permutation's substring starting at index i is valid until index j, then the substring starting at i + 1 is valid until at least j as well.

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

    what is difference between rolling hashing and prefix hashing? what's prefix hashing btw?

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

      Basically you store the prefix sum of a[i]*BASE^i so that: h[i] = h[i-1] + a[i]*BASE^i

      So when you want to get hash code for substring (L, R) in O(1) you can do it like this

      (h[R]-h[L-1]) * invPow[L]

      invPow[i] represents BASE^(-i)

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

      For rolling hash you just keep a window (actually a number to represent the window) of size k and you "pop" and "push" to slide the window.

      For example, you maintain k = 3 at i: a[i]*BASE^2, a[i+1]*BASE^1, a[i+2]*BASE^0

      You would subtract a[i]*BASE^(k-1), multiply everything by BASE, then add a[i+k] (BASE^0 is just 1)

      You could also maintain it in reverse and "divide" with modular inverses, but that's just more work.

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

For F, I got accepted by a randomized algorithm with some greedy at the beginning (45016248).

  • Greedy part: remove some numbers on the array such that there is no pair on it which the one is divisible by the other one. (e.g. ).
  • Randomization part: Attempt many (e.g. 1, 000, 000) sessions to randomly pick some elements from the array until its GCD is 1 or restart if the number of elements picked is more than the best one.
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is the expected runtime?

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

      The expected runtime is just a big constant for the randomization part, around O(1, 000, 000 × 50) but can change 50 to 7 or 8 as it is the maximum possible answer.

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

        Actually, neal showed below that the expected runtime of one iteration is not 7.

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

          We cap the 7, if after picking 7 numbers doesn't give a GCD of 1 then skip and restart the iteration.

          This number btw can be lower, as we keep track the progress of iterations.

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

            Thanks, then it is deterministic runtime :)

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

    Here's a test case that your algorithm will have trouble on:

    [10, 21, 6 * p for all primes p that fit]

    The answer is 2 because you can pick 10 and 21. However every other pair of numbers in this array will have a GCD greater than 1. So you only have a roughly chance of picking the right pair on every attempt you make, and n can get fairly large, over 5,000.

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

      Ah, that's correct; I only did calculation for case of instead and found out of success. The success percentage of your case is just 4% for my program. I guess I got lucky then, ><

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

I think that in the last paragraph of tutorial of problem E it should be

Similarly we have that yi  +  xj  <  xi  +  yj if xi  -  yi  >  xj  -  yj.

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

can some admin link this to the problems, right now only the announcement is linked, thanks

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

    It looks like instead of linking the tutorial, the announcement was unlinked!

    Please fix, thanks.

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

There are no contests this week.
:(

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

How to Solve C ?

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

    I add 'b' to input string at last. Then if i see 'ba' or 'ab' in string then revers at that point. You can try some examples to better understanding of this approach.

    my code

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

The answer is 3 if the string s is baac, bcaa or aabc

Cases bcaa and aabc don't make sense. It probably should be baca and abac.

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

I solved Problem C during contest. But I wanted to know DP approach for solving it. Can anyone share DP approach to solve Problem C ?

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

Pure stl challenge for problem A :)

int n;
cin >> n;

vector<int> a;
copy(istream_iterator<int>(cin), istream_iterator<int>(), back_inserter(a));
cout << max(*max_element(a.begin(), a.end()), 2 * accumulate(a.begin(), a.end(), 0) / n + 1);
→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

I solved C with another interesting approach.

Let's have a recursive function sol(int pos, bool asc).
pos is the position (or prefix) till which we need the answer, and asc tells us whether to make this prefix ascending or descending.
The final answer is sol(n, true).

Let's call the position with the rightmost 'a' (or the minimum character in the prefix) inside the current prefix as idx. (rightmost max character in case of asc == false)
Now, to get the optimal answer, we need to flip at position idx.
But, to make sure that this flip will be optimal, we have to make the prefix before idx in descending order, so we call sol(idx - 1, !asc) which will make the prefix in the optimal descending order, and then let recursion do its job.

Base case would be when we reach the prefix of size 1, where it doesn't matter whether to flip or not.
My submission — 45069274.

UPD: It seems I have solved this problem for a regular string (without the restriction of containing only as and bs) :D
I need to read problems more carefully!

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

    I know i am late, but if you are still reading this.. i don't understand this part "But, to make sure that this flip will be optimal, we have to make the prefix before idx in descending order"

    Can you elaborate? thanks.

    UPD: i got it, when we flip the prefix 0..idx, we want the 0..idx-1 to be in biggest to smallest order so that when we split upto idx...it is the smallest possible order.

    → Reply
»
6 years ago, # |
  Vote: I like it +25 Vote: I do not like it
Another solution for F:
→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Very cool and fast editoral, thank you!

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

my solution for D looks asymptotically correct but it gives TLE at testcase 36 can someone help 45130338

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

In problem D :-> my solution is giving tle in O(M*n), i tried to take input in one go through string which makes it fast but giving wrong answer can anybody tell me where i am wrong?

Here is my submission by simply taking the input one by one: First Submission

By taking string as input: Second submmission

UPDATE: I GOT MY FLAW!! thanx if anyone GETTING TLE USING O(M*N) TRY TO TAKE INPUT USING GETLINE IN ONE GO,IT WILL REMOVE THE TLE PROBLEM!!

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

Will someone please explain problem F a bit more clearly..

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

    You can remove the duplicates in the array and get the same result. Why? Because gcd(a,a) = a. So now let us force every element to be unique. If we greedily maximize how many element we can have it is 1, 2, 2*3, 2*3*5, ...2*3* 5*7*11*13 = 7 elements

    This means we only care about making gcd(arr) = 1 with 7 elements at max.

    So we can reduce O(n*maxA) DP to O(7 * maxA) states

    We we want to know for a number j, how many ways can we use i elements to make gcd(the i elements) = kj. This is can be calculate with combination modulo some number. We can precalculate some value mult[j] which says "how many values are multiple of j" to achieve this.

    But we want to exclude answers where k > 1, so we subtract those. This loop is actually (AlogA) because O(n + n/2 + n/3 ... 1) = O(nlogn)

    So we get O(7 * maxA * logA) complexity

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

Another approach for problem F: Do a binary search first. Notice that: It's hard to determine whether a subset of size k and with its gcd equals to 1 exists directly, but calculating the number of such subsets modulo a big prime is easy: simply use the inclusion-exclusion principle(with the mobius function). Use a good prime and you'll get accepted. :P

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

    Your approach sounds interesting. Can you explain a little more how you use inclusion-exclusion? And mobius function?

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

      The number of ways to select k coprime elements from a multiset is sigma(mu(x) * comb(number_of_elements_that_is_a_multiple_of_x, k) for 1 <= x <= MAXA).

      You can precalculate the factorials and the inverses of the factorials of each positive integer <= n to compute binomial coefficients and a sieve to compute mu(x) and number_of_elements_that_is_a_multiple_of_x for each x.

      Time complexity: O(n + MAXA log MAXA)

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

45341495

my solution for D is WA on #7, can someone tell me what i'm doing wrong?

i'm counting for every 'i' the size of the largest array [i, i+1, ...] that is present on every array, then i sum all these values. my code returns correct results for all other testcases with small size

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

isaf27 About problem G , why the distance between l and i in suffix array <= sqrt（n）?

and what is the second solution to check if there exists a border for [l,r]

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

i have read some other solution for G and it's look like they don't find any tandem repetitions. Is there a easier solution for G? I think this solution is too hard to implement in contest. Tks you

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

I don't know if this is my first time to solve D by my own.

Well my approach is a little different from others. I stored first array as it is. While for other arrays I stored the position of each element (eg. [1, 4, 2, 3] will be stored as [1, 3, 4, 2]). We will also maintain an array p of m size for storing current positions of m arrays.

Now we traverse the elements of first array. If for all remaining arrays, the position in the array for current element in first array is 1 greater than the current array position i.e. if p[i] + 1 = array[i][array[1][p[1]]] then subarray size will be incremented. In case the condition is not true and if size of common subarray is k till now then ans will be incremented to k × (k + 1) / 2 and k will 1.

Complexity is O(mn).

Link to code

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

Could someone explain the alternative solution of Problem F(Solution 2) to me?

I confuse at bitmask-part in get_edge function.

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

in there anybody who can explain bit-mask solution for problem F ?

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

In G, the "finding a border" part can be done "easily" without a suffix array. The observation is that if a substring with length $$$L$$$ doesn't start with a tandem, then for any $$$K$$$, it contains at most $$$2L/K$$$ occurrences of its prefix with length $$$K$$$ -- otherwise, two of them are sufficiently close to create a tandem. I fix $$$K \approx \sqrt{N}$$$, precompute hashes of all $$$O(N)$$$ substrings with length exactly $$$K$$$, and for each query substring, check for all borders with length $$$\le K$$$, look at occurrences of its prefix with length $$$K$$$ inside it and check for each of these occurrences if the border's end half starts there. With $$$O(1)$$$ substring comparison using hashes, this is $$$O(\sqrt{N})$$$ as well.

On the other hand, I used a suffix array approach instead of Main-Lorentz, since I didn't know it.

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

For F, can someone please give me some intuition(or proof) behind the first line, that it not contain more than 7 elements...

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

    any number up to 3e5, which is the constraint, doesn't have more than 7 distinct prime divisors, and thus the prime factorization would be at most of size 7 without the exponents kind of just think about intersection of pf's, if there aren't any then we could just take a non intersecting pair , there can't be more than 7 intersecting pf's since the size is at most 7, etc.

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

Please give me some hints for an F-like problem: Given an array with 2e5 number a[1], a[2], ..., a[n](a[i] <= 1e9). We have to find the subsequence of A such that their pairwise indices' gcd is equal to 1 and their sum of a[i] is as maximum as possible. For example, we have an array A = {1, 2, 1, 3, 1, 6}, so the answer is 8 because if we choose a[1], a[5], and a[6] because gcd(1, 5) = gcd(1, 6) = gcd(5, 6) = 1 and a[1] + a[5] + a[6] = 8 is the largest answer

→ Reply