Author: YouKn0wWho
Here
Note that $$$m \geq 1$$$, so $$$(y+1) > c$$$. So we can say that $$$ (y+1) \; is \; composite: \; y \geq 1$$$
So $$$K^{th}$$$ value of $$$y$$$ is ($$$K^{th}$$$ composite number $$$-1$$$ ). How can we find it given that $$$K \leq 10^9$$$?
Binary Search
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ll long long
#define nl '\n'
#define deb(x) cerr<<#x" = "<<x<<nl
#define in() ( { int a ; scanf("%d",&a); a; } )
const int N = 3e5 + 9;
const int mod = 1e9 + 7;
const int MAX = 10000005;
bool prime[MAX];
int prec[MAX];
vector<int> P;
const int LIM = 250;
int memo[LIM*LIM][LIM];
ll rec(ll N, int K) {
if (N <= 1 || K < 0) return 0;
if (N <= P[K]) return N-1;
if (N < MAX && P[K] * 1LL * P[K] > N) return N-1 - prec[N] + prec[P[K]];
bool ok = N < LIM*LIM && K < LIM;
if (ok && memo[N][K]) return memo[N][K];
ll ret = N/P[K] - rec(N/P[K], K-1) + rec(N, K-1);
if (ok) memo[N][K] = ret;
return ret;
}
ll count_primes(ll N) {
if (N < MAX) return prec[N];
int K = prec[(int)sqrt(N) + 1];
return N-1 - rec(N, K) + prec[P[K]];
}
void init_count_primes() {
prime[2] = true;
for (int i = 3; i < MAX; i += 2) prime[i] = true;
for (int i = 3; i*i < MAX; i += 2)
if (prime[i])
for (int j = i*i; j < MAX; j += i+i)
prime[j] = false;
for(int i=2; i<MAX; i++) if (prime[i]) P.push_back(i);
for(int i=1; i<MAX; i++) prec[i] = prec[i-1] + prime[i];
}
int32_t main()
{
init_count_primes();
int t; cin>>t;
assert(1<=t<=20);
while(t--){
int k; cin>>k;
assert(1<=k<=1000000000);
ll l=1, r=2e9;
ll ans=-1;
while(l<=r){
ll mid=(l+r)/2;
if(mid-count_primes(mid)-1<k) l=mid+1;
else ans=mid, r=mid-1;
}
assert(ans>0);
cout<<ans-1<<nl;
}
return 0;
}
Author: YouKn0wWho
Giveaway. The answer is always the length of the given string.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while(t--)
{
string s;
cin >> s;
cout<<s.size()<<endl;
}
}
Author: YouKn0wWho
Let $$$X$$$ $$$=$$$ xor of all elements of $$$A$$$.
if $$$X$$$ $$$=$$$ $$$0$$$, output $$$-1$$$.
Otherwise, consider the largest set bit in $$$X$$$. Clearly this bit occurs an odd number of times in the whole array. So if we partition the array at the index where this bit occurs for the first time, then the right part will contain an even number of occurrence of that bit. So that bit will be off in the xor of the remaining elements. So we will have an optimal answer.
Using OR queries and binary search find the first element that has this bit set. Let's call it $$$k$$$. If $$$k$$$ $$$=$$$ $$$n$$$, output $$$-1$$$, otherwise output $$$k$$$.
So we will use at most $$$18$$$ queries.
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ll long long
#define nl '\n'
#define deb(x) cerr<<#x" = "<<x<<nl
#define in() ( { int a ; scanf("%d",&a); a; } )
const int N = 3e5 + 9;
const int mod = 1e9 + 7;
int32_t main()
{
int n=in();
cout<<2<<' '<<1<<' '<<n<<nl;
cout.flush();
int x; cin>>x;
int b=-1;
for(int i=30; i>=0; i--) if((x>>i)&1){
b=i;
break;
}
if(b==-1){
cout<<"! -1\n";
cout.flush();
return 0;
}
int l=1, r=n-1, ans=-1;
while(l<=r){
int mid = (l+r)/2;
cout<<1<<' '<<1<<' '<<mid<<nl;
cout.flush();
int o; cin>>o;
if((o>>b)&1){
ans=mid;
r = mid-1;
}
else l = mid+1;
}
cout<<"! "<<ans<<nl;
cout.flush();
return 0;
}
Author: YouKn0wWho
Obvoiusly $$$G[n]= \left \lfloor{log \; n} \right \rfloor$$$. That's beacuse the good subsequence having maximum size is $$$1, 2, 4, 8, ...$$$
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ll long long
#define nl '\n'
#define deb(x) cerr<<#x" = "<<x<<nl
#define in() ( { int a ; scanf("%d",&a); a; } )
const int N = 3e5 + 9;
const int mod = 1e9 + 7;
int mp[50];
int get(int n)
{
if(n==0) return 0;
int i;
for( i=31;i>=0;i--) if(n&(1<<i)) break;
n-=(1<<i);
ll ans=1LL*(i+1)*(n+1);
return (ans+mp[i])%mod;
}
int32_t main()
{
int i,j,k,n,m,t,l,r;
for(i=1;i<32;i++){
mp[i]=mp[i-1]+1LL*i*(1LL<<(i-1))%mod;
mp[i]%=mod;
}
scanf("%d", &t);
assert(t>=1&&t<=1e5);
while(t--){
scanf("%d %d", &l, &r);
assert(l>=1&&l<=1e9);
assert(r>=l&&r<=1e9);
printf("%d\n", (get(r)-get(l-1)+mod)%mod);
}
return 0;
}
E. Playing On A Directed Graph
Author: YouKn0wWho
If there is a negative cycle then obviously no solution exists. Otherwise, set $$$P_i=$$$ the shortest path to the vertex $$$i$$$ from any vertex (including itself).
So we can use floyd-warshall or bellman-ford to solve the problem.
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ll long long
#define nl '\n'
#define deb(x) cerr<<#x" = "<<x<<nl
#define in() ( { int a ; scanf("%d",&a); a; } )
const int N = 505;
const int mod = 1e9 + 7;
int ans[N];
int d[N][N];
int32_t main()
{
int i,j,k,n,m,u,v,w;
cin>>n>>m;
assert(n>=2&&n<=500);
assert(m>=1&&m<=min(n*(n-1),(int)1e5));
for(i=1;i<=n;i++) for(j=1;j<=n;j++) d[i][j]=1e9,d[i][i]=0;
vector<pii> ed;
vector<int> we;
for(i=1;i<=m;i++){
cin>>u>>v>>w;
d[u][v]=w;
ed.eb(u,v);
we.eb(w);
assert(u>=1&&u<=n);
assert(v>=1&&v<=n);
assert(w>=-1e5&&w<=1e5);
assert(u!=v);
}
for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++){
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
for(i=1;i<=n;i++) if(d[i][i]<0){
cout<<"NO\n";
return 0;
}
cout<<"YES\n";
for(i=1;i<=n;i++) ans[i]=1e9;
for(i=1;i<=n;i++) for(j=1;j<=n;j++) ans[j]=min(ans[j],d[i][j]);
for(i=0;i<m;i++) assert(ans[ed[i].second]-ans[ed[i].first]<=we[i]);
for(i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n];
return 0;
}
///Before submit=>
/// *check for integer overflow,array bounds
/// *check for n=1
Author: YouKn0wWho
We have to erase the minimum sum of lengths of the edges such that an eulerian path exists in the graph.
#include <bits/stdc++.h>
#define fs first
#define sc second
#define mx 100005
#define mod 1000000007
#define pii pair<int, int>
#define ll long long
using namespace std;
const double pi = 3.1416;
int main()
{
int t;
scanf("%d", &t);
while(t--){
int n;
double l;
scanf("%d %lf", &n, &l);
assert(n >= 3);
double sum = l;
double nw = l;
double angle = (n-2)*pi/n;
double hehe = angle;
double eqAngle = angle/(n-2);
for(int i = 1; i<n-1; i++){
double bahu = sqrt(nw*nw + l*l - cos(angle)*2.0*nw*l);
sum += bahu;
//cout << angle << endl;
angle = hehe - (pi - angle - eqAngle);
nw = bahu;
// cout << bahu << " ... " << endl;
}
// cout << sum*2 << endl;
// assert(fabs(nw-l) < 1e-3);
printf("%.10f\n", (sum*n)/2.0 - ( n%2==1 ? 0: floor((n-2)/2)*l ));
}
return 0;
}
Author: YouKn0wWho
Let
We can rewrite it as
Let
So
Now for finding $$$n!$$$ we have to evaluate the polynomial $$$P$$$ on $$$\left \lfloor{\frac{n}{B}}\right \rfloor+1$$$ points $$$P(0), P(B), ..., P(\left \lfloor{\frac{n}{B}}\right \rfloor*B)$$$ and then we can multiply the remaining elements using brute force. Note that the remaining elements are less than $$$B$$$.
Now we can use multipoint evaluation for evaluating multiple points faster. So We have solved the problem!
But here is an idea of using the $$$32kb$$$ source code space we are given! Set $$$B=10^6$$$. Then we have to evaluate the polynomial on at most $$$1000$$$ points given that $$$n\leq 10^9$$$. We can evaluate them offline in $$$O(10^9)$$$ and save them in an array. Here $$$mod = 10^9+7$$$. So the array will occupy less than $$$10kb$$$ of space. So here we go! Now we can generate the value of $$$n!$$$ in $$$O(B)$$$ where $$$B=10^6$$$ in our case.
We can use the precalculation idea from above again. Note that the precalculation won't take more than $$$10$$$ seconds.
Now the solution to our given product for some $$$l$$$ and $$$r$$$ is $$$\frac{F(r)}{F(l-1)}$$$
#include <bits/stdc++.h>
#define fs first
#define sc second
#define mx 100005
#define mod 1000000007
#define pii pair<int, int>
#define ll long long
#define mkp make_pair
#define all(a) a.begin(),a.end()
using namespace std;
ll bigmod(ll a, ll p){
ll ret = 1;
while(p){
if(p&1) ret = ret * a % mod;
a = a * a % mod;
p /= 2;
}
return ret;
}
ll fact[2000]={682498929, 491101308, 76479948, 723816384, 67347853, 27368307, 625544428, 199888908, 888050723, 927880474, 281863274, 661224977, 623534362, 970055531, 261384175, 195888993, 66404266, 547665832, 109838563, 933245637, 724691727, 368925948, 268838846, 136026497, 112390913, 135498044, 217544623, 419363534, 500780548, 668123525, 128487469, 30977140, 522049725, 309058615, 386027524, 189239124, 148528617, 940567523, 917084264, 429277690, 996164327, 358655417, 568392357, 780072518, 462639908, 275105629, 909210595, 99199382, 703397904, 733333339, 97830135, 608823837, 256141983, 141827977, 696628828, 637939935, 811575797, 848924691, 131772368, 724464507, 272814771, 326159309, 456152084, 903466878, 92255682, 769795511, 373745190, 606241871, 825871994, 957939114, 435887178, 852304035, 663307737, 375297772, 217598709, 624148346, 671734977, 624500515, 748510389, 203191898, 423951674, 629786193, 672850561, 814362881, 823845496, 116667533, 256473217, 627655552, 245795606, 586445753, 172114298, 193781724, 778983779, 83868974, 315103615, 965785236, 492741665, 377329025, 847549272, 698611116};
ll multfact[2000]={611120140, 17897580,159967943,343237090,592951953,602244843,164013908,893236658,952101451,118482211,209920162,215152598,502381710,324159984,695459226,666860816,975716615,604726097,763034477,379041292,460748324,158354199,508213120,767279289,370470133,987651923,39242596,185475889,981761633,262769826,837005788, 681180371,661100686,908774984,38108703,396223792,793503000,819198011, 933664044,769608345,128783369,939038698,734053167,519165427,507816805,782246763,670871900,695337837,566025613,643867105, 476008438,909547109,980518787,678456808,218366494,992637363,7537905,20980780,379803548,410124767,587218502,463599811, 262065380,382170139,989269458,283943725,896112848,514669474,947602158,862475009,415829023,306830063,519359563,363545474, 758757919,497204956,969569909,39102155,126855068,631173350,6923144,794815151,253495907,554716148,685948839,513720461,309947752,492867651,326211127,657169128,464633342,764165057,613528541,579064017,114865160,794726205,431086582,512549494,460665448,34560};
const int lim = 10000000;
ll fun(ll n){
// if(n < 1) return 1;
if(n < lim) {
ll ret = 1, mult = 1;
for(int i = 1; i<=n; i++) {
ret = ret * i % mod;
mult = mult * ret % mod;
}
return bigmod(ret, n+2) * bigmod(mult, mod-2) % mod;
}
ll nfact = fact[n/lim-1];
ll mult = multfact[n/lim-1];
for(int i = (n/lim)*lim+1; i<=n; i++){
nfact = nfact * i % mod;
mult = mult * nfact % mod;
}
return bigmod(nfact, n+2) * bigmod(mult, mod-2) % mod;
}
int main()
{
// ll fact = 1;
// printf("ll fact[2000]={");
// vector<int> vt;
// ll mult = 1;
// for(int i = 1; i<mod; i++){
// fact = (fact * i) % mod;
// mult = mult * fact % mod;
// if(i%lim == 0){
// vt.push_back(mult);
// if(i/lim!=1) printf(", ");
// printf("%lld",fact);
// }
// }
// printf("};\n");
// printf("ll multfact[2000]={%d", vt[0]);
// vt.erase(vt.begin());
// for(int x : vt){
// printf(",%d",x);
// }
// printf("};");
// int fact = 1;
// int mult = 1;
// for(int i = 1; i<=lim; i++){
// fact = 1ll * fact * i % mod;
// mult = 1ll * mult * fact % mod;
// }
// cout << fact << endl;
// cout << mult << endl;
int t;
scanf("%d", &t);
while(t--){
int l, r;
scanf("%d %d", &l, &r);
ll mult = 1;
// for(int i = l; i<=r; i++)
// {
// mult = mult * bigmod(i, i+1) % mod;
// }
// cout << mult << " ";
cout << fun(r) * bigmod(fun(l-1), mod-2) % mod << endl;
}
return 0;
}
Author: YouKn0wWho
Notice that for any two non-negative integers $$$a$$$ and $$$b$$$, $$$a$$$ & $$$b$$$ $$$<$$$ $$$a$$$ and $$$a$$$ & $$$b$$$ $$$<$$$ $$$b$$$.
So the minimum value of all possible subset AND is the bitwise AND of all of the elements of the array. So just check if it less than $$$k$$$ or not.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while(t--)
{
int n,k,x;
cin >> n >> k ;
int an;
cin >> an;
n--;
while(n--)
{
cin >> x;
an&=x;
}
if(an<k) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
Author: foyaz05
Dp state for our solution is ( position , $$$c_0$$$ , $$$c_1$$$), here $$$c_0,c_1$$$ indicates the remaining count of zeroes and ones in the second string which we can still use to form a subsequence of the first string. For counting only the distinct permutations, from every position we go to the position of next zero and one and return 1 when we reach the state where $$$c_0=0$$$ and $$$c_1=0$$$.
Here the length of the strings can be up to $$$700$$$. Solutions with $$$O(N^3)$$$ memory won’t pass. So, we need to reduce a state. We can do bottom-up and get rid of the state position. The only difficulty here is that, in our usual bottom-up solutions, for any position, we need the dp values from the previous position. But here we are jumping from current position to the position with next zero or one(not necessarily position$$$+1$$$). For that, we can save dp values for the last one and last zero before current position and use those values to calculate dp for current position.
#include<bits/stdc++.h>
using namespace std;
#define N 710
#define mod 1000000007
int dp[2][N][N];
int all[2][N][N];
int pos[2],pre[2][N];
int cnt[2];
int main()
{
string s1,s2;
cin >> s1 >> s2;
pos[0]=pos[1]=-1;
for(int i=0; i<s1.size(); i++)
{
pre[0][i]=pos[0];
pre[1][i]=pos[1];
pos[s1[i]-'0']=i;
}
for(int i=0; i<s2.size(); i++) cnt[s2[i]-'0']++;
int ans=0;
for(int p=0; p<s1.size(); p++)
{
int nw=s1[p]-'0';
if(nw==0)
{
if(pre[nw][p]==-1)
{
dp[0][1][0]=1;
all[0][1][0]=1;
for(int i=1; i<=cnt[1]; i++)
{
dp[0][1][i]=all[1][0][i];
all[0][1][i]=all[1][0][i];
}
}
else
{
for(int i=cnt[0]; i>=0; i--)
{
for(int j=cnt[1]; j>=0; j--)
{
if(i>0) dp[0][i][j]=dp[0][i-1][j];
else dp[0][i][j]=0;
if(i>0) dp[0][i][j]+=all[1][i-1][j];
dp[0][i][j]%=mod;
all[0][i][j]+=dp[0][i][j];
all[0][i][j]%=mod;
}
}
}
memset(all[1],0,sizeof (all[1]));
ans+=dp[0][cnt[0]][cnt[1]];
ans%=mod;
}
else
{
if(pre[nw][p]==-1)
{
dp[1][0][1]=1;
all[1][0][1]=1;
for(int i=1; i<=cnt[0]; i++)
{
dp[1][i][1]=all[0][i][0];
all[1][i][1]=all[0][i][0];
}
}
else
{
for(int i=cnt[0]; i>=0; i--)
{
for(int j=cnt[1]; j>=0; j--)
{
if(j>0) dp[1][i][j]=dp[1][i][j-1];
else dp[1][i][j]=0;
if(j>0) dp[1][i][j]+=all[0][i][j-1];
dp[1][i][j]%=mod;
all[1][i][j]+=dp[1][i][j];
all[1][i][j]%=mod;
}
}
}
memset(all[0],0,sizeof (all[0]));
ans+=dp[1][cnt[0]][cnt[1]];
ans%=mod;
}
}
cout<<ans<<endl;
}
Author: YouKn0wWho
So we need to find the sum of the cost of all possible spanning trees in a complete graph where the weight of an edge from $$$i$$$ to $$$j$$$ is $$$i*j$$$.
Let's find the contribution of an edge $$$(i \rightarrow j)$$$ to the final answer. In how many spanning trees does this edge exist? Let's go deeper in Cayley's Formula. If there are $$$k$$$ connected components in a graph having $$$n$$$ nodes each having size $$$s_1, s_2,...,s_k$$$ then the number of ways to connect them is
Refer to this for proof.
So if we connect edge $$$i \rightarrow j$$$ and disconnect every other edge then the number of ways to connect every component is the same as the number of spanning trees in which this edge is included. And it equals to $$$2*n^{n-3}$$$. As this is a complete graph this value is the same for every other edge.
Let $$$C \; =$$$ sum of the costs of all edges in the graph. So our final answer is $$$2*n^{n-3}*C$$$.
Here $$$2*C \; =$$$ square of the sum of natural numbers up to $$$n$$$ — the sum of squared natural numbers up to $$$n$$$.
So we can solve the problem in $$$O(log \; n)$$$.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
ll bm(ll b,ll p)
{
ll ret=1;
b=b%mod;p=p%(mod-1);
while(p)
{
if(p&1) ret=(ret*b)%mod;
p/=2;
b=(b*b)%mod;
}
return ret;
}
int main()
{
int t;
ll n;
cin >> t;
while(t--)
{
cin >> n;
if(n==2)
{
cout<<"2"<<endl;
continue;
}
ll sum=n%mod*((n+1)%mod)%mod;
sum=sum*bm(2,mod-2)%mod;
sum=sum%mod*sum%mod;
ll tmp=n%mod*((n+1)%mod)%mod*((2LL*n+1)%mod)%mod;
tmp=tmp%mod*bm(6,mod-2)%mod;
ll ans=(sum-tmp+mod)%mod;
ans=ans%mod*bm(2,mod-2)%mod;
ans=ans%mod*2LL%mod*bm(n,n-3)%mod;
cout<<ans<<endl;
}
}
Author: ovis96
If the $$$1^{st}$$$ element of a special sequence is $$$x$$$ then the special sequence will look like
Let $$$C_i$$$ be the number of integers $$$p$$$ such that $$$p \mod m = i$$$
So the number of special sequences having $$$x$$$ as its first element is
#include <bits/stdc++.h>
#define fs first
#define sc second
#define mx 100005
#define mod 1000000007
#define pii pair<int, int>
#define ll long long
using namespace std;
int ara[mx*10];
ll bigmod(ll a, ll p){
ll ret = 1;
while(p){
if(p&1) ret = ret * a % mod;
a = a * a % mod;
p /= 2;
}
return ret;
}
void myassert(int x, int l, int r){
assert(x <= r);
assert(l <= x);
}
int main()
{
// freopen("in12.txt", "r", stdin);
map<int, int> mp;
int sz = 0;
int a;
scanf("%d", &sz);
for(int i = 0; i<sz; i++)
scanf("%d", &ara[i]);
assert(sz <= 1000000);
assert(1 <= sz);
int n, m;
scanf("%d %d", &n, &m);
myassert(n, 1, 1000000000);
myassert(m, 1, 1000000000);
for(int i = 0; i<sz; i++){
mp[ara[i]%m]++;
}
// cout << mp.size() << endl;
ll ans = 0;
for(auto p : mp){
if(p.first == ((m-p.first)%m)) ans = (ans + bigmod(p.second, n)) % mod;
else{
if(mp.find((m-p.first)%m) == mp.end()) continue;
ll nw = mp[(m-p.first)%m];
ll nwans = bigmod(p.second, n/2) * bigmod(nw, n-(n/2)) % mod;
ans = (ans + nwans) % mod;
}
}
printf("%lld\n", ans);
return 0;
}
Author: mk_Shahriar
TBA
~~~~~
~~~~~
When and how to submit for practice on toph? Is there a special procedure or we can do it after contest?
$$$-$$$ Is there a special procedure?
$$$-$$$ No
Problems are open now. GL & HF!
Okay thanks.
Is it configurable ( and hence only admins/ problem setters can allow submissions after contest )?
I ask, because I am unable to submit for another contest that I gave previously. I am new to toph.
Yes, it is configurable.
In problem E's editorial for the Bellman-Ford solution, I don't think it is correct to say that we find shortest distance from 1 as it may happen that there doesn't exist a path from 1 to some vertex. It is more like we initialize the distance of all vertices (instead of just only the source to 0) and then run an algorithm similar to Bellman-Ford.
UPD: Here's my code: https://ideone.com/Z5ylfX
Uh! My bad! Sorry. The editorial is updated. Thanks!
Its kinda still wrong, as you take the shortest path from the vertex to itself in case there's no other incoming edge into it. I think its more like $$$P_i$$$ = the shortest path to the vertex i from any vertex (including itself). In this case, the final value of any vertex comes out to be <= 0.
Anyways, I find it a little strange that even after solving a problem I'm not allowed to click the view editorial button on the problem page on TOPH as it says my achievements won't be considered in case I unlock it.
In problem A ,
2nd line .... y % (c+1) = c : c>=1 3rd line .... y % c = c-1 : c>=2
How can u say such ? What is the logic behind it ?
For example let y=11, c=5. So, 11 % 6 = 5, that doesn't mean that 11%5 =4 .