The answer is 'yes' if and only if there are exactly $$$n$$$ odd numbers.
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n,cnt[2]={0};
cin>>n;
for(int i=1,x;i<=n*2;i++)cin>>x,cnt[x%2]++;
if(cnt[0]==n)puts("Yes");
else puts("No");
}
return 0;
}
What kind of element in the set is important?
If $$$x$$$ is in the set, but $$$x-b$$$ is not, $$$x$$$ is important. Why?
How can we find all important elements?
First check specially if $$$b=1$$$.
Let's consider when $$$n$$$ is in $$$S$$$. The answer is when the smallest number $$$m$$$ in $$$S$$$ that $$$n\ \mathrm{mod}\ b=m\ \mathrm{mod}\ b$$$ is less than $$$n$$$. It's easy to see that a new case of $$$x\ \mathrm{mod}\ b$$$ can only appear when you use $$$\times a$$$ to generate a new element. So the smallest number $$$m$$$ in S that $$$m\ \mathrm{mod}\ b=k$$$ must be a power of $$$a$$$.
Find all powers of a that is smaller than $$$n$$$. If there is one $$$m=a^k$$$ that $$$n\ \mathrm{mod}\ b=m\ \mathrm{mod}\ b$$$, the answer is yes. Otherwise it's no. Time complexity is $$$O(\log n)$$$.
t=(int)(input())
for i in range(t):
w=input().split()
n=(int)(w[0])
a=(int)(w[1])
b=(int)(w[2])
if a==1 :
if (n-1)%b==0 :
print("Yes")
else :
print("No")
else :
t=1
flag=0
while t<=n :
if t%b==n%b:
flag=1
break
t=t*a
if flag==1:
print("Yes")
else :
print("No")
$$$f(n)$$$ is small.
For a given $$$x$$$, when is $$$f(n)$$$ equal to $$$x$$$?
Enumerate the value of $$$f(i)$$$. Since $$$f(n)=i$$$ means $$$lcm(1,2,...,i-1)\le n$$$, $$$f(n)$$$ will not be too big (less than $$$100$$$). The number of $$$k$$$s such that $$$f(k)=i$$$ is $$$\lfloor n/lcm(1,2,...,i-1)\rfloor -\lfloor n/lcm(1,2,...,i)\rfloor $$$. ($$$k$$$ should be divisible by $$$1\sim i-1$$$ but not $$$i$$$) So the answer is $$$\sum_{i>1} i(\lfloor n/lcm(1,2,...,i-1)\rfloor -\lfloor n/lcm(1,2,...,i)\rfloor )$$$.
We can also write the answer in another form, which is equivalent to the previous form:
#include<bits/stdc++.h>
#define int long long
#define re register
using namespace std;
int t,n;
const int M=1e9+7;
inline int gcd(re int x,re int y){
return y?gcd(y,x%y):x;
}
inline int LCM(re int x,re int y){
return x/gcd(x,y)*y;
}
signed main(){
scanf("%lld",&t);
while(t--){
scanf("%lld",&n);
re int G=1,ans=0;
for(re int i=1;G<=n;++i){
G=LCM(G,i);
if(G>n)break;
ans+=n/G;
}
printf("%lld\n",(ans+n)%M);
}
}
For each $$$x$$$, count how many $$$B$$$s make the final set contain $$$x$$$.
For each $$$x$$$, count how many $$$B$$$s make the final set contain $$$x$$$.
Let's say we have picked the $$$x$$$ in the $$$I$$$-th operation, call it $$$X$$$. Then, the subsequence we choose must satisfy the following conditions:
- It must contain the $$$i$$$-th operation (otherwise $$$X$$$ won't be added).
- Let $$$s$$$ denote the number of numbers less than $$$X$$$ in the current $$$T$$$. Whenever we meet a
-element in $$$S$$$ after the $$$i$$$-th operation, $$$s$$$ should be greater than $$$0$$$.
With those conditions, we can come up with the following dp.
Let $$$f(i,j)$$$ denote the number of subsequences of $$$a[1...i]$$$, that if we maintain $$$T$$$ with the subsequence, $$$s$$$ will become $$$j$$$.
Then we have the following transitions:
- $$$f(i-1,j)\to f(i,j)$$$ (when we don't include the $$$i$$$-th element is $$$S$$$, here $$$i\ne I$$$)
- $$$f(i-1,j)\to f(i,\max(j-1,0))$$$ (here, $$$i<I$$$, and the $$$i$$$-th element of $$$A$$$ is
-, so the number of numbers in $$$T$$$ less than $$$x$$$ decreases by one. If there is no such number, $$$s$$$ remains $$$0$$$) - $$$f(i-1,j)\to f(i,j-1)$$$ (here, $$$i>I$$$, and and the $$$i$$$-th element of $$$A$$$ is
-, so the number of numbers in $$$T$$$ less than $$$x$$$ decreases by one.) - $$$f(i-1,j)\to f(i,j)$$$ (here, the $$$i$$$-th element of $$$A$$$ is
+and its $$$x$$$ is greater than $$$X$$$) - $$$f(i-1,j)\to f(i,j+1)$$$ (here, the $$$i$$$-th element of $$$A$$$ is
+and its $$$x$$$ is less than $$$x$$$ or [equal to $$$x$$$ but $i>I$] ) [this is to deal with same elements]
Then we add $$$ans$$$ by $$$X\times \sum_{i\ge 0} f(n,i)$$$.
The time complexity is $$$O(n^3)$$$.
mod=998244353
n=(int)(input())
a=[0 for i in range(n+1)]
for i in range(1,n+1):
m=input().split()
if m[0]=="+":
a[i]=(int)(m[1])
ans=0
for t in range(1,n+1):
if a[t]==0:
continue
f=[[0 for i in range(n+2)] for j in range(n+2)]
f[0][0]=1
for i in range(1,n+1):
for j in range(0,i+1):
if a[i]==0:
if ((i<=t) or (j>0)):
f[i][max(j-1,0)]=(f[i][max(j-1,0)]+f[i-1][j])%mod
else :
if ((a[i]<a[t]) or ((a[i]==a[t]) and (i<t))):
f[i][j+1]=(f[i][j+1]+f[i-1][j])%mod
else :
f[i][j]=(f[i][j]+f[i-1][j])%mod
if (i!=t) :
f[i][j]=(f[i][j]+f[i-1][j])%mod
for i in range(0,n+1):
ans=(ans+f[n][i]*a[t])%mod
print(ans)
What does lexicographically mean?
Let's first calculate the number of permutation pair $$$(p,q)$$$s (with length $$$i$$$) that $$$p_1<q_1$$$ but $$$inv(p)>inv(q)$$$ ($$$inv(p)$$$ is the number of inversions in $$$p$$$). Call it $$$t_i$$$.
Let's enumerate $$$p_1=j$$$ and $$$q_1=k$$$, then $$$inv(p[2...i])-inv(q[2...i])>k-j$$$. ($$$inv(p)=inv(p[2...i])+j-1,inv(q)=inv(q[2...i])+k-1$$$, with $$$inv(p)>inv(q)$$$ we get the following.)
Precalculate $$$f(i,j)$$$: the number of permutation $$$p$$$s of length $$$i$$$ such that $$$inv(p)=j$$$. Let $$$s(i,j)$$$ be $$$\sum_{k\le j}f(i,k)$$$, then:
$$$f$$$ and $$$s$$$ can be calculated in $$$O(n^4)$$$ or $$$O(n^3)$$$ in the following way: if you insert $$$i$$$ into a permutation of length $$$i-1$$$ after the $$$i-1-p$$$-th element $$$(0\le p\le i-1)$$$, it will bring $$$p$$$ inversions into the permutation. So $$$f(i,j)=\sum_{j-i+1\le k\le j} f(i-1,k)$$$.
After calculating $$$t$$$, calculating the answer it easy. Let $$$ans_i$$$ be the answer for $$$n=i$$$, then
Consider if $$$p_1=q_1$$$. If so, there are $$$i$$$ choices of $$$p_1$$$, and $$$ans_{i-1}$$$ choices of the following $$$n-1$$$ numbers. Otherwise, there are $$$t_i$$$ choices.
Total complexity is $$$O(n^5)$$$, but it can be optimized to $$$O(n^4)$$$ if you consider the difference between $$$j-k$$$ only, and can be optimized to $$$O(n^3\log n)$$$ using FFT with arbitary mod (which we hope can't pass E2!).
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,mod,f[55][2005]={1},s[55][2005]={1},ans[55];
int main(){
cin>>n>>mod;
for(int i=1;i<=n*(n-1)/2;i++)s[0][i]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=n*(n-1)/2;j++){
if(j-i>=0)f[i][j]=(s[i-1][j]-s[i-1][j-i]+mod)%mod;
else f[i][j]=s[i-1][j];
s[i][j]=((j?s[i][j-1]:0)+f[i][j])%mod;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
for(int k=j+1;k<=i;k++){
for(int o=0;o<=(i-1)*(i-2)/2;o++){
int t=o-(k-j)-1;
if(t<0)continue;
ans[i]=(ans[i]+1ll*f[i-1][o]*s[i-1][t]%mod)%mod;
}
}
}
}
for(int i=2;i<=n;i++)ans[i]=(ans[i]+1ll*i*ans[i-1])%mod;
cout<<ans[n];
}
In E1 we calculated the number of permutation pairs from the number of permutations. Can we calculate the number of permutation pairs directly?
We recommend you to read E1's editorial first.
Let's directly count the number of permutation pairs $$$(p,q)$$$ of length $$$n$$$ with $$$inv(p)-inv(q)=k$$$, instead of counting it indirectly from "the number of permutation $$$p$$$s of length $$$i$$$ such that $$$inv(p)=j$$$.". Call this number $$$f(n,k)$$$.
We have an $$$n^4$$$ transition: $$$f(n,k)=\sum_{|i|<n} f(n-1,k-i)\times (n-|i|)$$$ (Consider where to insert $$$n$$$ in the first and second permutation. If the two places are indices $$$(I,J)$$$, then the delta of $$$inv(p)$$$ is $$$n-I$$$, the other is $$$n-J$$$, so the delta of difference is $$$J-I$$$. In $$$[1,n]$$$ there are $$$n-|J-I|$$$ pairs of integers with difference $$$J-I$$$.)
Let's speed it up. When $$$f(n,k)$$$ moves to $$$f(n,k+1)$$$, it looks like this: ($$$n=4$$$, as an example)
- $$$f(n-1,k-3)\times 1+f(n-1,k-2)\times 2+f(n-1,k-1)\times 3+f(n-1,k)\times 4+f(n-1,k+1)\times 3+f(n-1,k+2)\times 2+f(n-1,k+3)\times 1$$$
- $$$f(n-1,k-2)\times 1+f(n-1,k-1)\times 2+f(n-1,k)\times 3+f(n-1,k+1)\times 4+f(n-1,k+2)\times 3+f(n-1,k+3)\times 2+f(n-1,k+4)\times 1$$$
So with prefix sums $$$s$$$ ($$$s(i,j)=\sum_{k\le j} f(i,k)$$$) we can write $$$f(n,k+1)=f(n,k)-(s(n-1,k)-s(n-1,k-n))+(s(n-1,k+n)-s(n-1,k))$$$.
Note that the second indice of the array might be negative, so we should shift it by $$$130000$$$.
The memory complexity is $$$O(n^3)$$$, so we should only keep two layers of transition to optimize it to $$$O(n^2)$$$ (If implemented well, $$$O(n^3)$$$ memory solutions can also pass.)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int B=130000;
int n,mod,w[2][2*B+5],s[2][2*B+5],ans[505];
int main(){
cin>>n>>mod;
w[0][B]=s[0][B]=1;
for(int i=B;i<=2*B;i++)s[0][i]=1;
for(int i=1;i<=n;i++){
int curs=1,I=i&1,J=I^1;
memset(w[I],0,sizeof(w[I])),memset(s[I],0,sizeof(s[I]));
for(int u=i*(i-1)/2,j=-u+B;j<=u+B;j++){
w[I][j]=curs;
curs=(0ll+curs-s[J][j]+s[J][j-i]+s[J][j+i]-s[J][j]+2ll*mod)%mod;
}
for(int j=B-i*(i-1)/2,v=(i+2)*(i+1)/2+B;j<=v;j++)s[I][j]=(s[I][j-1]+w[I][j])%mod;
for(int j=1;j<i;j++)ans[i]=(ans[i]+1ll*(s[J][(i+1)*i/2+B]-s[J][j+B]+mod)%mod*(i-j))%mod;
}
for(int i=2;i<=n;i++)ans[i]=(ans[i]+1ll*i*ans[i-1])%mod;
cout<<ans[n];
}
Great problems
Good stuff, I liked C a lot, it made me think of LCM in a new way
can you please elaborate your thought about LCM..
yes plz how u thought of lcm i thought of 3 first then thought for 6 then 12 and come up with factorial approach but it hasn't worked.
I'll try to explain.
$$$n \leq 1e16$$$, so just starting a loop and trying to find an answer for each $$$i (1 \leq i \leq n)$$$ is a bad idea. This is why we need to "group" the answers. It is important to understand that the answers cannot be great. Because if $$$f(i) = x$$$, it means that i has divisors $$$2, 3, 4 \dots x - 1$$$, so $$$i \geq lcm (2, 3, 4 \dots x - 1)$$$
Let's try to figure out what $$$⌊n / lcm (1,2, \dots, i) ⌋$$$ means. This is the number of elements that are divisible by $$$2, 3, 4 \dots i$$$, so we have not counted the answer for them yet. Thus, based on the editiorial "The number of ks such that $$$f (k) = i$$$ is $$$⌊n / lcm (1,2, \dots, i — 1) ⌋ — ⌊n / lcm (1,2, \dots, i)⌋$$$" It means that $$$⌊n / lcm (1,2, ..., i — 1) ⌋$$$ is the number of elements that have "reached" us. And $$$⌊n / lcm (1,2, ..., i) ⌋$$$ is the number of elements for which the answer is greater than $$$i$$$. Thus, subtracting one from the other, we get the number of elements for which the answer is equal to $$$i$$$. And of course, sorry for my bad English, I tried my best.
My C++ solution:
121264752
Thanks for the clear explanation. Just one small correction, instead of
it probably should be
Oh, my fault. I will edit it immediately.
Thank you!
thanks man, after reading it looks simple logic but why i can't think of these logics in contest :(
noob me :{
I'm really happy that my comment was useful for somebody.
You are not noob) In my opinion it's absolutely normal, when you can't solve the problem during the contest.
P.S. I couldn't solve C too))
Do you think f(k) = i = 6, is possible ??
There will be no k such that f(k)=6.
Explaining using the formula derived in the editorial part
lcm(1,2,3,4,5) = 60 lcm(1,2,3,4,5,6) = 60 This will cancel out each other.
Logically If f(k)!=2 && f(k)!= 3 then f(k)!=6 this means k has already has divisors 2 and 3 which eventually means it has divisor 6.
There will me many numbers such as 6.
to know how many numbers in range 1 to n are divisable by all numbers from 1 to i it equals to n / lcm(1,2,3,..,i) for example :- if n = 15 and you want to know how many number divisable by 1, 2, 3 and 4 floor(15 / lcm(1,2,3,4)) = 1 there is just one number divisable by 1, 2, 3, and 4 and this number is 12.
tenks man
Thanks for the editorial
My C++ solution for the problem C (feel free to ignore the template): https://mirror.codeforces.com/contest/1542/submission/121274457. The key idea is for a $$$2 \leq k \leq n$$$ to be the minimum positive number that is not a divisor of a number $$$x$$$, all 1,...k-1 must be divisor of $$$x$$$, that is $$$lcm(1,...k-1)$$$ divides $$$x$$$. Thus we can iterate over $$$k$$$ and each time count how many such $$$x$$$ for each $$$k$$$, which is $$$n/lcm(1,..,k-1) - n/lcm(1,..,k)$$$. See the code for more details.
Which problem? I've only got B & D
https://codeforces.ml/contest/1542/submission/121271831 B
https://codeforces.ml/contest/1542/submission/121276656 D
Mathforces!
This one requires a lot more math, but it's not friendly to younger participants. And, this is an algorithm competition, not a math competition.
why is it not friendly? i think everybody should know smth about LCM. Also B was not hard at all. I am a young participant (i'm 13) and ABC weren't hard at all
smart russians.
Saying ABC weren't "hard at all" won't cut it mate. They were hard, for the average folks. I've been coding for almost 1.5+ years now, and could only solve A. I found a research paper on OEIS which was directly related to C, still couldn't code it up in time. Thank your stars (or rather your smart ass genes lol) that you're able to do such good level math problems at such a tender age. You probably are meant for this, keep solving!
Nobody is meant for anything, it's just the timing when they started. And btw you are comparing your present with his, he also learned to check prime from O(n) to O(sqrt(n)) at some point in time.
i also started about 1.5 years ago)
I guess he is just frustrated by the fact that the contest was just Math+ DP, out of which people struggle at both a bit... ig..
PS. like, i like geometry and DS based problems, but it has been a long time i haven't seen such problems in recent contests....
Anyhow its pretty Subjective, i felt yesterday's contest was pretty doable at least till C.
sorry, my english is bad. what is DS?
Data structures
Hard is a relative subject, some topics can be hard for someone, and easier for others. Age doesn't matter at all. This was a more math-focused contest (ABC all have math tag), and a mathematical approach is often harder for some.
Everyone plays games , and only some reach the top but all other plays because they enjoy playing it .
Beacuse your ability is weak but not the round is not friendly.And I think problem D is easier than B and C.So why this contest unfriendly?
Great Round, Great problems. Statements were short and crisp problem "C" is my personal favourite. Looking forward to see more such rounds. Thank you!!!
Although I didn't participate, I also think the problems especially C and D are wonderful!
When I was solving B, for some reason I typed "a^x" as "a*x" and spent almost all round to understand why extended euclidian algorithm doesn't work. Moral of the story: Don't tunnel vision, do your math.
Great round!
I spent over an hour on b since I put (n % (a ^ k))%b == 0 instead of (n — (a ^ k))%b == 0.
Nonetheless the problems were good, and I enjoyed the round
I think B is harder to think than D.
Imagine C is harder to think than D...
Can someone explain the second paragraph of $$$B$$$ tutorial?
Let us assume
nis present in the set.ncan be represented asx*a^k + y*b, wherex,k,yare whole numbers. Nown%b = (x*a^k + y*b)%b = (x*a^k)%b = x%b * (a^k)%b.xcan be any of the previous values in the set, used to generaten. Thus we can assumex = (x')*(a^k') + y*bandx%b = (x')%b * (a^k')%b. Eventually we can see thatx%bwill be of typea^kwherekwill be a whole number. Hence we can writen%b = (a^k)%b, givennis present in the set.I had a slightly different approach for problem C. So I will explain my solution and thinking process.
Initially I was not able to solve the problem. Then I remembered one thing that factorial of even small numbers is very large (like $$$50!$$$). So, this gave me direction to think that $$$f(n)$$$ cannot be very large. So I ran a test to see that when we multiply prime numbers up to $$$50$$$, it will exceed $$$10^{16}$$$.
I still had no clue how to solve this problem. Then I randomly wrote a number in prime factorization form. I saw that $$$f(n)$$$ can only be some power of only a single prime i.e. $$$f(n) = p^k$$$ where $$$p$$$ is some prime and $$$k$$$ is its power. I was able to prove this.
Now, I knew that $$$f(n)$$$ can only be some power of prime up to $$$50$$$. So, now if $$$f(n)=p^k$$$, then $$$n$$$ must have exactly $$$p^{k-1}$$$ in its prime factorization form because otherwise $$$p^{k-1}$$$ will be $$$f(n)$$$. Now, I had to think what else should $$$n$$$ must have in its prime factorization form. I observed that for some other prime $$$q$$$ its power $$$m$$$ must be such that $$$q^{m+1} > p^k$$$ because otherwise $$$q^{m+1}$$$ can be answer. Then I found a number $$$D$$$ satisfying the above requirements. Now, the number of multiples of $$$D$$$ minus the number of multiples of $$$D*p$$$ would give the numbers for which $$$f(n) = p^k$$$. Then I would just add contribution to answer. Note that we have to handle a corner case i.e. when $$$D$$$ exceeds $$$n$$$, then we don't take any contribution from $$$p^k$$$.
Me Too
I massively overcomplicated my solution (originally in Rust, translated to C++) and reading it again now I realize that it basically amounts to Um_nik's solution except mine is slightly faster because it only evaluates the numbers that change the lcm. Of course, it's nowhere near the TL so that doesn't even matter.
Any idea why this solution to B gives TLE? Is it some silly mistake? Cause I've pretty much followed the editorial.
m should be long long
m should be long long . if not , m may less than 0, so tle.
Can anyone analysis the time complexity of problem C for me pls?
Someone correct me if I'm wrong, I think it's O(nlogn) because for every i computing lcm involves computing gcd which is logn with Euclidean algorithm
So you mean there are 10^16 log 10^16 operations in worst case @@?
no, max(N) is about 40-50
Sorry that was a horrible mistake. The loop runs while lcm <= n, and I think by lcm(1,...,40) you passed 10^16, so it should be O(40 log(something))
Ok I get it thanks a lot
Can someone please guide me through the equivalence of both formulas in C?
math math math math math maTh MaTH MATH MATH MATH MATH MATH MATH MATH AAAAAAAAAAAAAAAAAAAA!!!!1!!!11!!!
These format of spoilers hurt my eye really bad, can you make it like this ? It will look much better.
Really a great contest! Kudos!
Nice contest.
- Team Atcoder Fan, 2021
Can you explain your D? It seems more crisp.
in the C Tutorial : "Since f(n)= i means lcm(1,2,...,i−1) ≤n " why? I don't understand this, can you explain it to me?
because 'i' is the minimum number not divisor of n. and n is divisible by all number (1 to i-1). Like what is the minimum number that divisible by all number (1 to i-1) ??? it's g = Lcm(1,,,,i-1). Now, if f(n) = i, that means (n % g == 0) and g <= n.
I think what they are actually trying to say is that it doesn't make sense to go to such an i where lcm(1,2,...,i-1)>n since the contribution for such an i would be zero.
why chinese people think,that math problems are more interesting than algorithmic or data structure?
Can someone help me understand how they thought of this DP (and it's states) in problem D?
The current editorial focuses more on implementation, less on the idea.
watch galen colin video.
When you have these expected value problems and you have to compute the total value (or expected value) of all sums, you can generally compute the total contribution of each term and add it separately.
I think this can somewhat be seen by putting all the subsets of sums with the # of times they get counted vertically. When you add all of them up, you just get one equation in the $$$n$$$ variables (for whatever $$$n$$$ is, here it's the number of terms that start with $$$+$$$). The coefficient of each variable here is the number of times it's counted across all subsets -- which is the same as its independent contribution. Then, you can proceed as above.
Look at my code for B, it's very funny compared to the original solution, but still my code passed all the tests. Here is the link: https://mirror.codeforces.com/contest/1542/submission/121210576
What are $$$p1$$$ and $$$q1$$$ in E1 editorial? And what do you mean by enumerating $$$p1$$$ and $$$q1$$$? feecIe6418
$$$p_1$$$ is the first element of $$$p$$$
Hi, I don't understand the editorial of problem B. Can someone please explain it to me?
Thanks
Here is my approach — Every element of the set can be expressed in the form $$${a^p + qb}$$$ where p and q are whole numbers. You can try writing the elements of the set in a tabular form to see it for yourself, intuitively. $$$1,1+b,1+2b,1+3b...$$$
$$$a,a+b,a+2b,a+3b...$$$ $$$a^2,a^2+b,a^2+2b,a^2+3b...$$$
We want to check if n is expressible in this form. To do this, iterate through p from 0 to any large enough value. For each value of p, check if $$$n = a^p + qb$$$, that is, ($$$n - a^p$$$)%b == 0. If this is true, the answer is YES. The loop terminates when $$$a^p$$$ becomes greater than n itself.
Does anyone have a different solution for E1?
froggyzhang had given a solution for e2 by using generating functions which i think is much easier than the official tutorial(which is also great!). Unluckily, it's in Chinese. And if anyone want to read it you can find it here.
My English is very bad, can anyone help me translate it into English? awa
I translated it into English here
Is there any recursive approach to solve D
I solved with recursive.
In B, is it true that if $$$n$$$ is equal to some power of $$$a$$$ then $$$n$$$ belongs to the set?
I had the following condition in my code:
and for some reason this gives a wrong answer. My reasoning was the following. If $$$1$$$ and $$$1 \cdot a$$$ are in the set then $$$1 \cdot a \cdot a$$$ must also be in the set and other powers e.g. $$$1 \cdot a \cdot a \cdot a$$$ as well. So if $$$a$$$ divides $$$n$$$ i.e. $$$n \pmod a == 0$$$ then $$$n$$$ should be in the set. Am I missing something trivial ????
n = 10, a = 5
Can someone explain in better/different words what the states in the DP for D actually represent? The editorial is not at all clear to me.
For each number x, to determine whether it's in the final set or not, we only need to consider those numbers that are smaller than x. Because those larger ones will always be popped after x is popped. If there are more than one x, we assume the one that appears first is smaller.
So, for each number x, define f[i][j] represent: after considering the ith operation, how many subsequences are there satisfies that there are j numbers in the set are smaller than x. (Remember to ignore the operation for the number x).
Then do the dynamic programming as the tutorial shows.
"If there are more than one x, we assume the one that appears first is smaller." Can you explain why so?
Actually, this is just an assumption to prevent some number being counted twice.
For example, the whole sequence is +1 +1 -.
After processing the whole sequence +1 +1 -, the final set is 1.
When we count the first +1, we will not count the sequence +1 +1 -, cause the first +1 is smaller, according to the assumption. The 1 in the final set is the second +1, we'll count this one when processing the second +1.
If you don't set the rule for equal elements, +1 +1 — will be counted for both +1, which is not what we want.
Now I got the intution behind it! Thnx!
You can have a look here and the parent comment, I tried to explain it with a picture:
What a nice math contest!(C is really nice)
Brilliant Problems!! Thanks for such a nice contest.
Could anyone explain why I got a time limit exceed in problem B test 2?
Thank you so much.
Because you used
intinstead oflong long.thank you, but I got a wrong answer in test 2 now.
Try this data, the answer is
Yes.Someone please explain solution of D. I am unable to comprehend the tutorial solution.
Can anyone explain me div 2 D solution
when coming up with dp solutions of taskE1 would you write the initial statements first(for(int i=1;i<=n*(n-1)/2;i++)s[0][i]=1;) or figure it out after the recursive statements? Because I had a hard time writing the initial statements,not knowing how many elements in the array should I initialize(Like why is s[0][0]=1 not needed). Please share some tips! and sorry for my bad English
I'M THE ONLY ONE FST ON D!!!!!!!!!!!!! :(
Vegetable!
Let me introduce froggyzhang's idea of problem E in English. You can find the original edition here(in Chinese).
I recommend you read the first and second paragraph of the official tutorial of E2 and the official tutorial of E1 before reading the following part of this article.
Assume $$$p_{i+1}=a$$$ and $$$q_{i+1}=b$$$, $$$a,b$$$ are their rank in their permutations.
So $$$inv(p)> inv(q)\Leftrightarrow inv(p[i+2,\dots n])-inv(q[i+2\dots n]\ge b-a+1$$$. So we just want to find the number of the pairs of permutations $$$p,q$$$ of length $$$n-i-1$$$ and $$$inv(p)-inv(q)\ge b-a$$$.
Precalculate $$$f(i,j)$$$ the number of the pairs of permutations $$$p,q$$$ and $$$inv(p)-inv(q)=j$$$. You can insert the numbers to the permutation from small to big and you can do it in $$$O(n^4)$$$ or $$$O(n^5)$$$ by using brute force(which is also mentioned in the official tutorial of E2).
You will find inserting number $$$i$$$'s generating function is as follow:
About the above part we can write it in to DP functions($$$a\to b$$$ means we add the value of $$$a$$$ to $$$b$$$).
And $$$\frac{1}{(x-1)^2}$$$ means we want to roll back twice. Just think what do you do when you $$$\times (x-1)^2$$$. So we can calculate $$$f$$$ in $$$O(n^3)$$$(both time and memory). We can only keep two layers of transition to optimize the memory to $$$O(n^2)$$$. And we can calculate suffix sum and the answer of the same prefix in $$$O(n^2)$$$.
You can read froggyzhang's code in his blog. You can find other details of coding in his code if you need.
In the implementation of problem D, why is the additional
if (i!=t) : f[i][j]=(f[i][j]+f[i-1][j])%modthere at the end of innermost for loop? Isn't the case where we skip the ith element already considered in each case?Please read the definition of the dp statement again. It means the number of sequences for $$$x$$$ exit at last if we add option $$$t$$$ to the sequences. So that we needn't consider option $$$t$$$.
Can anyone explain problem D. I didn't understand the solution in editorial.
This is my code for Div2 D
Someone please provide me any small testcase for debugging.
Thanks for the help. I got AC
Hey I don't know why I am wrong answer on test 2 of Problem B. This is my submission: https://mirror.codeforces.com/contest/1542/submission/121246560 Can you tell me what I am wrong. Thanks you
In your recursion
$$$n-c$$$ become negative so
just firstly check if $$$c>n$$$ then return false
if not then check for $$$n-c$$$
Just modified your code a bit
https://mirror.codeforces.com/contest/1542/submission/121831825
Edit: Understood my mistake.
Can someone tell me what's wrong in my logic for B: I observed a pattern for f(n) over numbers. Till every 6th number f(n) is 2 3 2 3 2, and for every 6th number, if the divisor upon dividing the number by 6 if odd then f(n) is 4 otherwise 5. So if n = 12, f(n) = 2 + 3 + 2 + 3 + 2 + 4 + 2 + 3 + 2 + 3 + 2 + 5 = 33. This logic is not working for the pretest 1 (10^16). Can anyone tell what's wrong in this?
When n is large enough,f(x) can be 7、9 or larger for some x,and it’s hard to find the law.
in tutorial for C, why ∑i>1i(⌊n/lcm(1,2,...,i−1)⌋−⌊n/lcm(1,2,...,i)⌋) is equal to ∑i≥1⌊n/lcm(1,2,...,i)⌋+n?
Sorry,I'm not sure abount Problem D.If there are multiple smallest elements and then we execute an erasing operation,what will happen?Will we erase all the smallest elements or just erase one of them?
just erase one of them.
Thank you and I have accepted now.That's a great problem. :)
Problem $$$E1$$$ is very nice. I have an alternative solution, which to me at least makes more sense.
In a lot of these problems where we have $$$p < q$$$ for some permutation/array $$$p, q$$$, we can break up $$$p, q$$$ into some interval $$$[1, \dots i]$$$ in which $$$p_j = q_j \forall j \in [1, i]$$$, $$$p_{i + 1} < q_{i + 1}$$$ and then an arbitrary permutation from $$$i + 2$$$ onwards. Perhaps my notation is a bit pedantic; maybe an example will help:
$$$p = 1 3 4 5 2$$$
$$$q = 1 3 2 4 5$$$
In this case, $$$p$$$ and $$$q$$$ share a common prefix of length $$$2$$$. Then, after that, we have that $$$4 > 2$$$, so we know that $$$p > q$$$. $$$[5, 2]$$$ and $$$[2, 5]$$$ can be respectively remapped to a new permutation ($$$[2, 5] \to [1, 2]$$$).
Okay, so let's assume that $$$p, q$$$ share some prefix of length $$$len$$$. Then, we know that $$$p_{len + 1} > q_{len + 1}$$$, so we can iterate over pairs $$$p_{len + 1} < q_{len + 1}$$$, which serve as a sort of distinguisher. If we let $$$dp[n][k]$$$ be the number of permutations of length $$$n$$$ with $$$k$$$ inversions, then we see that $$$ans[inv]$$$ — the number of pairs $$$p, q, p < q$$$ such that $$$\text{inv} (p) > \text{inv} (q)$$$ — can be written as:
$$$ans[inv] = ans[inv] + dp[N - len - 1][inv + q_{ind + 1} - p_{ind + 1}] \cdot \frac{N!}{(N - len)!}$$$
It remains to find $$$dp[n][k]$$$. The editorial has a good explanation on that, so I omit that detail.
Also needs some optimization since this is $$$\mathcal{O}(N^5)$$$. Can be optimizes if we iterate over $$$q_{ind + 1} - p_{ind + 1}$$$ instead.
Cheers!
EDIT: SAME IDEA CAN SOLVE E2 LET'S GOOOO: 145998673 First 2700 problem solved w/o editorial!!
In problem C,
I think there is an interesting pattern to observe...
Look...
For all Odd numbers,
x will always be 2.
For even numbers,
Please correct me If I am wrong...
This is wrong. For example, $$$f(60)=7$$$.
I solved this by observing such patterns (probably bad idea, but this all I can come up)
We can see 4 is alternating with 5, but the after the forth 4 is not 5 but 7 (at 60)
Still, 4 occurs every 6 path minus every 12 path (which can be 5, or 7, or anyelse)
Let's write g(x): times occurrences of a number x in length n.
g(4) = n/6 - n/12Let's check g(x) for some other x.
We can see a pattern here, but why g(6) = 0? also what's up with g(8)?
Turns out g(x) = 0 for all x which has more than one prime factor. (in this case 6 = 2*3)
And g(8)'s pattern is different because the pattern actually concerns with its prime factor (in this case 8's sole prime factor is 2).
For C :- — We need to min positive integer for each number 1 , 2 ... N which doesn't divide it.
- We can do grouping of numbers ( of x ). lets take an example first -> N / 2 = number of elements divisible by 2 -> N / 3 = number of elements divisible by 3 -> N / 6 = number of elements divisible by 6 = number of elements divisible by 2 and 3 = number of elements divisible by lcm(1,2,3) ie lcm(1,2,..i) elements N / lcm(1..i) -> numbers in N which are divisible by first i elements N / lcm(1...i-1) -> numbers in N which are divisible by first (i - 1) elements so N / lcm(i...i) - N / lcm(1.. i-1) = no of elements not divible by I. we can do it for all numbers till 42 since lcm of first 42 elements > 1e16.