I am sorry for the weak tests in B, for C being a little standardish and for misjudging the relative difficulties of E and F. Nevertheless, I hope you enjoyed the round. Here is the editorial. Do provide your feedback on each problem so that I can improve upon them the next time.
A. Subtle Substring Subtraction
Greedy
The answer depends on whether the length of $$$s$$$ is even or odd and on the first and last characters of $$$s$$$ if the length is odd.
The problem can be solved greedily. Let $$$n$$$ be the length of the given string.
- If the $$$n$$$ is even, it is always optimal for Alice to remove the whole string.
- If the $$$n$$$ is odd, it is always optimal for Alice to remove either $$$s_1s_2\ldots s_{n-1}$$$ or $$$s_2s_3\ldots s_n$$$ based on which gives the higher score and then Bob can remove the remaining character ($$$s_n$$$ or $$$s_1$$$ respectively). This is optimal because if Alice chooses to remove a substring of even length $$$2k$$$ such that $$$2k < n-1$$$ then Bob can remove the remaining $$$n-2k\geq 3$$$ characters, one of which will always be either $$$s_1$$$ or $$$s_n$$$, thus increasing Bob's score and decreasing Alice's score.
Prove that -
- Bob can win if and only if the length of the string is $$$1$$$.
- A draw is impossible.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int tc;
cin >> tc;
while(tc--)
{
string s;
cin >> s;
int n=s.length(),alice=0;
for(int i=0;i<n;i++)
alice += s[i]-'a'+1;
if(n%2==0)
cout << "Alice " << alice << '\n';
else
{
int bob;
if(s[0]<=s[n-1])
bob = s[0]-'a'+1;
else
bob = s[n-1]-'a'+1;
alice -= bob;
if(alice > bob)
cout << "Alice " << alice-bob << '\n';
else if(alice < bob)
cout << "Bob " << bob-alice << '\n';
else
cout << "Draw " << 0 << '\n';
}
}
}
B. A Perfectly Balanced String?
The string is perfectly balanced if it is periodic and the repeating pattern contains all distinct alphabets.
Let the number of distinct characters in $$$s$$$ be $$$k$$$ and length of $$$s$$$ be $$$n$$$. Then, $$$s$$$ will be perfectly balanced if and only if $$$s_{i}, s_{i+1}, \ldots, s_{i+k-1}$$$ are all pairwise distinct for every $$$i$$$ in the range $$$1\leq i\leq n-k+1$$$.
If there exists some $$$i$$$ in the range $$$1\leq i\leq n-k+1$$$ for which the characters $$$s_{i}, s_{i+1}, \ldots, s_{i+k-1}$$$ are not pairwise distinct, there will be atleast one character $$$u$$$ in the substring $$$t=s_{i} s_{i+1}\ldots s_{i+k-1}$$$ such that $$$f_t(u)\geq 2$$$ and by pigeonhole principle, there will be atleast one character $$$v$$$ present in $$$s$$$ such that $$$f_t(v)=0$$$. So, for the triple $$$(t,u,v)$$$, $$$f_t(u)-f_t(v)\geq 2$$$, violating the criteria for the $$$s$$$ to be perfectly balanced.
Suppose the following condition is met. Let's pick up any substring $$$t=s_is_{i+1}\ldots s_j$$$. Let's divide $$$t$$$ into $$$\Big\lceil \frac{j-i+1}{k}\Big\rceil$$$ blocks each of length $$$k$$$ except probably the last block. For each of these blocks, the frequency of all characters is equal to $$$1$$$ (because there are $$$k$$$ distinct characters in a block as well as in $$$s$$$) and for the last block, the frequency of some characters is equal to $$$1$$$ wheras the frequency of rest of the characters is equal to $$$0$$$. So, the frequency of some characters in $$$t$$$ will be equal to $$$\Big\lceil \frac{j-i+1}{k}\Big\rceil$$$ while that for the other characters will be equal to $$$\Big\lceil \frac{j-i+1}{k}\Big\rceil-1$$$. If we pick any two characters $$$u$$$ and $$$v$$$, $$$\lvert f_t(u)-f_t(v)\rvert\leq 1$$$ meaning that $$$s$$$ is perfectly balanced.
Prove that the condition is equivalent to the following two conditions -
- The first $$$k$$$ characters of $$$s$$$ are pairwise distinct.
- For each $$$i$$$ in the range $$$1\leq i\leq n-k$$$, $$$s_i=s_{i+k}$$$.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int tc;
cin >> tc;
while(tc--)
{
string s;
cin >> s;
int n = s.length();
set<char> c;
bool ok = true;
int k;
for(k=0;k<n;k++)
{
if(c.find(s[k])==c.end())
c.insert(s[k]);
else
break;
}
for(int i=k;i<n;i++)
{
if(s[i]!=s[i-k])
ok = false;
}
if(ok)
cout << "YES\n";
else
cout << "NO\n";
}
}
C. Palindrome Basis
The number of palindromes less than $$$4\cdot 10^4$$$ is relatively small.
The rest of the problem is quite similar to the classical partitions problem.
First, we need to observe that the number of palindromes less than $$$4\cdot 10^4$$$ is relatively very small. The number of $$$5$$$-digit palindromes are $$$300$$$ (enumerate all $$$3$$$-digit numbers less than $$$400$$$ and append the first two digits in the reverse order). Similarly, the number of $$$4$$$-digit, $$$3$$$-digit, $$$2$$$-digit and $$$1$$$-digit palindromes are $$$90$$$, $$$90$$$, $$$9$$$ and $$$9$$$ respectively, giving a total of $$$M=498$$$ palindromes.
Now, the problem can be solved just like the classical partitions problem which can be solved using Dynamic Programming.
Let $$$dp_{k,m} =$$$ Number of ways to partition the number $$$k$$$ using only the first $$$m$$$ palindromes. It is not hard to see that $$$dp_{k,m} = dp_{k,m-1} + dp_{k-p_m,m}$$$ where $$$p_m$$$ denotes the $$$m^{th}$$$ palindrome. The first term corresponds to the partitions of $$$k$$$ using only the first $$$m-1$$$ palindromes and the second term corresponds to those partitions of $$$k$$$ in which the $$$m^{th}$$$ palindrome has been used atleast once. As base cases, $$$dp_{k,1}=1$$$ and $$$dp_{1,m}=1$$$. The final answer for any $$$n$$$ will be $$$dp_{n,M}$$$.
The time and space complexity is $$$\mathcal{O}(n\cdot M)$$$.
Try to optimize the space complexity to $$$\mathcal{O}(n)$$$.
#include <bits/stdc++.h>
using namespace std;
const int N = 40004, M = 502;
const long long MOD = 1000000007;
long long dp[N][M];
int reverse(int n)
{
int r=0;
while(n>0)
{
r=r*10+n%10;
n/=10;
}
return r;
}
bool palindrome(int n)
{
return (reverse(n)==n);
}
int main()
{
vector<int> palin;
palin.push_back(0);
for(int i=1;i<2*N;i++)
{
if(palindrome(i))
palin.push_back(i);
}
for(int j=1;j<M;j++)
dp[0][j]=1;
for(int i=1;i<N;i++)
{
dp[i][0]=0;
for(int j=1;j<M;j++)
{
if(palin[j]<=i)
dp[i][j]=(dp[i][j-1]+dp[i-palin[j]][j])%MOD;
else
dp[i][j]=dp[i][j-1];
}
}
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tc;
cin >> tc;
while(tc--)
{
int n;
cin >> n;
cout << dp[n][M-1] << '\n';
}
}
D. Lost Arithmetic Progression
First check if all elements of $$$C$$$ are present in $$$B$$$ or not. If not, the answer is $$$0$$$.
Then check if the answer is infinite or not. It depends on only the first and last elements of $$$B$$$ and $$$C$$$.
If $$$p$$$ is the common difference of $$$A$$$ then $$$lcm(p,q)=r$$$. $$$p$$$ must necessarily be a factor of $$$r$$$ and $$$\mathcal{O}(\sqrt n)$$$ works here.
If all elements of $$$C$$$ are not present in $$$B$$$, then the answer is $$$0$$$. It is sufficient to check the following $$$4$$$ conditions to check if all elements of $$$C$$$ are present in $$$B$$$ or not -
- The first term of $$$B\leq$$$ The first term of $$$C$$$, i.e., $$$b\leq c$$$.
- The last term of $$$B\geq$$$ The last term of $$$C$$$, i.e., $$$b+(y-1)q\geq c+(z-1)r$$$.
- The common difference of $$$C$$$ must be divisible by the common difference of $$$B$$$, i.e., $$$r\bmod q=0$$$.
- The first term of $$$C$$$ must lie in $$$B$$$, i.e., $$$(c-b)\bmod q=0$$$.
Now suppose the following conditions are satisfied. Let's denote an Arithmetic Progression (AP) with first term $$$a$$$, common difference $$$d$$$ and $$$n$$$ number of terms by $$$[a,d,n]$$$.
If $$$b>c-r$$$ then there are infinite number of progressions which can be $$$A$$$ like $$$[c,r,z]$$$, $$$[c-r,r,z+1]$$$, $$$[c-2r,r,z+2]$$$ and so on. Similarly, if $$$b+(y-1)q<c+zr$$$, there are infinite number of progressions which can be $$$A$$$ like $$$[c,r,z]$$$, $$$[c,r,z+1]$$$, $$$[c,r,z+2]$$$ and so on.
Otherwise, there are a finite number of progressions which can be $$$A$$$. Let's count them. Let $$$A$$$ be the AP $$$[a,p,x]$$$ and $$$l=a+(x-1)p$$$. It can be seen that $$$lcm(p,q)=r$$$, $$$(c-a)\bmod p=0$$$, $$$a>c-r$$$ and $$$l<c+rz$$$ for any valid $$$A$$$. The first two conditions are trivial. The third condition is necessary because if $$$a\leq c-r$$$ then $$$c-r$$$ will always be present in both $$$A$$$ and $$$B$$$ contradicting the fact that $$$C$$$ contains all the terms common to $$$A$$$ and $$$B$$$. Similarly, the fourth condition is also necessary.
The only possible values $$$p$$$ can take according to the first condition are factors of $$$r$$$ which can be enumerated in $$$\mathcal{O}(\sqrt{r})$$$. The $$$lcm$$$ condition can be checked in $$$\mathcal{O}(\log r)$$$. For a particular value of $$$p$$$, there are $$$\frac{r}{p}$$$ possible values of $$$a$$$ satisfying conditions 2 and 3 and $$$\frac{r}{p}$$$ possible values of $$$l$$$ satisfying conditions 2 and 4. Thus, the answer is $$$\displaystyle\sum_{lcm(p,q)=r}\Big(\frac{r}{p}\Big)^2$$$.
Time complexity: $$$\mathcal{O}(t\,\sqrt{r}\,\log r)$$$
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long gcd(long long a,long long b)
{
if(b==0)
return a;
else
return gcd(b,a%b);
}
long long lcm(long long a,long long b)
{
long long g = gcd(a,b);
return (a*b)/g;
}
int main()
{
int tc;
cin >> tc;
while(tc--)
{
long long b,c,q,r,y,z;
cin >> b >> q >> y;
cin >> c >> r >> z;
long long e = b+q*(y-1);
long long f = c+r*(z-1);
if(c<b || c>e || f<b || f>e || r%q!=0 || (c-b)%q!=0)
cout << 0 << '\n';
else if(c-r<b || f+r>e)
cout << -1 << '\n';
else
{
long long ans = 0;
for(long long p=1;p*p<=r;p++)
{
if(r%p==0)
{
if(lcm(p,q)==r)
{
long long a = ((r/p)*(r/p))%MOD;
ans = (ans+a)%MOD;
}
if(p*p!=r && lcm(r/p,q)==r)
{
long long a = (p*p)%MOD;
ans = (ans+a)%MOD;
}
}
}
cout << ans << '\n';
}
}
}
E. Power or XOR?
All numbers in $$$A$$$ are powers of $$$2$$$ and the modulo is also a power of $$$2$$$ and $$$B_i\geq 1$$$.
Fix all operators in a particular subsegment as $$$\texttt{Power}$$$ and fix the operators around the segment as $$$\texttt{XOR}$$$. Find the contribution of this segment independent of other segments.
Maximum possible length for such a subsegment which can contribute to the answer is $$$20$$$.
Use Lucas' Theorem or Submasks DP or precomputation in order to count the parity of the number of valid unambiguous expressions in which the subsegment appears as in Hint 2.
Let's consider a subsegment $$$[A_{l}\wedge A_{l+1}\wedge A_{l+2}\wedge\ldots\wedge A_r]$$$. Let all the $$$\wedge$$$ symbols in this segment be replaced by $$$\texttt{Power}$$$ and the $$$\wedge$$$ symbols before $$$A_l$$$ and after $$$A_r$$$ be replaced by $$$\texttt{XOR}$$$. Then the value of this segment will not be affected by the rest of the expression. Moreover, out of all the expressions in which this segment appears as above, it will contribute the same value to the final answer. Since the final answer is also a $$$\texttt{XOR}$$$, if the segment $$$[l\ldots r]$$$ appears in the above mentioned form in odd number of valid unambiguous expressions, it will contribute $$$(\ldots((A_l^{A_{l+1}})^{A_{l+2}}) \ldots )^ {A_r}$$$ to the final answer else it will contribute nothing. We can find the contribution of each segment $$$[l\ldots r]$$$ independently for all values of $$$1\leq l < r \leq n$$$.
Now, there are two things we need to find out:
- How much $$$(\ldots((A_l^{A_{l+1}})^{A_{l+2}}) \ldots )^ {A_r}$$$ will contribute to the final answer, modulo $$$MOD = 2^{1048576}$$$.
- What is the parity of the count of valid unambiguous expressions, in which the segment $$$[l...r]$$$ appears as $$$... \oplus (\ldots((A_l^{A_{l+1}})^{A_{l+2}}) \ldots )^ {A_r} \oplus \ldots$$$.
Part 1: Notice that since all the elements of $$$A$$$ are powers of $$$2$$$, $$$S(l,r)=(\ldots((A_l^{A_{l+1}})^{A_{l+2}}) \ldots )^ {A_r}$$$ will also be a power of $$$2$$$. It means that $$$\texttt{XOR}$$$-ing it with answer will flip not more than $$$1$$$ bit in the answer. The rest of the calculations is pretty straightforward. $$$S(l,r) = 2^{B_l\cdot A_{l+1}\cdot A_{l+2}\cdot\ldots\cdot A_{r}}$$$ by properties of exponents. So, if it contributes to the answer, it will flip the $$$B_l\cdot A_{l+1}\cdot A_{l+2}\cdot\ldots\cdot A_{r}-$$$th bit of the answer. Now, note that if $$$S\geq 2^{1048576}$$$, it will have no effect on the answer because $$$S(l,r) \bmod 2^{1048576}$$$ will then be $$$0$$$. So, we care only for those $$$(l,r)$$$ for which $$$S(l,r) < 2^{1048576}$$$. Since $$$B_i\geq 1$$$, $$$A_i\geq 2$$$ and so, $$$r-l \leq 20$$$ because $$$2^{20} = 1048576$$$. Thus, it is sufficient to calculate $$$S(l,r)$$$ for only $$$20$$$ values of $$$r$$$ per value of $$$l$$$.
Part 2: We have used $$$r-l$$$ $$$\wedge$$$ operators as $$$\texttt{Power}$$$ and $$$0$$$, $$$1$$$ or $$$2$$$ $$$\wedge$$$ operators as $$$\texttt{XOR}$$$. Let's say that out of the $$$m$$$ unused operators, we need to use at least $$$q$$$ of them as $$$\texttt{XOR}$$$. Then the number of ways to do this is $$$\binom{m}{q}+\binom{m}{q+1}+\binom{m}{q+2}+\ldots+\binom{m}{m}$$$. Infact, instead of finding this value, we are only interested in finding whether it is even or odd. So, we need the value of $$$\big[\binom{m}{q}+\binom{m}{q+1}+\binom{m}{q+2}+\ldots+\binom{m}{m}\big]\bmod 2=$$$ $$$\big[\binom{m-1}{q}+\binom{m-1}{q-1} + \binom{m-1}{q+1}+\binom{m-1}{q} + \binom{m-1}{q+2}+\binom{m-1}{q+1} + \ldots + \binom{m-1}{m-1}+\binom{m-1}{m-2} + \binom{m}{m}\big] \bmod 2=$$$ $$$\big[\binom{m-1}{q-1} + \binom{m-1}{m-1} + \binom{m}{m}]\bmod 2 =$$$ $$$\binom{m-1}{q-1} \bmod 2$$$ as $$$(a + a) \bmod 2 = 0$$$ and $$$\binom{x}{x} = 1$$$ by definition. $$$\binom{m-1}{q-1} \bmod 2$$$ can be found using Lucas' Theorem. It turns out that $$$\binom{n}{r}$$$ is odd if and only if $$$r$$$ is a submask of $$$n$$$, i.e., $$$n | r = n$$$. Note that there are also many other ways to find this value (like Submasks DP or using the fact that $$$r-l\leq 20$$$ for precomputation) but this is the easiest one.
Some final notes -
- We can maintain the final answer as a binary string of length $$$1048576$$$. Find the value $$$X = B_l\cdot A_{l+1}\cdot A_{l+2}\cdot\ldots\cdot A_{r}$$$ and if the required parity is odd and $$$X < 1048576$$$, flip the $X-$th bit of the string.
- We need to be careful while calculating $$$B_l\cdot A_{l+1}\cdot A_{l+2}\cdot\ldots\cdot A_{r}$$$ since $$$A_i$$$ can be as large as $$$2^{1048575}$$$. But since we are interested in values that evaluate to something smaller than $$$1048576$$$, we will never try to multiply $$$A_i$$$ for anything with $$$B_i > 20$$$.
- Calculating the parity of $$$\binom{n}{r}$$$ in $$$\mathcal{O}(\log n)$$$ may time out. The constraints are strict enough.
Total time Complexity — $$$\mathcal{O}(n \log \log MOD)$$$
Try to solve the problem if $$$B_i\geq 0$$$ and if powers are calculated from right to left.
#include <bits/stdc++.h>
using namespace std;
const int N = 1048576;
long long b[N];
char ans[N];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,k;
cin >> n >> k;
for(int i=0;i<n;i++)
{
cin >> b[i];
}
for(int i=0;i<1048576;i++)
ans[i]='0';
for(int l=0;l<n;l++)
{
long long p=1;
for(int r=l;r<n;r++)
{
if(r==l)
p*=b[r];
else
{
if(b[r]>=20)
break;
else
p*=(1ll<<b[r]);
}
if(p>=1048576)
break;
int m = n-r+l-3;
int q = k-2;
if(l==0)
{
m++;
q++;
}
if(r==n-1)
{
m++;
q++;
}
if(m>=q && (m==0 || (q>0 && ((m-1)|(q-1))==(m-1))))
ans[p]='1'+'0'-ans[p];
}
}
bool start=false;
for(int i=1048575;i>=0;i--)
{
if(ans[i]=='0' && start)
cout << 0;
else if(ans[i]=='1')
{
cout << 1;
start=true;
}
}
if(!start)
cout << 0;
cout << '\n';
}
F. Anti-Theft Road Planning
The main goal is to assign numbers $$$A_{i,j}$$$ from $$$0$$$ to $$$1023$$$ to all buildings such that all buildings get distinct numbers and assign the road lengths between buildings $$$B_{x_1,y_1}$$$ and $$$B_{x_2,y_2}$$$ as $$$A_{x_1,y_1}\oplus A_{x_2,y_2}$$$. Among all such assignments, try to find the one which has the least sum of road lengths.
$$$2$$$-Dimensional Gray Code works
For now, lets ignore $$$n<=32$$$ and assume $$$n=32$$$.
Let's try to build the roads in such a way that no matter what path the thief takes to reach building $$$B_{i,j}$$$, the tracker will always return a fixed value $$$A_{i,j}$$$ such that all $$$A_{i,j}$$$ are distinct. Then by knowing the values returned by the tracker, one can easily find which building the theft occurred in. The main problem here is not to choose the lengths of the roads, since by choosing the length of road between buildings $$$B_{x_1,y_1}$$$ and $$$B_{x_2,y_2}$$$ as $$$A_{x_1,y_1}\oplus A_{x_2,y_2}$$$, one can always achieve this property. But there is a constraint which needs to be satisfied: The total length of all roads must not exceed $$$48000$$$. This is, in fact, a tight constraint (model solution uses $$$47616$$$) due to which one needs to choose the values of $$$A_{i,j}$$$ very efficiently.
Consider this problem — Find a permutation of numbers from $$$0$$$ to $$$2^m-1$$$ such that the sum of XOR of consecutive integers is minimized. The answer to this is Gray Code or Reflected Binary Code. In the standard Gray Code, bit $$$0$$$ is flipped $$$2^{m-1}$$$ times, bit $$$1$$$ is flipped $$$2^{m-2}$$$ times, bit $$$2$$$ is flipped $$$2^{m-3}$$$ times, $$$\ldots$$$, bit $$$m-1$$$ is flipped $$$1$$$ time. The idea is to use small bits more number of times compared to the larger ones.
Our task is to implement this idea in $$$2$$$-dimensions. Let's look at the algorithm used to build Gray Code. If we have the Gray Code for $$$k$$$ bits, it can be extended to $$$k+1$$$ bits by taking a copy of it, reflecting it and appending $$$1$$$ to the beginning of the reflected code and $$$0$$$ to the beginning of the original one. Here, if we have the Gray Code for $$$2^k \times 2^k$$$ matrix, it can be first extended to a Gray Code for $$$2^k \times 2^{k+1}$$$ matrix and this can further be extended to a Gray Code for $$$2^{k+1} \times 2^{k+1}$$$ matrix. If we build a $$$2^m \times 2^m$$$ matrix using this algorithm, the total length of roads used will be $$$\frac{3}{2}\cdot(4^m)\cdot(2^m-1)$$$. In this problem, $$$m = 5$$$. So, total length of roads used = $$$\frac{3}{2} \cdot 1024 \cdot 31 = 47616$$$.
Once this construction is complete, finding the buildings where thefts occurred is elementary since there can now be only one building corresponding to each value returned by the tracker.
Now, coming back to the original problem, we can simply take the first $$$n$$$ rows and the first $$$n$$$ columns from the constructed matrix. The cost won't increase and the properties still hold.
#include <bits/stdc++.h>
using namespace std;
const int N = 32;
int maxpower2(int n)
{
int p=1;
while(n%2==0)
{
p*=2;
n/=2;
}
return p;
}
int main()
{
int n,k;
cin >> n >> k;
int h[N][N-1];
for(int i=0;i<N;i++)
{
for(int j=1;j<=N-1;j++)
{
h[i][j-1]=maxpower2(j)*maxpower2(j);
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n-1;j++)
{
cout << h[i][j] << " ";
}
cout << endl;
}
int v[N-1][N];
for(int i=1;i<=N-1;i++)
{
for(int j=0;j<N;j++)
{
v[i-1][j]=2*maxpower2(i)*maxpower2(i);
}
}
for(int i=0;i<n-1;i++)
{
for(int j=0;j<n;j++)
{
cout << v[i][j] << " ";
}
cout << endl;
}
int b[n][n];
b[0][0]=0;
for(int j=1;j<n;j++)
{
b[0][j]=b[0][j-1]^h[0][j-1];
}
for(int i=1;i<n;i++)
{
for(int j=0;j<n;j++)
{
b[i][j]=b[i-1][j]^v[i-1][j];
}
}
map<int,pair<int,int> > m;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
m[b[i][j]]={i,j};
}
}
int y=0;
while(k--)
{
int x;
cin >> x;
pair<int,int> ans = m[x^y];
cout << ans.first+1 << " " << ans.second+1 << endl;
y^=x;
}
}
I spend at least 5 times as much time on B as I do on C ...
.
maybe its because U solve it too late , and it gave barely any points
They just could give me 0 pints not -78 !!
when you perform lower than ur current rating level ur rating will drop
Okay , I won't enter any contexts anymore fuck their judgment
You shouldnt think like , contest bring your rating to your real performance , sometimes you can have rating drops but in the end when you look for like a 1 year rating graph , you will see a linear growth
Lol, bye.
Fun fact: For the first five contests you participate, you get an extra few hundred rating points as technically unrated accounts start at 1500 (behind the scene), and after that, there is no such thing.
https://codeforces.net/blog/entry/77890 I think it is 1400.
You are right, my rating started to fall after my fifth contest. I always wondered why, thanks for this info.
If CF worked like that I could have been red...
I like the idea of "I solved A, so I get some points" ;) We good looking people must stick together!
I couldnt understand how do we prevent counting the same thing over and over in C
instead of counting for T test cases, you only count once for all the possible values of n and then get the answer for each test case in O(1). So your final answer would be O(498*N + T), not O(T*N*498). I hope that it helps.
in the editorial of problem C, aren't there only M = 498 palindromes?
Yeah, you are right. It was a typing error and has been fixed now.
Here are the video Solutions for A-D in case someone is interested.
/
If you prefer command line, checkout CF Doctor for more flexibility and faster feedback.
If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.
If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).
Finally reached green :))
Thanks for the fast editorial!
For problem C, I don't get why the second term of the dp is $$$dp_{k-p_m, m}$$$ but not $$$dp_{k-p_m, m-1}$$$, because we have the mth palindrome number fixed and then we have m-1 other palindromes that need to be chosen to give our answer
Because if we can use the same number more than once, so even if we use the mth palindrome number ending at k, we can still use all other m palindrome numbers
Because you still need to use pm to construct k-pm
Problem F
Hint1 says "try to find the one which has the least sum of road lengths."
I want to know the proof that 47616 is the least sum.
Update: My bad, the solution below is worse than the standard solution. It should be $$$x_k=16x_{k-1}+3\times 2^k$$$. Apologies for incovenience.
I don't know whether my solution reaches the least sum possible, but it seems much better than the one given in the tutorial.
Let's recursively construct the matrix $$$A$$$ mentioned in the tutorial. We are going to construct a $$$2^k\times 2^k$$$ matrix $$$A_k$$$ for each $$$k\in [0,5]$$$, thus giving a solution to the original problem by taking the first $$$n$$$ rows and columns of $$$A_5$$$.
The base case $$$A_0$$$ is simple, with a single $$$0$$$. Here is my way to get $$$A_k(k\geq 1)$$$ by $$$A_{k-1}$$$: flip $$$A_{k-1}$$$ to its right side to form a $$$2^{k-1}\times 2^k$$$ matrix (let's say, $$$B_k$$$), then flip $$$B_k$$$ to its down side to form a $$$2^k\times 2^k$$$ matrix $$$C_k$$$. Finally, we multiply each element in $$$C_k$$$ by $$$4$$$, and add $$$0,1,2,3$$$ to the up-left, up-right, down-left, and down-right part of the matrix respectively to form $$$A_k$$$ (by the up-left part I mean the submatrix consisting of elements in both the first $$$2^{k-1}$$$ rows and first $$$2^{k-1}$$$ columns, the other three are defined in similar ways).
Let $$$x_k$$$ be the sum of length of edges in $$$A_k$$$. One can find that $$$x_0=0$$$, and $$$x_k=4x_{k-1}+3\times 2^k$$$. By using the calculator it turns out that $$$x_5=2976$$$, far lower than the problem's original constraints.
Do you have an implementation?
Finally able to use some standard dp I learnt in a rated contest. Love it! XD.
Is C too standard?
I have a solution for problem F that constructs the same grid but with a completely different intuition. So let's say for a fixed row, all the values should be the same, that way you can know if you have passed that row before. Since if you ever make a "redundant" move, you will have to cross it again and the xor will cancel out. The same logic applies to the columns. So then you try to use 5 bits to manipulate the information for rows and 5 bits for the columns. Think about the line that evenly splits the rows into two halves. If you put a line of all of the same bit there, simply by checking if that bit is on, you can see which halves of the partition the rows is a part of. Then you have a smaller problem of half the rows to deal with. Finally, when there is only 1 row left, you can just leave the last bit on to check if it has crossed that row or not. The same logic applies to the columns. Now you also have to pick the bits rows to manipulate and the bits the columns manipulate separately. I found that the choice of
fits within the limit of $$$48000$$$. To construct the answer itself, you check if a certain bit is on, and if it is, you update the respective row/column value and also xor x to make sure that the contribution of the prefix is considered.
My implementation of the idea is here.
Have the same logic in my solution.
I like B
In editorial for problem B
s will be perfectly balanced if and only if si,si+1,…,si+k are all pairwise distinct
shoudn't it be si,si+1,…,si+k-1 since there are k distinct chars
Yes, it has been corrected now.
My A problem was garbled but I passed the in-match test and got RE after the match because the array was opened too small.How happy I was at the end of the race and how sad I was after the retest.。゚(゚´Д`゚)゚。
Here is another way to calculate $$$\binom{n}{m} \bmod 2$$$. We know that $$$\binom{n}{m} = \frac{n!}{m!(n - m)!}$$$. Define $$$P(n) = \max\{k : 2^k | n!\} = \sum_{i = 1}^{+\infty} \lfloor \frac{n}{2^i} \rfloor$$$. Then $$$\binom{n}{m} \bmod 2 = 1$$$ iff $$$P(n) - P(m) - P(n - m) = 0$$$.
Obviously, we can calculate $$$P(n)$$$ in $$$O(\log n)$$$ time, but here is a more efficient way. Suppose $$$n = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_m}$$$. Then
Obviously, $$$m = \text{popcount}(n)$$$, the number of $$$1$$$(s) in binary form of $$$n$$$, which can be calculated fast in C++ with
__builtin_popcount(n)
or__builtin_popcountll(n)
(whenn
islong long
type). This improvement helped me from TLE to AC, and shows that__builtin_popcount
really has very small constant. :PIt's Legendre formula.
easer way is user lucus thero, (n+m, n)(i.e., n+mCn) is even if (n^m == n&m) so here ncr is even iff (n-r)^r == (n-r)&r https://math.stackexchange.com/questions/11002/cn-p-even-or-odd
I have coded almost the same solution (with same time complexity) for 1673C - Palindrome Basis but still TLE! Can someone help me understand why?
You recompute $$$dp$$$ for every testcase, so the number of operations is on the order $$$10^4 \times 4 \cdot 10^4 \times 500 = 2 \cdot 10^{11}$$$.
Instead precompute the $$$dp$$$ table once before all testcases, then simply output $$$dp[n][sum]$$$ in each test case.
Thank you so much!
i solved A and B after contest
Hey if some one can tell me what is the max size of vector we can have of long long int in c++? AS for problem B I had something of 1e6 but neither it gave MLE nor any other error.
One long long int occupies 8 bytes. The array of 1M values itself occupies 8 Mbytes of memory. vector ocupies more but not twice. How many arrays do you create?
actually it was vector not array and its maximum size will be 26*2*1e5 155418148
you can check here . I am doing same with array and its giving run time error with array in my own system but for vector its accepting I don't know why though
I need a help, in problem B firstly we need to find out that how many distinctive characters are there. So, i wrote a function in C to find out the number of elements which are distinctive. So my question is: What is the more efficient way to find out the distinctive elements in a string? here is my code in C:
There are only 26 letters. You could make an array of 26 zeroes and mark with 1 every letter found. The sum of the array is an answer.
The Bonus Tasks are really educational !! Thanks a lot
In editorial for B, do you mean $$$s_i, s_{i+1}, \dots s_{i+k-1}$$$
For the editorial of Problem D:
Could you explain why
For a particular value of p, there are r/p possible values of a satisfying conditions 2 and 3 and r/p possible values of l satisfying conditions 2 and 4
?Given p is a factor of r which we take as common difference of array A. Then let elements of C be x1 x2 x3 x4....xn the number of terms of A b/w xi and xi+1 will be (x2-x1)/p-1= r/p-1
before x1 there could be thus (r/p-1) +1(no number to left of x1) = r/p numbers this because the number x0=x1-r
x0 is not in C which implies it is not in A since x0 = x1-k*q (r=k*q) ( Not taking infinity case into consideration here)
Thanks, I got it!
Can someone explain how to extend 2^k*2^k gray code to 2^k*2^(k+1) please?
I have a very simple solution for problem F:
First, lets look at the 1d version of the problem. Recall that the action of $$$+1$$$ or $$$-1$$$ is just flipping the first few bits of the number in binary representation. Firstly, 0-index the buildings. For edge between $$$i$$$ and $$$i+1$$$, we will assign the length as the highest power of 2 that divides $$$i+1$$$. For each query, we will check through the bits of $$$re$$$ (the number returned by the interactor). if the $$$ith$$$ bit is on, we will filp the first $$$i$$$ bits of the current $$$x$$$ coordinate.
The sum of length, if $$$n$$$ is a perfect power of 2, is $$$n/2\times\log(n)$$$. Proof is left to the reader.
By implementing for the $$$x$$$ coordinate on odd bit positions and $$$y$$$ coordinate on even bit positions, the sum is exactly $$$47616$$$. Proof is again, very simple and left to the reader.
Implementation, which is quite short and pretty: here
Can anyone explain how the dp is working for problem C Palindrome Basis?? If anyone can share some resources then also it will be helpful.
I think the editorial has skipped a possible intuition for the dp states and transitions under the cover of an existing standard problem.
During my upsolving I thought like this :-
Since the problem states that sequences are differentiated solely on the basis of frequencies, why not think in terms of sorted sequences.
I find out the list of palindromes in sorted order first.
It's easy to see that if two sorted sequences are the same then they will have the same frequencies.
My states for dp are :- $$$dp_{value,last}$$$
basically the current sequence has a sum = value and we had appended some element x as the latest element which can be <= last.
$$$dp_{value,last} = dp_{value,last−1} + dp_{value−p_{last},last}$$$
So we can either have a sequence whose sum is = value and the latest element appended is <= last $$$-$$$ 1 and we do not append anything or we can have a sequence where we append $$$p_{last}$$$, in that case, our sequence's former last element should have been <= last and also its sum should be = $$$value - p_{last}$$$
so transitions are just the same as in the editorial
This is one way to think 'intuitively' about the states perhaps there are other ways to go about it too.
My solution for B was this:
Assume $$$S$$$ — set of distinct letters in string $$$s$$$. Let's check every substring $$$s_iAs_j$$$, where $$$s_i = s_j = c,\,c \not\in A$$$ for every $$$c \in S$$$. Note that $$$A$$$ can be empty ($$$A = \emptyset$$$).
We give answer NO if there is letter $$$\hat c \ne c$$$ such that $$$\hat c \in S$$$ and $$$\hat c \not\in A$$$. That means that substring $$$s_i A s_j$$$ has two letters $$$c$$$ and zero letters $$$\hat c$$$. Otherwise the answer is YES.
My submission: 155416323
P.S. I guess there might be a problem with time complexity since we have two nested cycles for letters $$$a...z$$$. But I think either we find NO fast, either the second cycle will run only each $$$k$$$ iterations, where $$$k$$$ -- number of distinct letters in $$$s$$$. Correct me if I'm wrong.
P.P.S In my code I should break the cycle if I find NO, it was my fault :D
Very nice contest! I love super-super ad-hoc problems, they're the most interesting to me. Unfortunately I couldn't quite solve E in time, because I initially misread "at least $$$k$$$" as "exactly $$$k$$$", and then panicked :(
hi everyone, my solution to problem b is different and i think it's better using the concept to sliding window and maps, just wanted to share it:->
include <bits/stdc++.h>
using namespace std;
define int long long
define endl " \n"
signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t; cin>>t; while(t--){ string a; cin>>a; map<char,int> x; for(int i=0;i<a.length();i++){ x[a[i]]++; } int flag=0; int j=0; int i=0; map<char,int> ans; while(j<a.length()){ ans[a[j]]++; if(ans[a[j]]>=2){ if(ans.size()!=x.size()){ flag=1; break; } ans[a[i]]--;
}
SORRY for the mess, this was my first time posting, here is the link to the submission https://codeforces.net/contest/1673/submission/155436027
Problem F was very good. Thank you!
How to solve problem C in space complexity to O(n)?
Please help!
Draw O(n*m) dp table and you will notice a pattern.
181681138
If you need more explanation then, reply to this thread.