Thank you for participating in the first ever Serbian Div. 3 Codeforces round!
Before the editorial, we are sorry for the big gap between problems C and D.
This was the first round we ever created (except for wxhtzdy).
We are striving to become better problem-setters and create more balanced problems-sets in the future.
Also a massive thanks to Vladosiya for giving us a chance to create a divison 3 round!
1878A - How Much Does Daytona Cost?
Author: wxhtzdy
Prepared by: ognjentesic, AndrewPav, AlphaMale06
When is the answer definitely "NO"?
What happens if there is no element equal to $$$k$$$ in the array?
What happens if there is an element equal to $$$k$$$ in the array?
#include <bits/stdc++.h>
using namespace std;
int main(){
int t; //read the number of test cases
cin >> t;
while(t--){
int n, k;
cin >> n >> k; //read n and k
bool ys=0; //bool value if true then there exists a subsegment which satisfies the condition, else it doesn't exist
for(int i=0; i< n; i++){
int a; //read the i-th element of the array
cin >> a;
if(a==k)ys=1; //if the element is equal to k, then the subsegment [i, i] has the most common element equal to k
}
if(ys)cout << "YES\n"; //output the answer
else cout << "NO\n";
}
}
Author: ognjentesic
Prepared by: ognjentesic, AlphaMale06
Watch parity.
What does the parity of $$$3 \cdot x$$$ depend on?
What parity are numbers which divide odd numbers?
#include <bits/stdc++.h>
using namespace std;
int main(){
int t; //read the number of test cases
cin >> t;
while(t--){
int n; //read n
cin >> n;
for(int i=0; i< n; i++)cout << i*2+1 << " "; //write the first n odd numbers in order
cout << '\n';
}
}
Author: AlphaMale06
Prepared by: ognjentesic, AlphaMale06
Prove that the answer for the second test case is "NO".
$$$ 1 + 2 + 3 \gt 5$$$
Determine the minimum and maximum sum achievable.
Prove that it's possible to construct the desired sequence for any requested sum between the minimum and maximum possible sum.
#include <iostream>
using namespace std;
int main(){
int t; //read the number of test cases
cin >> t;
while(t--){
long long n, x, k; //read n, x, k for each test case
cin >> n >> x >> k;
if(2*k>=x*(x+1) && 2*k<=n*(n+1)-(n-x)*(n-x+1)){ //check if k is between the minimum and maximum sum
cout << "YES\n";
}
else cout << "NO\n";
}
}
Author: AlphaMale06
Prepared by: ognjentesic, AlphaMale06
For each $$$i$$$, ($$$1 \le i \le k$$$), we can treat the substring $$$[l_i, r_i]$$$ as a seperate test case.
What happens when we make the same modification twice?
Does the order of the operations matter?
Try pre-processing the queries
#include <bits/stdc++.h>
using namespace std;
int main(){
int t; //number of test cases
cin >> t;
while(t--){
int n, k; //read the input
cin >> n >> k;
string s;
cin >> s;
int a[k]; int b[k];
for(int i=0; i< k; i++){cin >> a[i]; a[i]--;}
for(int i=0; i< k; i++){cin >> b[i]; b[i]--;}
int q;
cin >> q;
int cnt[n+1]={0}; //read and preprocess queries
for(int i=0; i< q; i++){
int x; cin >> x; cnt[x-1]++;
}
string ans="";
for(int i=0; i<k; i++){ //treat each interval as a seperate test case
string s1=s.substr(a[i], b[i]-a[i]+1);
int sum=0;
int l=a[i];
int r=b[i];
for(int j=l; j<=(l+r)/2; j++){
sum+=cnt[j]+cnt[r-j+l];
if(sum&1)swap(s1[j-l], s1[r-j]);
}
ans+=s1;
}
cout << ans << '\n';
}
}
Author: AndrewPav, AlphaMale06
Prepared by: ognjentesic, AndrewPav, OAleksa, AlphaMale06
Try calculating $$$f(l, r)$$$ bit by bit
Which condition has to hold true for all elements on a subsegment $$$[l,r]$$$, and for a certain bit, for that bit to be present in $$$f(l,r)$$$?
How can we check if that condition is true for a certain bit fast?
Try prefix sums.
Try binary search.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N =200003;
const int bits=30;
int pref[N][bits];
int a[N];
void Buildprefix(int n){ //Builds the prefix sums for each bit
for(int i=0; i< n; i++){
for(int j=0; j<30; j++){
if(a[i]&(1<<j)){
pref[i+1][j]=pref[i][j]+1;
}
else{
pref[i+1][j]=pref[i][j];
}
}
}
}
void solve(){
int n;
cin >> n;
for(int i=0; i< n; i++){
cin >> a[i];
}
Buildprefix(n);
int q;
cin >> q;
while(q--){
int l, k;
cin >> l >> k;
if(a[l-1]<k){
cout << -1 << '\n';
continue;
}
int lo=l;
int hi=n;
int ans=l;
while(lo<=hi){
int s=(lo+hi)/2;
int num=0;
for(int j=0; j< bits; j++){
if(pref[s][j]-pref[l-1][j]==s-l+1){
num+=(1<<j);
}
}
if(num>=k){
lo=s+1;
ans=max(ans, s);
}
else hi=s-1;
}
cout << ans << '\n';
}
}
int main(){
int t = 1;
cin >> t;
while(t--){
solve();
}
}
1878F - Vasilije Loves Number Theory
Author: ognjentesic, AlphaMale06
Prepared by: ognjentesic, AlphaMale06
What does the condition $$$gcd(a, n) = 1$$$ allow us to do?
How does any allowed operation affect $$$d(a \cdot n)$$$?
Try to prove that the answer is "YES" if $$$d(n)$$$ divides $$$n$$$.
Try to prove that the answer is "NO" otherwise.
How can you find and maintain the number of divisors quickly?
To make the implementation easier, try using the condition $$$d(n) \le 10^9$$$.
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const int N = 1000003;
map<int, int> powers; //key is a prime number, value is te highest powert
map<int, int> original_divisors; //same as map powers but isn't updated during queries, it's used to reset the powers
int smallest_divisor[N]; //precalculated smallest divisors to make factorization O(logx)
bool mark[N]; //marks numbers which aren't prime (used for sieve)
ll divisor_count = 1; //the number of divisors (updated during queries)
void prime(){ //calculates the smallers divisor for each number from 1 to N (sieve of erathosetenes)
smallest_divisor[1]=1;
smallest_divisor[2]=2;
for(int i=4; i<N; i+=2){
mark[i]=true;
smallest_divisor[i]=2;
}
for(int i=3; i<N; i+=2){
if(!mark[i]){
smallest_divisor[i]=i;
for(ll j = i*1ll*i; j<N; j+=2*i){
if(!mark[j]){
smallest_divisor[j]=i;
mark[j]=1;
}
}
}
}
}
//a function for factorizing a number (used to process queries and factorize n in the beginning)
//it also updates the highest prime which divides n (powers map), and the number of divisors of n (divisor_count)
void factorize(int x){
int p=0;
int current_divisor = 1;
while(x>1){ //while x has non 1 divisors, divide it by it's smallest divisor which isn't 1(smallers divisor if always prime)
if(smallest_divisor[x]!=current_divisor){
if(p>0){
divisor_count/=powers[current_divisor]+1;
powers[current_divisor]+=p;
divisor_count*=powers[current_divisor]+1;
}
p=1;
current_divisor=smallest_divisor[x];
}
else{
p++;
}
x/=smallest_divisor[x];
}
if(p>0){
divisor_count/=powers[current_divisor]+1;
powers[current_divisor]+=p;
divisor_count*=powers[current_divisor]+1;
}
return;
}
int main(){
prime(); //precalculate smallest divisors
int t;
cin >> t;
while(t--){
//read n and q
int n; int q;
cin >> n >> q;
//factorize n
factorize(n);
//since factorize updates the powers map, update the origional_divisors map too
for(auto prime : powers){
original_divisors[prime.first]=prime.second;
}
int original_divisor_count = divisor_count; //since factorize updates the divisor_count we update the original_divisor_count too
vector<int> queries; //storing previous queries
//processing queries
while(q--){
int query_type;
cin >> query_type;
if(query_type==1){ //query of type 1 (multiply n by x)
int x;
cin >> x;
factorize(x); //factorize x, update the powers map, and the number of divisors
queries.push_back(x); //add x to the list of previous queries
ll num=n;
for(int query : queries){ //check if the product of all previous queries and n is divisible by d(n)
num*=query;
num%=divisor_count;
}
if(num==0){ //if it is the answer is yes else the answer is no
cout << "YES\n";
}
else cout << "NO\n";
}
else{ //here we should reset everything related to the type 1 query
powers.clear(); //clear the powers map and set it to original divisors and powers
for(auto original_div : original_divisors){
powers[original_div.first]=original_div.second;
}
divisor_count=original_divisor_count; //restart the divisor_count
queries.clear(); //clear the queries (since we only need the queries since the previous type 2 query)
}
}
original_divisors.clear();
powers.clear();
divisor_count=1;
original_divisor_count =1;
if(t) cout << "\n";
}
}
Author: wxhtzdy
Prepared by: ognjentesic, OAleksa, AlphaMale06
How many vertices actually matter on the path from $$$x$$$ to $$$y$$$?
How do we find them?
Root the tree arbitrarily.
Try calculating the number of occurrences for each bit on the path from the root to a certain vertex.
Try binary search.
Try LCA (Lowest common ancestor).
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
#define int long long
const int maxn = 2e5 + 69;
const int k = 19;
const int bits = 30;
vector<int> g[maxn];
int n, q, a[maxn], up[maxn][k], tin[maxn], tout[maxn], timer, d[maxn];
int r[maxn][k];
int bst[maxn][bits];
void dfs(int v, int p, vector<int> b) {
tin[v] = ++timer;
up[v][0] = p;
r[v][0] = a[p];
d[v] = d[p] + 1;
for (int i = 0;i < bits;i++) {
bst[v][i] = b[i];
if (a[v] & (1 << i))
b[i] = v;
}
for (int i = 1;i < k;i++) {
up[v][i] = up[up[v][i - 1]][i - 1];
r[v][i] = r[v][i - 1] | r[up[v][i - 1]][i - 1];
}
for (auto u : g[v]) {
if (u != p)
dfs(u, v, b);
}
tout[v] = timer;
}
bool is_anc(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v) {
if(is_anc(u, v))
return u;
else if(is_anc(v, u))
return v;
for (int i = k - 1;i >= 0;i--) {
if (!is_anc(up[u][i], v) && up[u][i] > 0)
u = up[u][i];
}
return up[u][0];
}
int OR(int u, int dis) {
int res = a[u];
for (int j = 0;j < bits;j++) {
if (dis & (1 << j)) {
res |= r[u][j];
u = up[u][j];
}
}
return res;
}
int Qry(int u, int v) {
int lc = lca(u, v);
return OR(u, d[u] - d[lc]) | OR(v, d[v] - d[lc]);
}
signed main()
{
int tt = 1;
cin >> tt;
while(tt--) {
cin >> n;
timer = 0;
for (int i = 1;i <= n;i++)
g[i].clear();
for (int i = 1;i <= n;i++)
cin >> a[i];
for (int i = 1;i <= n - 1;i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
vector<int> temp(30, -1);
dfs(1, 0, temp);
cin >> q;
for (int i = 1;i <= q;i++) {
int x, y;
cin >> x >> y;
int LCA = lca(x, y);
vector<int> t;
t.push_back(x);
t.push_back(y);
for (int i = 0;i < bits;i++) {
if (bst[x][i] != -1 && is_anc(LCA, bst[x][i]))
t.push_back(bst[x][i]);
if (bst[y][i] != -1 && is_anc(LCA, bst[y][i]))
t.push_back(bst[y][i]);
}
int ans = __builtin_popcount(a[x]) + __builtin_popcount(a[y]);
for (auto p : t) {
int x1 = a[x], x2 = a[y];
x1 |= Qry(x, p);
x2 |= Qry(y, p);
ans = max(ans, 1ll * __builtin_popcount(x1) + __builtin_popcount(x2));
}
cout << ans << " ";
}
cout << "\n";
}
return 0;
}
Pretty balanced contenst
reverse madness was a cool one
Thanks for the fast Editorial.
Very interesting problem set, especially problem F
Why my solution is failing for F on tc 4 ;
Solution
Used pollard rho algorithm for d(n)
it usually fails on test 4 when n overflows
You have to check for divisibility by checking that all factors of divisor count are present in n, or like in the editorial
ok, thanks !!
because n can be much more than 1e9 only d(n) <= 1e9, but not n
One of the best Div3. D problem, first I just printed valued of a,b (cause nothing else was coming in my mind :)), and then i was not difficult to see that for each possible a there is unique b
The idea behind E is nice but you can just code a sparse table to handle the query part from the binary search.
Can you please help me see why the code below times out? This code is for E. Thank you very much!
Your check functions runs in $$$O(N)$$$
I have a slightly different implementation for Problem G . My approach is the same as the editorial (finding the selective nodes where the bitwise or changes).
However to find these nodes, instead of using binary search, we can maintain a map for every node. The map will have the $$$ closest $$$ $$$ ancestor $$$ to the current node for each distinct bitwise or possible. To find such ancestors we can use a map and iterate on it.
Implementation
This implementation got TLE. To fix the TLE we can use vector of pairs instead of using an map. New implementation
I'd like to rephrase the proof of Problem C.
The key observation is that we can always change the sum of k numbers from s to s + 1, given that s is not the maximal. The proof comes as follows. Assume that we have a set of k numbers which sum to s. Let denote the maximal among the k numbers as m. If m < n, we can always achieve s + 1 by replacing m with m + 1 and the proof is done. If the maximal is n, we can prove it by contradiction as shown in the tutorial, i.e., n, n — 1, ..., n — k + 1 will belong to the set. This set will yield the maximal and contradicts the assumption that s is not the maximal.
If m < n, we can always achieve s + 1 by replacing m with m + 1 and the proof is done.
m < n, so maximal is not n it is mentioned. even if it is n, we have to replace next maximal by +1 if it does not already exist. so on...
In problem G, I don't understand why for each bit, we choose the vertex z such that it contains that bit, and z is closest to x (or y). What happen if we choose z such that it is not the closest?
Because it would produce the same results with the closest one. Therefore we don't have to check that node
I don't know if I misunderstand something. I think that if we choose another vertex that is not the closest one, the result for the current bit which we want will stay the same, but we don't know whether bits in other positions will increase the answer or not.
That's why we need to consider both nodes
For example assume the path from $$$u$$$ to $$$v$$$ looks like this :
$$$000, 001, 100, 101, 000, 010$$$
Here are the path looks for each bits from $$$u$$$ to $$$v$$$ :
And for bits from $$$v$$$ to $$$u$$$ :
For the sake of explanation, let's number the nodes in the path with $$$1, 2, 3, 4, 5, 6$$$ (where $$$u=1$$$ and $$$v=6$$$)
Now the closest nodes with $$$u$$$ that has a bit on for each bits are : $$$2, 6, 3$$$
And the closest nodes with $$$v$$$ are : $$$4, 6, 4$$$
Notice that the only important nodes are $$$2, 3, 4, 6$$$
Node $$$5$$$ — for instance — is not important because from the perspective of $$$u$$$, the bit $$$0$$$ and $$$2$$$ will be "turned on" at node $$$2$$$ and $$$3$$$ respectively. While the bit $$$1$$$ is still "turned off" at node $$$5$$$
The key observation here is once the bit has turned on within a path, it will never be turned off again because the nature of the $$$\text{OR}$$$ operations
Okay, let me think about it for a while, since I don't strongly understand about the fact of picking the first occurrence will give us optimal answer. However, thanks for your help!
Maybe the way you view it should be something like this :
if the first occurence node produces the same outcome with the other nodes for the rest of the path, then it's sufficient for us to only check the first one and no need to check the rest
Could you provide an example when the second occurrence will be useless? The node 5 you provide above is not one of that type (it is totally 0)
Try this :
$$$101, 100, 011, 110, 101, 110$$$
The important nodes are respectively :
We can see that node $$$4$$$ is useless because it produces the same results as node $$$3$$$ and $$$5$$$
And node $$$2$$$ is useless because it produce the same as node $$$1$$$
Thanks, I get it now!
For problem E, we can calculate every position, the first 0 to the right of every bit.
Then for each query, iterate each bit from low to high, and check first 0 to the right. If the current bit of k is 1, it needs to satisfy all the smallest right end points that are not 0. If the current bit of k is 0, since we iterate from low to high, the rightmost non-0 can be greater than or equal to k.
I am not sure if my solution is correct, after all, it has not passed the system test. But I want to share my ideas with you, and the code is as follows:
https://mirror.codeforces.com/contest/1878/submission/225352692
I'v implemented this idea and got very simple code https://mirror.codeforces.com/contest/1878/submission/225492472
If someone prefers video explanations or interested in knowing how to think in a live contest or reach to a particular solution.
Here is my live screencast of solving problems [A -> E] (with detailed commentary in Hindi language).
PS: Don't judge me by my current rating :(
Hello. I have a question about Problem G. Why is the complexity not q*logA*logn*logn? Because finding the intersection points takes logA time, finding LCA takes logn time, and finally calculating by bits also takes logn time. I'm a little confused here，and my code get TLE.
E had a very long implementation, a little bit much for div3 question imo.
Have you seen the authors solution
Small tutorial doesn't necessarily mean small code, apparently me being noob in implementing long code also hurts. Creation of prefix of all bits and then applying binary search on all of it is too much imo.
Lol, you should have seen Problem G then
don't say sorry contest was very nice. All the problems were very interesting.
there's a very simple O(N+Q) solution for E 225432409
First, notice that the only positions of R that change a[L]&...&a[R] are those where the bit which was set in a[L] gets reset. Calculate the next positions where each bit gets reset and store them. Then for each query iterate over those "important" R positions and update the current value of a[L]&...&a[R]. If at a certain R the answer stops being greater than K, then the answer is R-1, otherwise the answer is N-1.
That is a O(NlogN + QlogN)
It's not logN, it's log(max a[i]), but fair enough, I guess it shouldn't be considered a constant
That's more than log N lol(n<=2e5, max(a) is 1e9)
my point is it's faster than the editorial solution while not being any more complex
In editorial its said it can be O(NlogN) with sparse tables(which is faster than yours) :)
Yeah, we said there is a $$$O(N \cdot \log(N))$$$ solution with sparse tables, and it's very simple (if you know sparse table). We said we allowed slower solutions because it's div. 3.
Can I solve the problem E using segment tree? For each query I can use binary search to find the value of "r" and find the value of f(l,r) using query method of segment tree. Time complexity O(q*logn*logn). But I am getting wrong answer after performing binary search.
Yes
You can even perform it $$$O(qlogn)$$$ when you are in some node in the segment tree, you see if the $$$and$$$ to the right child is still >=k then you go there. Else you go left.
May be there is a misunderstanding. How the complexity is O(qlogn)? ..ans every query by binary search and inside every transition of binary search finding "AND" of (l to mid) take O( q* (log(n) )^2)
sorry I was wrong I don't think my solution works
Yup..after the contest when i was going on through the questions and saw problem E,the first approach which came to my mind was of segment tree. I coded it and it got accepted. It's time complexity was of O(nlogn+q*logn*logn). It crossed 2s time limit. I got little astonished but then i saw that the maximum time limit was of 5s. Here is my code 225420310
I think the most easier way (I mean no need handle bit by bit) to do 1878E - Iva & Pav is to use seg tree. Here is my solution: 225454109
YES got it, and one thing the time complexity is better if we solve by using bit by bit than seg tree I guess ?
Using pref sums or sparse tables is lowest possible complexity in this problem, but segtree also passes with added log N factor :)
Can you please let me know if there exists a way to calculate bitwise between given range l and r using segment tree?
yea its pretty easy. Just search on internet AND segment tree(u can take lets say sum segment tree and just instead + write &). Just note that in E from this round u don't need update(its called modify in some sources), so just use qry and build function.
In D, I used binary search to get the indices, then calculated all the reversals I have to do, then just copy paste a solution of CSES substring reversals. Even if the CSES solution uses treaps, you still can just copy a solution without thinking about the treaps part
I've observed this thing regarding all ICPC-style contests on CF(i.e., div3/div4/edu rounds): fast solving doesn't matter as much as it matters in normal rounds.
For eg. contestants who solved the same no. of problems as me in this div3 but half an hour before me are ranked just 400 places ahead of me.
In problem C it should be the sum of 1 to n-k elements (4th line)
Awesome round in general. The problem are balanced and cover a lot of topic. I really like problem F.
However C is a little bit adhoc but I think it is fine.
And in my opinion, the gap between C and D is close enough.
Meanwhile problem G: range minimum query, binary lifting, LCA.
That's a Div3G though. Div3G can be near Div2E level, which is fine to have these kinds of algorithms
Yup
This is a snippet of neal's solution of D
Not getting why
max(x, l[i] + r[i] - x)is not being considered while doing the swap or even during the preprocessing of queries.Edit: Ok, got it. So the answer lies in this statement —
It is easy to see that the modifications x and n - x + 1 are equivalent.Can this CSES task be also solved by similar trick, or advanced DS like treap is mandatory?
The task cannot be solved the same way, because here the operations aren't symmetrical, and the order of operations matters.
Can Someone explain why my code gave TLE ? 225358802
Have you tried lowering your
bitscountto 30 or at least 31? Also you don't need 64-bit integers for this problem since all elements in the array are not greater than $$$10^9$$$.Yes , but it is still giving TLE 225510500
Your prefix array size
MAXis wrong, in the problem array can have up to $$$2e5$$$ integers.Accepted submission: 225521320, TLE: 225521499
Thank you so much , I didnt realise that simple mistake in contest :(
Fis a very nice problem. Thanks for this round. Hope we see you again.Thank you, it's my favorite problem I created
During testing, I found a nice offline solution for E.
The idea is to iterate from right to left and keep the value for each current prefix. When the values $$$f(i,i)$$$, $$$f(i,i+1)$$$, $$$f(i,i+2)$$$, ... are stored in some array, we can find the answer to some query by performing a binary search. In fact, we keep the right endpoints (denoted by $$$j$$$) in an array. We update the left endpoints ($$$i$$$) dynamically.
This is $$$O(n)$$$ memory. Updating the values when traversing from $$$i$$$ to $$$i-1$$$ can require up to $$$O(n)$$$ time. It seems like the total complexity is $$$O(n^2)$$$, which is untrue. In fact, it is amortized. Notice how we only need to update the values for which $$$f(i,j)$$$ changes. Modifying them decreases the total number of bits (among all values of $$$f$$$). The number of bits is $$$O(n \ log \ A)$$$, making the complexity $$$O(q \ log \ n + n \ log \ A )$$$.
Thank you for the round. Hope we see you again.
Man, there's an even simpler solution for B:
I know, I said there are many constructions, but this one is the easiest to prove I think.
I guess you're right. This one though also fits a possible restriction for the output like a_i <= 3 * 10^5.
Ahhhhhh
I tried to make the answer table, but the code is too long...
And I used a strange code:225314696
I solved problem E by using a segment tree to query each segment in logarithmic time but it TLE'd in python3 during the contest. I found out just now that using Pypy is much faster and the solution is easily accepted. Is pypy a reasonable choice for competitive programming or will I still commonly run into this runtime trouble in the future?
I don't know much about python but pypy is much faster than standard python compiler(found that while was working on round xD).
Hall of fame level task names and descriptions
Iva & Pav as best problem on codeforces ever :)
Agree :)
In problem D, instead of editorial's approach where it is taking into consideration the parity of number of operations as a condition to swap. I'm maintaining an array (1 based) which stores the number of operations on x [x = min(x, ri + li — x)]. For every query, I perform prefix[x]++ and take prefix sum of this array after all the queries. Now, if parity of number of operations (in the prefix sum array) before starting a new pair of (l, r) and number of operations at any index (in the prefix sum array) during the iteration in this pair is different, that would suggest a swap is required at that index. Otherwise, continue iterating. But I'm getting wrong answer as verdict. Please help me find where I'm going wrong.
Here is the submission link : https://mirror.codeforces.com/contest/1878/submission/225566736
You do realize that $$$a=min(x,ri+li−x)$$$ in problem's text is a gimmick because it can be simplified to $$$a=x$$$ always?
This means that in your query loop you can directly use $$$prefix[x]++$$$ without calculating $$$a$$$ and $$$b$$$ bounds at all.
Tutorial of D is terribly explained. Worst.
Could you elaborate?
AlphaMale06 may you explain how sparse table can help here ? as in what we need to implement in the sparse table related to this problem ? sparse tables as far as i know is used to find minimum in a subarray how here it works ?
Sparse table also used to find and , or , xor , min , max , sum etc in subarray
ok what will it be used here as ? its not finding xor or min or max or sum isnt here?
and
thanks AndrewPav Acanikolic73
here you go: https://cp-algorithms.com/data_structures/sparse-table.html
I personally feel D was easier than E. Maybe it were the long statements.
Yeah it is, but many people learn some topics that are really advanced for their rank(like segment tree, not including pref sums here because it's easy to learn that idea even for newbie) and that's why E has more solves than D.
anyone can explain any of the below solutions if possible ? they took very much less time or sometimes quite low memory space. https://mirror.codeforces.com/contest/1878/submission/225305916 by satyam343 https://mirror.codeforces.com/contest/1878/submission/225321019 by vgtcross https://mirror.codeforces.com/contest/1878/submission/225297136 by jiangly
I'm pretty sure they use sparse tables (the thing mentioned in the end of editorial for E), that's how they get a solution in $$$O(n \log(n))$$$
My solution (linked above) used a segment tree and it is $$$O(n \log^2 n)$$$ (that's why memory is so small). I don't know why it runs so fast.
Looking at the codes, neither of the other two linked solutions seem to use sparse tables. To me, it looks like they're using the fact that for fixed $$$l$$$, there are only at most $$$1 + \log_2 a = 31$$$ different values of bitwise and of subarray $$$[l, r]$$$ over all $$$r$$$. The "changing points" of the bitwise and can be calculated for each $$$l$$$ and stored in $$$O(n \log a)$$$ time and memory, and each query can be solved in $$$O(\log a)$$$ leading to a $$$O((n + q)\log a)$$$ solution.
thanks for the reply it really helped me to understand now vgtcross AlphaMale06. The '31' is because suppose the l is having all bits set then we can put 1 bit to 0 and then the and will reduce that bit only else it all remains set only . likewise we can have maximum 31 different numbers. is this interpretation right ?
Yes. Each bit can change value at most once so the total value can change 30 times, meaning that there can be 31 different values.
In problem E, how can we use sparse table to get $$$f(l,r)$$$ in $$$O(1)$$$? I thought it's still needed to reconstruct the segment in $$$O(log_2(r-l))$$$ time? (I don't know much about sparse tables)
If a query result can contain overlapping segments (min, max, or, and) then the sparse table only needs to look at two values for the answer. You find the largest power of 2 less than the range and calculate an overlap (eg for length 7 you do 2 queries of length 4 and include the value at position 4 twice).
I'm getting TLEd on G. What I am doing is, while binary searching the answer, I am fetching the ancestor. So basically the binary search is from 1 to the number of nodes in the path, and accordingly I'm fetching the count of bits. The implementation isn't the best, but it works. This is heavy on time because during my binary search I'm constantly binary lifting to find the node, so the binary search costs O( log(n) * log(max(a)) ). Combine that with query and it TLEs out. I cannot clearly understand how the editorial does it in O( log(n) + log(max(a) ). Any help will be appreciated, thanks in advance!
https://mirror.codeforces.com/contest/1878/submission/225749618
I couldn't get how to do binary search in $$$O( \log{(n)} + \log{(max(a)} )$$$ too. Also there is no binary search in G's solution that is attached to the editorial, so I couldn't understand it from the code either. But I somehow managed to get an AC with a solution similar to yours. I'm doing binary search on the path from LCA to x to find highest and lowest occurrence of each bit (and from LCA to y). On each iteration of binary search I use binary lifting, so my binary search costs $$$O(\log{^2(n)})$$$ and I'm doing it for each bit, so I have $$$O(\log{(max(a))} \cdot \log{^2(n)})$$$ per query and $$$O(q \cdot \log{(max(a))} \cdot \log{^2(n)})$$$ is my overall asymptotic. With some non-asymptotic optimizations it gets AC:
https://mirror.codeforces.com/contest/1878/submission/241103000
Sorry for necroposting :D
Cool, I'll have a look. Thanks!
For E, solution has mentioned that we can use sparse table also.I am learning segment tree currently..
I think segment tree can also be used here, am i correct?
yes
Good contest and wonderful tutorial! Thanks.
Extended proof for F which may be useful in the future: If $$$x$$$ and $$$y$$$ are coprime, then $$$d(x\cdot y) = d(x)\cdot d(y)$$$
We will set some definitions first. Let $$$x$$$ be a positive integer, and let $$$f$$$ be it's prime factorization. $$$f$$$ is defined such that $$$2^{f_1} \times 3^{f_2} \times \ldots \times p_n^{f_n} = x$$$ where $$$p_n$$$ is the $$$n$$$-th prime number.
By assuming the original conjecture to be true, we can also say that $$$d(x) = \prod_{i=1}^{n} d(p_i^{f_n})$$$ without loss of generality, since each term of the product contains a unique prime as their sole prime factor, making it coprime with any other term. Now we can expand $$$d(x)$$$ and $$$d(y)$$$ in the original theorem.
It is well-known that a traditional method of factor counting is $$$d(x) = \prod_{i=1}^{n} (f_i+1)$$$. It is also easy to see that $$$d(a^b) = b+1$$$ for prime $$$a$$$. Therefore, we may equate the expansion of our original conjecture to the traditional method of factor counting (which is known to be true), proving the original conjecture. $$$\square$$$
Problem C: Note that the sum of n over all test cases may exceed 2⋅105.
TC 05: 10000 194598 194598 10085825445 196910 196910 19386872505 193137 193137 6236620375 194427 194427 8160790120 ...
shouldn't O(n) also be accepted according to constraints? have i missed something?
the sum on $$$N$$$ over all the test cases $$$MAY$$$ exceed $$$2 * 10 ^ 5$$$
oof, need to turn off the autocomplete thanks
no problem, I thought also the same xD
Can any of you tell me how the E question was optimized with a hash table, the official question solution doesn't give any specific instructions.
For problem F solution 2, I was actually originally going to do this solution for the problem, but I was deterred because to find prime divisors and their exponents for $$$d(N)$$$, I have to find prime factorization of $$$d(N)$$$. Thus, we need to keep track of the smallest prime factor of numbers up to 1e9 (because $$$d(N)$$$ is bounded by 1e9) if we want logarithmic complexity. This uses too much memory. Has anyone figured out an implementation to find this prime factorization without use of smallest prime factor?
If you have all the primes up to sqrt(1e9) there are less than 3500 primes to check. You can loop through that list and if you don't find a factor then the value is a prime. It isn't logarithmic complexity, but fast enough as there are only 1000 queries.
However, in the editorial it is claimed that a logarithmic time complexity can be achieved for the prime factorization d(n) (it shows this in the time complexity). How is that achieved?
It's possible to store d(N) as the map of prime divisors adding/removing new divisors on each query and never needing to factor a large number. Each query can add at most 19 new divisors.
Hye guys!
You can see the detailed solutions for the problems A,B and C with proofs from my youtube video below:
https://youtu.be/odTQC7AOL3s?feature=shared
my segment tree solution for E 227542958
Is problem G possible in O(n log n)? The part where you calculate the ORs for each node can be optimized by noticing that the total value of the sums of the g function will increase by 1 in the first occurence of the bit and decrease by 1 in the last occurence of the bit (going from x to y). With that in mind we can just go from the closest important node to X to the last important node and keep track of the current sum.
However the bottleneck is still there in finding the important nodes. Is there a way to optimise it O(nlogn)?
why does this code fail 255033091 and when i change the line m=m1 to add_divs(n,m) it gets acc why if i change m=m1 it fails
I wrote a code for question E where I would be storing the suffix of the set bits occurring and using them to see what might be the last position of R where we might get a higher value and also checking the case where the value of our bits are same as K and we checked how many set bits are making the R larger. here is the code but it is failing. can anyone explain please.
My Code