Hmm can you explain more? Thanks!

IMO one log is from binary search and another is from BIT, it's not clear to me how we can drop one of the two?

[Edit] I figured out how to do it... Basically you look at 1, 10, 100, 1000... and combine finding sum and checking the binary search condition.

A proof in plain language:

Consider two ks, k_0<k_1, they walk in the sequence simultaneously.

When k_0 levels up, k_1 still stays on the old level because more monster is required for him. This will result in k_0 skipping some monsters that k_1 fought.

But that's fine because either k_1's level never catches up with k_0, or if it catches up, at that time k_0 already made some progress at that level, and now they will fight the same monsters.

So k_1 can never fought more monsters than k_0 do.

I had a solution for problem E that's a bit simpler conceptually. (Doesn't require the harmonious series observation or changing the timeframe from i to k)

It's based on the following observation:

If a monster is fought when k=k_0, it will be fought when k is larger.

Given above, we can walk from position 1 to n, and maintain the number of monster fought for each k. For every new monster, based on observation, we only need to increase the count by 1 for a suffix. That can be done with BIT or your favorite range query data structures.

Now we still need to decide what's the smallest k for each position, or the which suffix should we operate on.

Again based on the observation, this can be found by binary search. When checking whether we will fight that monster for k, we make a query to our BIT to calculate the current level for k.

The overall complexity is still O(nlog^2n).

You are right. The sizeof only accounts for static memory. That explains it.

48B is what I got with sizeof(queue<int>()) from my local 64bit machine.

Thanks for your help!

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

They could have just said that you need to cut the string into substrings with <=k length instead of all that word bs...

I got WA with log first, then AC with log2. And after contest I tried again with log and EPS, that also worked.

You can take a look at my submissions.

I guessed that with a bit of intuition, but not sure how to approach a formal proof of it.

A brief tutorial to problem E, for people like me who cannot follow the official one:

Value $$$x$$$ will appear in one of the edges iff: $$$L \leq px \lt (p+1)x \leq R$$$, where $$$p=ceil(\frac{L}{x})$$$.

Now we enumerate every value of $$$p$$$ and count the number of possible $$$x$$$ for each $$$p$$$.

For $$$p=p_0$$$, the above inequality gives range of x: $$$\frac{L}{p_0} \leq x \leq \frac{R}{p_0+1}$$$.

Note that there is a hidden constraint of $$$ceil(\frac{L}{x}) = p_0$$$. This translates to $$$\frac{L}{p_0} \leq x \lt \frac{L}{p_0-1}$$$.

Combine the two ranges above, we get, for $$$p=p_0$$$, possible values of $$$x$$$ satisfies: $$$\frac{L}{p_0} \leq x \leq min(\frac{R}{p_0+1}, floor(\frac{L-1}{p_0-1}))$$$.

And we use sqrt decomposition to solve this counting problem: For $$$p\leq sqrt(L)+1$$$, we compute the range of $$$x$$$. For $$$p \gt sqrt(L)+1$$$, we have $$$x \leq sqrt(L)$$$, so we can just iterate through all $$$x$$$ values.

Complexity is $$$O(sqrt(L))$$$.

LOL. Some people solved C with incorrect solutions that they figured out within minutes and moved on. And those who realized that solution is incorrect will be punished. What kind of fairness is that?

It's a bad idea because some poor people like me spent ~30min trying to solve it and ~20min trying to understand why so many people solved such a hard problem xd

They probably used machine translation. The solution to E is impenetrable.

My solution to G2 with dfs and range query data structure(BIT for example):

First get the pre-order sequence of the tree, store the time stamp when you enter/exit each node.

For each query, find the node X with max depth, and node Y with min depth.

As described in the solution, X must be one end of the path. Let's enumerate the other end.

We put +1 on the timestamp you enter each node, and range_sum(X,Y) gives us the number of points covered by path X-Y.

Now we enumerate each node Z in the set, skip it if it's on path X-Y(can be determined by timestamp), otherwise see if range_sum(X,Y) + range_sum(Y,Z) = |S| + 1.

Ah, I thought there was another post XD

I had exactly the same idea but failed to implement it correctly...

Since this is 'another' solution, could you point me to the other solution? Thanks!

My sol of problem D:

First, observe that the values of array only get permuted but not changed. So sum of c[i]s should be n*(number of 1s). Thus number of 1s can be calculated.

Now you immediately know the sorted array of timestep n: 00..0011..11. And for former timesteps, The nth position is left unpermuted. Thus if c[n]>1, a[n]=1, otherwise a[n]=0.

After that you remove the influence of timestep n from c[i]s, and repeat for timestep n-1,n-2,...,0.

Imagine when you have 200000 numbers each 10^9, and you have to break everything into 1 before returning NO

The verdict of interactive problem is super confusing. I get TL while it should be WA.

Aww I realized that the irreducible fraction is actually irrelevant.

Since if u calculate $$$\frac{a}{b}=\frac{tu}{tv}$$$, where $$$gcd(u,v)=1$$$, then $$$ab^{-1} = tu(tv)^{-1}=uv^{-1}$$$ mod P.

Sad that I didn't get this during contest...

Well I do have something similar:

First, observe that the timesteps that cleaning is possible are cyclic, with cycle length no more than $$$4max(m,n)$$$.

Then, find the cycle, suppose it's $$$p_1, \cdots, p_c$$$.

Calculate the gap between neighboring points to get $$$g_1, \cdots, g_{c-1}, g_c=L-p_c$$$.

Then the answer is $$$[g_1 + g_2(1-p) + g_3(1-p)^2 + \cdots + g_c(1-p)^c] [1+(1-p)^c+(1-p)^{2c}+\cdots]$$$

And the latter term equals $$$\frac{1}{1-(1-p)^c}$$$.

That's where I stuck, cause I dont know how to simplify the fraction...

Anybody have idea on how to get the irreducible fraction in problem D?

I was able to derive an analytical form involving (p%)^i, (1-p%)^i, and O(n) constants. But if I calculate the fraction under mod P, it becomes hard to simplify the fraction. And I cannot find a way to simplify it in its analytical form...

XD

Yes we definitely can, and that's what I attempted during the contest.

I'm just feeling idiotic for not realizing the trivial simplification.

Aww I didn't realize (1+2x+x^2)=(1+x)^2 and was thinking to use NTT... How stupid!

Thanks for the explanation!

Ideas for problem D?

I think it might be Qpow+NTT, but 10^5 seems to be a bit big for that...

It is indeed meaningless to test whether people consider such edge case, but I guess it won't take too long to figure out where's the problem after getting WA?

O(nsqrt(nlogn)) should work for n=100k.

Example: 1540D - Inverse Inversions

Any O(nlogn) solution for Div1C/Div2E? I only came up with sqrt decomposition XD

NVM. Thought it was D.

You are right.

The method I mentioned has time complexity O(nk). If binary search is used, it becomes O(k^2logn).

Since n=0.5m, k=8k, the complexities are about the same. If monotonicity is used to optimize binsearch, it should be several times faster.

I'm being careless when doing the analysis XD.

I didn't check the correctness of your code, but there is indeed more efficient algorithm for this problem.

First, binary search is not needed, since as #ride become smaller, mins increase monotonically. This will eliminate a logn factor in time complexity.

Second, a simpler approach is possible for checking whether some s is valid given #ride. Consider team size $$${v_i}$$$, Now you first take largest v, and then you want to see if another smaller team can go with them. It can be shown that instead of taking the team with maximum possible size, you can just look at $$$v_1$$$. So basically you take elements only from left and right side of the array. No need to use set.

My code: 127899137

Yes you are right.

I only looked at your first claim, and didn't notice that the trick of finding the last occurrence will account for this.

Thanks for the clarification!

I think such simplification can not be done.

Consider a sequence whose sum is 2m-1, m>0:

We not only want $$$ps_x$$$ = m-1, $$$v_x=1$$$ is also required.

Already figured out D2D is calculating combinatorial number but didn't have the time to implement it... sad :(

I noticed that top-ranked guys solved the first several problems within 20 mins. I was like, how is that possible...

I'd say that I came up with the solutions once I understood what the problem was saying. And I also didn't get any WAs for those problem, which would incur delays. But it still took me about 50 mins :(.

Is there any special techniques other than reading/coding speed that makes those guys incredibly fast?

Anyone can help explain why ans for Div2 E2 with n=5 is 904 rather than 819?

It seems that I somehow misunderstood the description, but idk how...

A simple py program that outputs 819 for n=5:

from itertools import permutations

def invnum(p):
    ans=0
    for i in range(len(p)):
        for j in range(i+1,len(p)):
            if i<j and p[i]>p[j]:
                ans=ans+1
    return ans

def check(p, q):
    if p[0]>=q[0]:
        return False
    return invnum(p)>invnum(q)

cnt=0
l = list(permutations(range(1, 6)))
for p in l:
    for q in l:
        if check(p,q):
            cnt+=1
            #print("p=",p,' q=',q)
print(cnt)

Update: nvm, i thought the 'lexicographically smaller' do not include cases when p1=q1, because I didn't see these cases in the example with n=4.

You are right.

I guess it might just be typo and ci stands for j<i, pj<pi. At least with this definition of ci the algorithm seems correct :)

Check the definition of bi again dude. bi here means number of elements greater than pi. So to get ci, which is number of elements smaller than pi, you need i-bi.