Thanks for the editorial ^^

E1 WA on TC3 ,implemented using Mo's algo, help !!

`

My O(max(n,q) * sqrt(n) * log(max(q,sqrt(n))) solution to E1

This solution works even when the segment asked in query is not a RBS. Note that log factor can be removed on using pointers and using prefix sum(for heavy chains).

Can someone explain the Binary Spiders solutions.

Do anyone have the implementation of problem D, using the approach explained in the editorial?

Please upload the codes also.

For C, I think "min(dp[n][j]) over all 0 <= j <= k" is not the final answer, because that is forcing the n-th sign to be taken (not removed). To get the final answer, we have to enumerate the last taken sign, add the remaining road section's time to each one, and finally take the minimum value among all of them.

I think problem D memory limit should've been higher if bit-trie solutions were intended to be accepted. Fitting $$$O(n \log A)$$$ memory into 256 MiB is quite a challenge, especially for Java and Python

I was trying O(n^2) solution for Problem C by having additional DP state for propagating last selected speed limit. I am not looking for solution, but if someone can take a look and tell if this would work or not, that would help. Thanks.

142748551

On D

To solve the problem, we need the following well-known fact. Suppose we have a set of numbers and we need to find minimal possible xor over all the pairs. It is true that, if we sort the numbers in non-descending order, the answer will be equal to minimal xor over neighboring numbers.

Is it actually well known? Does anyone have a proof for why that is the case? Afaik the most common way to solve this problem is by making a bit trie.

I think in E2,it is more natural for me to think up the $$$O((n+q)\log n)$$$ solution than the $$$O((n+q)\sqrt n)$$$ solution.

E2 can still be solved if not only leaves are erased, but each pair must form a matching.

If we build the bracket tree, the erase operation can be transformed to erase a node and link all its sons to its father. The queries can be transformed to sum up $$$k*(k+1)/2$$$ for each node in the interval. We can use unionset to deal with father changes and a Fenwichtree to deal with subtree sum except the root. Degree of the root of each interval can be transformed to occurrences of minumum prefix sum in the interval. It can be maintained by segment tree.

Here is the code.

In question B, the answer seem to be n - min(v - u).

Can someone tell me why doesn't greedy algorithm work for problem C in which we remove the sign which causes a maximum decrease in time. If someone can provide a short test case which I can visualize that would be helpful. Here is my code 142511895

Some hints for people stuck at debugging problems B and C.

Iizy Problem: B

1
7
4 1 4 1 3 4 4 

6

5

i_will_be_expert nitigya Problem: C

5 5 2
0 1 2 3 4 
3 2 4 6 9 

17

18

umanggupta1975 Problem: C

4 5 2
0 1 2 4 
1 3 3 5

9

11

HaidRam Problem: C

5 6 2
0 1 2 3 4 
2 5 3 5 6 

19

22

Can someone explain E2 solution in $$$O((n+q)\sqrt{n})$$$?

Can anyone suggest why my submission is getting MLE? any possible improvements?

Another solution for problem D using divide and conquer:)
Suppose that now we have a set of spiders, $$$S$$$, to calculate the answer, obviously at first it's just the original set.
Let's look through the bits of $$$k$$$ from high to low, for the $$$i-th$$$ bit, there are two cases:
1. the $$$i-th$$$ bit of $$$k$$$ equals to $$$0$$$. In this case we can divide the set $$$S$$$ into two parts: one set $$$s_0$$$ with all elements whose $$$i-th$$$ bits equal 0, the other set $$$s_1$$$ with all elements whose $$$i-th$$$ bits equal 1. It's for the reason that if we choose any element $$$x$$$ in $$$s_0$$$ and any element $$$y$$$ in $$$s_1$$$, $$$x\ xor\ y$$$ will always be larger than $$$k$$$. Now here come two subproblems with $$$s_0$$$ and $$$s_1$$$ and it goes to the $$$(i-1)-th$$$ bit;
2. the $$$i-th$$$ bit of $$$k$$$ equals to $$$1$$$. In this case we can choose no more than two elements in $$$S$$$, and their $$$i-th$$$ bit must be different. To find the elements, we also need to divide $$$S$$$ into two parts following the rule above, and then go to the $$$(i-1)-th$$$ bit and continue to divide the two sets... To ensure that the two sets we have now always satisfying the property that the $$$xor$$$ of two elements from each must not be less than $$$k$$$. You can view my code for more details.
The time complexity is $$$O(n\cdot log\ max\lbrace a_i, k\rbrace)$$$, here is my code.

Can anyone explain the convex hull trick in problem C? Thx.

For problem C, why would it not work to use a simple greedy where you pick the sign such that its removal decreases the total time as much as possible, and repeat k times?

144901424

Why my code is giving wrong answer in 4th test case of Elementary particle question? PLEASE HELP.

include <bits/stdc++.h>

using namespace std;

int main() { int t; cin>>t; while(t--) { int n; cin>>n; int a[n]; for(int j=0;j<n;j++) cin>>a[j];

map<int,pair<int,int>> m;
  int temp=INT_MAX;
  for(int j=0;j<n;j++)
  {
    if(m[a[j]].first==0)
    {
      m[a[j]].first=j+1;
    }

    else if(m[a[j]].second==0)
    {
      m[a[j]].second=j+1;
    }

    else
    {
      if(m[a[j]].second - m[a[j]].first > j+1 - m[a[j]].second)
      {
        m[a[j]].first=m[a[j]].second;
        m[a[j]].second=j+1;
      }
    }
  }

  for(auto it=m.begin();it!=m.end();it++)
  {
    if(((*it).second).first==0 || ((*it).second).second==0)
    continue;

    if(((*it).second).second - ((*it).second).first < temp)
    temp=((*it).second).second - ((*it).second).first ;
  }

  if(temp==INT_MAX)
  cout<<"-1\n";
  else
  cout<<n-temp<<'\n';
}

return 0;

}

Sorry for necroposting, but I didn't find any solution for this in comments or anywhere

In problem D, The editorial solution uses a trie. if you use trie. Then there are at most nlogA vertices. If we implement using pointers then its memory would be nlogA*32 (32 if because of pointer address size in 32 bit compiler) = 3*10^5*30*30 = 2.7*10^8 ~ 2 GB. But memory limit is just 256 MB. How to solve this issue?

[Deleted]

why is my code not right for problem 1625C - Road Optimization?

anyone who can explain?

int f(int i, int k, int l,vll &v, vll &tpk, vvll &dp) { if(i == 0) { return (l)*tpk[0]; } if(dp[i][k] != -1)return dp[i][k];

int remove = INT_MAX;
if(k > 0)remove = f(i-1, k-1, l, v, tpk, dp);
int notremove =  tpk[i]*(l - v[i]) + f(i-1, k, v[i], v, tpk, dp);


return dp[i][k] = min(remove, notremove);

}

void solve() { read(n); read(l); read(k); vecin(v, n); vecin(tpk, n); vvll dp(n,vll(k+1,-1)); cout<<f(n-1, k, l, v, tpk, dp)<<endl; }

int32_t main() { fast_io; int t = 1; // cin >> t; fer (i, 1, t) { // cout << "Test Case " << i << endl; solve(); } return 0; }

For C

dp[i][k] = min answer up to ith speed limit and we took k speed limit. (we assume ith limit is taken)

dp[i][k] = min(dp[i-1][k-1] + ... , dp[i-2][k-1]+...., ....)

I think it can be solved in O(n^2) if we use some kind of prefix sum on dp table

Can someone elaborate how exactly Convex Hull Technique is used for optimization in C?!