Is there any extension/website that allows me to view only division 1 problems? I looked around a bit, and the closest I got to finding something was https://codehunt.cc , except the only thing it filters only for edus/div3.

# | User | Rating |
---|---|---|

1 | Benq | 3650 |

2 | Radewoosh | 3648 |

3 | tourist | 3579 |

4 | ecnerwala | 3551 |

5 | Um_nik | 3494 |

6 | Petr | 3452 |

7 | ksun48 | 3432 |

8 | jiangly | 3349 |

9 | maroonrk | 3338 |

10 | Miracle03 | 3314 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 210 |

2 | awoo | 188 |

3 | Errichto | 186 |

3 | rng_58 | 186 |

5 | SecondThread | 182 |

6 | Um_nik | 176 |

6 | Ashishgup | 176 |

8 | maroonrk | 172 |

9 | antontrygubO_o | 171 |

10 | -is-this-fft- | 169 |

Disclaimer : I just want to highlight some simple techniques used to solve Ad-Hoc tasks.

In my opinion, these are all simple techniques, but a lot of these are used even in much harder problems. I hope these will be helpful to some people.

1: Eliminate obvious cases, and see if you can simplify the problem.

How do we get to the solution here.

We eliminate any weight >w, as that is useless. We can use any weight s that is w/2 < s < w. Therefore, we essentially need to solve only for small weights. Now it is easy to see you wont "jump" over the range.

2: Ignore unnecessary information, and use it to draw the problem in new ways.

Firstly notice, numbers we will not remove are really not different at all. So we can represent them with a `.`

. Let i be the number we will remove in the ith operation.

Now we have something like `..2...1..4..3...`

. This is just to illustrate our transformation.

Now notice, that `.i.`

will give `..`

no matter which side you choose. Notice that `i`

is now removable. So now its obvious to see that operations are independent.

3: Making obvious lower and upper bounds, and proving they are constructible.

Consider the fact that if there are $$$A_i$$$ people in the subtree of $$$i$$$, they will all be distributed among the leaves in the subtree equally at best. So its clear, that the answer must be at least $$$\lceil A_i / Leaves_i \rceil$$$.

Now notice that if the answer for all the subtrees of some node's children was lesser, then we can easily distribute the new people among the leaves equally.

If its not, we can still assign greedily to the leaf with the least people, and it cannot exceed the maximum, because that would imply that the minimum is $$$ \ge\lceil A_i / Leaves_i \rceil$$$, which is not possible, because that would mean all the people are used up.

4: Finding invariants

When you set all 3 to $$$a_i \oplus a_j \oplus a_k$$$, notice that the xor of the full array is an invariant. This tells us that it is impossible to make all elements equal in an even length array if the xor of the full array is not 0.

There is another Ad-Hoc observation required to complete the construction.

Notice that if $$$A_j = A_k$$$, its essentially setting the values of them to $$$A_i$$$ when you do the operation. So if we make equal pairs, we can easily solve in floor(n/2) moves. Making equal pairs is also really easy. Just do operations with all pairs with a pivot element. Clearly this will work only in an odd length array.

This proves we can construct the solution for any odd length array. Now notice that if the xor of an even length array is 0, and we make the first n-1 are equal, that means that the last element will automatically be equal, because xor of the array will remain 0.

5 : Define something that cannot change much.

Lets think of the string like links 1 — 0 — 1 — 1 — 0 — 0 — 0 — 1. We dont want any 0 — 0 link, or 1 — 1 link.

Reversing a substring breaks and creates at most 2 links. if both the ends of the substring is the same, then the number of 0-0 and 1-1 links remains the same.

I just want to clarify, that this alone does not prove that it is never optimal to do this, just that it doesn't reduce our measure.

We can also show that the number of such links is reduced by at most 2, and that is done by choosing some 0 — 0 link and some 1 — 1 link.

So a lower bound on the answer is the number of bad links/2.

So now we want a 1 — 1 and 0 — 0 link.

Now the problem is, this doesn't always exist on a string such as "1001". That means that this solution is incorrect.

Notice that the last and first characters must also be different. Lets redefine our formation and include that link. Now each 0 and 1 has 2 links, so if there is 1 — 1 link, there is a 0 — 0 link matching with it.

So now the lower bound is bad links/2, and this time we can also construct it. And therefore this is the answer.

Step 1 : Rewrite the operation as subtract the values of b from a

Step 2 : Eliminate the obvious : 2 consecutive equal elements can have the same operations performed on them to get 0 so we only care about distinct elements.

Step 3 : If we subtract too much, then the array may get unsorted, then its impossible to write it as the sum of sorted arrays, so make sure to not do that.

Step 4 : Now notice every place where we increase the value of B, can make at most 2 values equal, so we can reduce the number of distinct elements by at most k-1. We can always do this easily.

Step 5 : We need distinct elements to be 1. If we manage to do that, then we can just add that values to all elements of an operation, to not add extra moves, So they are equivalent *if* you do a move.

Lets redefine n to be the number of distinct elements. if n == 1, then we need one move. if k==1 and n!=1 then it is impossible. if k!=1, then answer is ceil(n-1/k-1).

Some newbie messaged me with asking for help on this article https://www.geeksforgeeks.org/queries-for-number-of-distinct-elements-in-a-subarray-set-2/.

Can someone explain why time complexity is O(log n) and not O(n)?

Please read it once before downvoting. It is an advanced data structure, that is not well known.

There is a codeforces round X coming up. Is this a new thing in CF, or have similar rounds already taken place on CF?

Does anyone know what it is about?

Inspired by comments on this post, I am trying to recreate the system.

Please fill out this form and I will allocate as requested to the best of my ability. I believe Groups of $$$3$$$ are best for practising. If you are not content with your group, I will try to accommodate you in another group.

To prevent spam, please submit a compilation error to 29B in problemset. Alternatively, If you don't want a compilation error in your records, change your name to "Buddy" "System".

I hope I am able to help people have fun while practicing and feel more motivated. \

Edit : There are a full 111 participants, and it will be impossible for me to message all of them. I can only message $$$7$$$ people every hour.

Join this Discord Server. There are different channels for each rank and each time in GMT. This will allow you to quickly find the right people for yourself, rather than me making all the groups.

I'm trying to solve atcoder ABC167F. https://atcoder.jp/contests/abc167/tasks/abc167_f .

I started by questioning what conditions decide whether a concatenation is valid. We start by defining sum of a bracketed sequence, which is `count('(')-count(')')`

. I then found the sum of every string, and the smallest sum of a prefix of the string. They are denoted by $$$sum$$$ and $$$mnprefix$$$ in my code. If my current string is valid which is equivalent to $$$mnprefix\ge 0$$$ and has a sum of $$$x$$$, then a concatenation is valid if and only if $$$x+mnprefix\ge 0$$$ and our new sequnce has a sum of $$$x+sum$$$. Let's say we have two strings $$$a$$$ and $$$b$$$. Let $$$a.sum$$$ denote the sum of $$$a$$$ and the rest of the notation is deductible.

Let's say $$$a$$$ comes before $$$b$$$. Then the two conditions that need to be valid are $$$x\ge a.mnprefix$$$ and $$$x\ge b.mnprefix-a.sum$$$. So we want $$$\max(a.mnprefix, b.mnprefix-a.sum)\le \max(b.mnprefix, a.mnprefix - b.sum)$$$ for $$$a$$$ to be chosen before $$$b$$$. However my proof has one flaw, which is that it doesn't account for transitivity. I don't know how to prove another string $$$c$$$ will not affect my result, and how do I know my comparator function is transitive, as each string doesn't have an exact value, and the comparator values are differing according to the string being compared to.

If my solution is correct, can someone tell me if I have made an error in my implementation.

```
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb emplace_back
#define vi vector<int>
using namespace std;
struct brackets{
int mnprefix, sum;
brackets(const string &s){
mnprefix=0;
sum=0;
for(int i=0;i<s.size();i++){
if(s[i]=='('){
sum++;
}
if(s[i]==')'){
--sum;
}
mnprefix=min(mnprefix, sum);
}
}
bool operator<(const brackets &y){
return max(mnprefix, y.mnprefix-sum) < max(y.mnprefix, mnprefix - y.sum);
}
};
void solve(){
int n;
cin>>n;
vector<brackets> seq;
for(int i=0;i<n;i++){
string s;
cin>>s;
seq.pb(brackets(s));
}
sort(seq.begin(), seq.end());
int currsum=0;
for(int i=0;i<n;i++){
if(currsum+seq[i].mnprefix<0){
cout<<"No\n";
return;
}
currsum+=seq[i].sum;
}
if(currsum!=0){
cout<<"No\n";
return;
}
cout<<"Yes\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
//17/32 correct
```

Edit : nvm, I was using `abs(mnprefix)`

in my calculation but not in my code.

https://atcoder.jp/contests/abc160/tasks/abc160_f //Question link

https://atcoder.jp/contests/abc160/submissions/11324766 //My TLE submission

I need help in understanding how to reroot the tree in O(n) I think I have understood how to reroot the tree but I cannot understand how to do it for every node. For example

```
dp.resize(n,mp(-1,0)); //dp[u]=(the actual answer, size of subtree)
cout<<solve(0,0).first<<"\n";
dp[0]=mp(-1,0);
dp[edge[0][0]]=mp(-1,0);
cout<<solve(edge[0][0],edge[0][0]).first<<"\n";
```

The following code seems to correctly calculate the answer for the root node and it's first edge. But how do I reroot the tree in such a way that it goes to all edges and calculates the answer in O(n)?

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/06/2021 18:46:27 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|