Codeforces and Polygon may be unavailable from May 23, 4:00 (UTC) to May 23, 8:00 (UTC) due to technical maintenance. ×

### gepardo's blog

By gepardo, history, 2 years ago, translation,
• +74

| Write comment?
 » 2 years ago, # |   +5 Thanks for the editorial ^^
 » 2 years ago, # |   0
•  » » 2 years ago, # ^ |   +11 Input5 1 ()()) 2 3 4  Expected Output1  Your Output3  Comment$S[3 \dots 4] = ()$ Clearly, there's just 1 way to permute it.
 » 2 years ago, # |   0 My O(max(n,q) * sqrt(n) * log(max(q,sqrt(n))) solution to E1This 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).
 » 2 years ago, # |   +12 Can someone explain the Binary Spiders solutions.
•  » » 2 years ago, # ^ |   0 +. more detail if it's possible. cause I'm dealing with tries first time. and i watching about tries there. i got the gist of the idea. but here the process of finding the maximum subset for i in the trie is little bit complicated. thanks in advance
•  » » » 2 years ago, # ^ |   +12 let's give it a trie. this is my solution which is a little different than the one in the editorial. First, let's focus on the MSB of K and try to group the number based on bits starting from the MSB position to the end. for example, if we have K=00010101 so we're interested in the prefix part till the first 1 bit, split k like that. 0001 | 0101 and we split numbers at the same position to height bits and lowest bits 0110 | 1000 0110 | 1001 1010 | 1100 1011 | 1010 0001 | 1001 0111 | 1000 group numbers by the first part.observation-1 look at the left part (highest bits) if this part is equal then XOR will be zero and it's bad as it will make our XOR lower than K, so the max we can get from this group is only one element. observation-2 if the left part only differs at the lowest bit then we can get one element from each group, we just need to know that the XOR between these two elements is >=K and we can do this using trie (later I will explain how). observation-3 if the bits are different then it's guaranteed that it will produce a number greater than K. so getting to the Trie part, the trie is only needed in observation two, if we found two numbers have the same prefix and differ only in the first bit. so to check that we're checking two groups A, B and trying to find if we have any two pairs that have XOR >=k. put all the numbers in group A in a trie, our binary trie will have left as zero bit, right as 1 bit. now iterate over numbers in group B, for each number try to find the MAX XOR you can get, basically you iterate over the bits in this number from left to write and try to go to the opposite if possible. if the current bit is 1 then try to go to 0 in the trie (this will maximize the XOR value). hope this helped out. my submission for ref: https://codeforces.com/contest/1625/submission/142621030
•  » » » » 2 years ago, # ^ |   +3 Great, great effort. Really appreciate it. Thankyou so much.
 » 2 years ago, # |   +11 Do anyone have the implementation of problem D, using the approach explained in the editorial?
•  » » 2 years ago, # ^ |   0 I followed the editorial's approach 142894864
 » 2 years ago, # |   +21 Please upload the codes also.
 » 2 years ago, # |   0 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.
•  » » 2 years ago, # ^ |   0 We are indexing from $0$ so element at at index $n$ is destination city (or simply it's $l$).
•  » » » 2 years ago, # ^ |   0 Oh, thank you. That makes sense.
 » 2 years ago, # | ← Rev. 2 →   +11 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
 » 2 years ago, # |   0 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
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Hey, I am also doing this only. But unable to figure out the mistake. Did you get to know why this will not work. Or anybody else can help us out! Please!! Thank you so much!My Code -> 142787581 (Similar to @i_will_be_expert's)PLEASE PLEASE, help us out!
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 This might help.
 » 2 years ago, # |   +24 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.
•  » » 2 years ago, # ^ |   0 In bitwise xor, same bits give us 0, while different bits give us 1. If we try to find minimal xor pair, neighboring numbers have more of the same bits starting from the MSB, which makes the xor value smaller.
•  » » » 2 years ago, # ^ |   0 Not always true.Consider 6 7 8, (7^8) is greater than (6^8).But still the overall minimum comes out as (6^7) which are still the neighboring elements. Its so confusing lol.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +15 Let a,b and c be three numbers such that a
•  » » » 2 years ago, # ^ |   0 Thanks for explanation.
 » 2 years ago, # |   +16 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.
•  » » 2 years ago, # ^ | ← Rev. 3 →   +11 Another thing I've noticed, converting RBS to tree is pretty much the inverse operation of DFS/finding the Eulerian path of a tree. So instead of building the tree explicitly, I found it much more efficient to simply compute the statistics for each node/open bracket in place.142753393 link to my submission
 » 2 years ago, # |   +15 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.
 » 2 years ago, # |   0 In question B, the answer seem to be n - min(v - u).
•  » » 2 years ago, # ^ |   0 Yes, you are right. I will fix it soon.
 » 2 years ago, # |   0 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
•  » » 2 years ago, # ^ |   0 I am also trying greedy approach, do you get info why greedy will not work here?
•  » » » 2 years ago, # ^ |   0 https://codeforces.com/blog/entry/99031?#comment-878059 He gave a test case why greedy won't work. Check it out.
 » 2 years ago, # |   +6 Some hints for people stuck at debugging problems B and C.Iizy Problem: B Input1 7 4 1 4 1 3 4 4  Expected Output6  Your Output5  CommentA possible sequence is $4 \ 1 \ 4 \ 1 \ 3 \ 4$ $1 \ 4 \ 1 \ 3 \ 4 \ 4$Obviously, the last 4 matches, hence it's a valid one.i_will_be_expert nitigya Problem: C Input5 5 2 0 1 2 3 4 3 2 4 6 9  Expected Output17  Your Output18  CommentThe optimal move is to remove the the signs $3$ and $4$, resulting in a total cost of $(1-0)*3 + (2 - 1)*2 + (5 - 2)*4 = 17$umanggupta1975 Problem: C Input4 5 2 0 1 2 4 1 3 3 5  Expected Output9  Your Output11  CommentThe optimal move is to remove signs at $1$ and $2$, resulting in a total cost of $(4 - 0)*1 + (5 - 4)*5 = 9$HaidRam Problem: C Input5 6 2 0 1 2 3 4 2 5 3 5 6  Expected Output19  Your Output22  CommentThe optimal move is to remove the signs $3$ and $4$ resulting in a total cost of $(1 - 0)*2 + (2 - 1)*5 + (6 - 2)*3 = 19$
•  » » 2 years ago, # ^ |   0 Thanks a lot.
•  » » 2 years ago, # ^ |   0 love you
•  » » 2 years ago, # ^ |   0 Thanks a lot
 » 2 years ago, # | ← Rev. 3 →   0 Can someone explain E2 solution in $O((n+q)\sqrt{n})$?
 » 2 years ago, # |   0 Can anyone suggest why my submission is getting MLE? any possible improvements?
 » 2 years ago, # |   +10 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.
 » 2 years ago, # |   0 Can anyone explain the convex hull trick in problem C? Thx.
•  » » 2 years ago, # ^ |   0 Interested in the convex hull trick solution too!
 » 2 years ago, # |   0 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
»
21 month(s) ago, # |
0

# 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;

}

 » 5 months ago, # |   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?
 » 5 months ago, # | ← Rev. 2 →   0 [Deleted]
 » 6 weeks ago, # | ← Rev. 2 →   0 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<> t; fer (i, 1, t) { // cout << "Test Case " << i << endl; solve(); } return 0; }