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 \lt 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 \lt 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.