ScreenCast

As a participant, I wish all positive delta and that there is NO XOR problems..

As a author... So, now "As a author" comment here. Wait for testers

Heap_OverFlow Also as a author, You will enjoy the problems xD.

Thanks AhmedYahia, Hope you will enjoy the problems.

As a divison 2 participant,I worship Tom66.

NO

Yeah bro-,-.. 1. My semester finals are from 12 December

+

Thanks Yossef.

ok

It will never be difficult. You will not Learn running unless you start walking. So participate in this contest and try to solve atleast one or two problem. Best wishes.

It's nothing compared to div1 rounds. You need more practice

I think it's also because of easy Mo's algorithm solution.

Cuz why not ?

My solution had a complexity of $$$\mathcal{O}(n^2\log{n})$$$, using LCA and dp.

I will try my best to explain what I did, So a few observations first, The permutation is 1,2,3,4....n 1) Number of subsequences starting from 'i' are n-i+1.

2) If we have a pair (1,2) that means that it includes all pairs (1,2),(1,3),(1,4)...(1,n) are included in it (because if we take any pair they will have (1,2) always). So if we have 2 inputs given as (1,2) and (1,4) so we can ignore (1,4) and take only (1,2) in consideration for calculation.

3) Now take a case like this we have only (2,3) as the pair, So when we consider subsequences starting from 1, They are: {[1],[1,2],[1,2,3],[1,2,3,4]}. Now as we have (2,3) as a pair we have to stop before 3. So we have to consider the effects of the number after 1 to get its stopping point.(once read code comments to be more clear)

4) if we only consider the pair (1,4), lets say n is 5. so the possible subsequences are 1,{1,2}, {1,2,3} == 4-1 {or b-a for a pair (a,b)}

Code With comments

int n, m;
cin >> n >> m;
vector<int> v(n + 1, INT_MAX); (This vector denotes that where we have to stop next, like for (1,2), i have to stop my subsequence before 2)
for (int i = 1; i <= m; i++)
{
    int a, b;
    cin >> a >> b;
    if (a > b)swap(a, b);
    v[a] = min(v[a], b); //Observation 2
}
for (int i = n - 1; i >= 1; i--)
{
    v[i] = min(v[i], v[i + 1]);//observation 3
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
    if (v[i] != INT_MAX) {
        v[i] = v[i] - i;
    }
    else {
        v[i] = n - i + 1;//observation 1
    }
}
for (int i = 1; i <= n; i++)
{
    ans += v[i];//finally adding contribution from each number. i.e number of possible subsequences starting from that number 
}
cout << ans << endl;

Sorry If I complicated in explaining something.

Some observations:

• If $$$[a, b]$$$ is a good subsegment, then all subsegments of $$$[a, b]$$$ are also good subsegments.
• If the non-friend list contains a pair $$$(a, b)$$$, then any good subsegment that contains $$$a$$$ will not contain $$$b$$$.
• If $$$[a + 1, b]$$$ is not a good subsegment, then $$$[a, b]$$$ is not a good subsegment.
• If $$$[a + 1, b]$$$ is a good subsegment, and $$$a$$$ is friends with all $$$x$$$ satisfying $$$a < x \leq b$$$, then $$$[a, b]$$$ is also a good subsegment.
• If the largest good subsegment that begins with $$$a$$$ is $$$[a, b]$$$, then there are exactly $$$b - a + 1$$$ good subsegments that begin with $$$a$$$ (all prefixes of $$$[a, b]$$$).

Individually, these observations should be obvious, but this leads to the following solution:

• First, for each person $$$i$$$, find the earliest person after $$$i$$$ who is not friends with $$$i$$$, i.e., find the number $$$j$$$ such that $$$i$$$ is friends with everyone in the interval $$$(i, j)$$$ but $$$i$$$ is not friends with $$$j$$$.
• • We can prepare this by simply maintaining a 1D vector nextstranger, such that when we read a non-friend pair $$$a, b$$$ with $$$a < b$$$, we set nextstranger[a] = min (next_stranger[a], b).
• Suppose we know that the largest good subsegment that begins with $$$a + 1$$$ is $$$[a + 1, b]$$$. If $$$a$$$ is friends with everybody in the range $$$(a, b)$$$, then the largest good subsegment that begins with $$$a$$$ is $$$[a, b]$$$ (cannot extend to $$$b + 1$$$ because there must be somebody within that that doesn't know $$$b + 1$$$). But if there is at least one person that $$$a$$$ is not friends with in the range $$$[a + 1, b]$$$, then the largest good subsegment that begins with $$$a$$$ is $$$[a, nextstranger[a] - 1]$$$, since $$$a$$$ knows everyone afterwards up until nextstranger[a].
• • In other words, the largest good subsegment that begins with $$$a$$$ is $$$[a, \min (b, nextstranger[a] - 1)]$$$.
• If we now iterate $$$i$$$ from $$$n$$$ to $$$1$$$ (descending order), we can now find the largest good subsegment that begins with $$$i$$$. The base-case is when $$$i = n$$$, where the largest good subsegment is obviously $$$[n, n]$$$.

My submission: 184766262

I used non to refer to nextstranger and cut to represent the person right after the longest good subsegment ends, i.e., for a given value of $$$i$$$, cut becomes the minimum of nextstranger[i] and the previous cut (i.e. the cutoff point for the largest good subsegment that begins at $$$i + 1$$$).

+1

This solution is too long, because lcm(a) and prod(a) can be ~ 10^(n * 9).

math.prod(a) is so huge number... power(10, 9 * 1e5)

It's actually possible to get AC with your formula with some constant factor (and some other) improvements.

for example: 184805714

Yes, but it will probably FST (184750417).

UPD. It passed

If $$$n$$$ is a large prime or a product of two primes $$$p, q$$$ such that $$$|p-q|$$$ is small, your factorization algorithm degenerates into $$$O(\sqrt{n})$$$ which is unable to pass.

I am so dumb that I have to nuke it with the Pollard Rho algorithm after failing 7 times, sigh~. Look my submission 184795924 when available.

Not sure of system tests though but the basic solution passed.

vector<ll> seivePrimes() {
  vector<ll> prime(35001);
  vector<ll> nums;
  for(ll i = 2; i <= 35000; i ++) {
    if(prime[i] == 0) {
      nums.push_back(i);
      for(ll j = i; j <= 35000; j += i) {
        prime[j] = 1;
      }
    }
    if(nums.size() >= 3410) return nums;
  }
  return nums;
}
 
void solve(vector<ll> & primes) {
  ll n, x;
  cin >> n;
  vector<ll> v(n);
  ll ans = 0;
  for(ll i = 0; i < n; i ++) {
    cin >> x;
    v[i] = x;
  }
  
 
  for(auto it: primes) {
    ll count = 0;
    for(auto &i: v) {
      ll p = 0;
      while (i % it == 0) {
        i /= it;
        p ++;
      }
      count += p > 0;
    }
    if(count > 1) {
      cout << "YES\n";
      return;
    }
  }
 
  sort(v.begin(), v.end());
  for(ll i = 1; i < v.size(); i ++) {
    if(v[i] == v[i &mdash; 1] && v[i] > 1) {
      cout << "YES\n";
      return;
    }
  }
  cout << "NO\n";
}

Soooo, True This is one of the worst DIV 2

Although this was a harder div2 B, it most certainly is not on the same level as a div1 B.

Any idea why Runtime error for such a code?

I also got it for few of my submissions. Still couldn't find out why !

sample explanation in B also does not have latex

Btw I found editorial for 652C to be much more readable

I used sieve for C — worked well within the time limit.

I disagree.. The contest was good. B was very good. (It required a bit more thinking unlike usual Div 2 B where you just see the problem and start coding, also no tricky edge cases were there for me least).

Even though I wasn't able to solve C. I guess that's what makes the problem good. Must have missed some observation.

this basically sums this contest up

can't agree more... I didn't see any interesting problems in this contest

What was not bad ? Round has 3 nice problems with more or less short statements — A, C, F. Everything else is shit on a stick

It's not enough to check until 10**4.5, you do need to check until 10**9. For example, you might have 2*192763567 and 3*192763567 in the data set (192763567 being prime).

can u explain ur sqrt decomposition logic ?

I managed to write a solution using sqrt decomposition that passes, but just barely. I had to implement range paint using a vEB tree instead of DSU (which turned out to have a better constant factor than making the log log n faster than the inverse_ackermann n for this problem).

Explanation of the solution: Divide the array into B blocks. Then process each block individually like this: Look at each value that occurs in the array, but not in the block. Assume the left bound of some query is inside the block, and the right bound is outside the block. Then if the answer is a value that isn't in the block, it must occur an odd number of times outside the block. And which is the smallest of these for a given right bound does not depend on the left bound, since the left bound is inside the block, and the block doesn't contain the value. So by range-"painting" values you can compute the answer for every right bound, assuming the left bound is inside the block and that the answer is not a value inside the block. Range painting can be done in O(n log log n) with good constant factor using a vEB tree.

Then to answer a query, you can look only at the block corresponding to the left bound of the query. Brute force count how many occurrences there are in the range of each value that appears in the block. There are n / B values in the block, so this can be done in O(n / B * log n) time by binary searching in arrays of positions of occurrences.

Then take the minimum of this answer and the pre-computed answer for the right bound in the block.

Total running time is O(qn / B * log n + Bn log log n). Code: 184822603

Had to steal some fast IO from nor and vEB tree from mango lassi and nor to make it pass.

What brute force did you think of?

I came up with the solution of D, but it got the WA.

Can you please explain your logic for problem -D ?

Use long long

got it

If all elements are same the answer is $$$n(n-1)$$$.

can u share ur solution plz ? :)

how did u solve it ?

There are only 3401 primes smaller than sqrt(1e9) so you only need to check for those primes. Then, once you are done dividing by all the primes, if the number left is greater than 1 then it is another prime.

Square root of 10^9 is 31622. There are atmost 3402 primes in 31622. There are 10^5 numbers and try to prime factorize by 3402 primes. Complexity O(n*3402) will pass.

I thought it will get TLE, so I didn't write it. Too bad.

You can avoid hash table by taking a 3500 length array for storing frequency of each prime, but I agree that it was not clear that $$$3.5e8$$$ modulo operations would pass in tl.

True. I got TLE using python