I passed subtask 1 of this problem. However, I get TLEs on the second and third subtask.
My code:
https://www.codechef.com/viewsolution/30615722
Can someone please help me solve this? I’m a beginner.
Zco solutions are not visible as of now. You’ll have to post the code in the forum. To format it, use ```above and below the code.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long int blockCount(vector <long long int> vec)
{
long long int count = 0, traversed = 0;
while (traversed < vec.size())
{
if (vec[traversed] != vec[traversed+1])
{
count++;
}
traversed++;
}
return count;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
long long int t;
cin >> t;
while (t--)
{
long long int n, m, k;
cin >> n >> m >> k;
vector <long long int> A, B, X, C;
A.resize(n);
B.resize(m);
X.resize(0);
C.resize(n + m);
for (long long int i = 0; i < n; ++i)
{
cin >> A[i];
X.push_back(0);
}
for (long long int i = 0; i < m; ++i)
{
cin >> B[i];
X.push_back(1);
}
long long int kcount = 0;
do {
long long int i = 0, j = 0;
while ((i + j) < (n + m))
{
if (X[i + j] == 0)
{
C[i + j] = A[i];
i++;
} else {
C[i + j] = B[j];
j++;
}
}
if (k == blockCount(C))
{
kcount++;
}
} while (next_permutation(X.begin(), X.end()));
cout << (kcount % 100000007) << endl;
}
}
Your code is O((n+m)\binom{n+m}{m}). So it will take 10^63 calculations. 10^9 is would already be pushing the limit.
3 Likes
To solve it correctly, we need to define a dp state. We need to know the amount of numbers we have used from each sequence, The number of blocks we’ve created, and from which sequence we’ve used the last element. This is all the information we need to define a dp state. so
dp[i][j][k][l] means i elements from seq1, j elements from seq2, k blocks created, and ends with the first sequence if l is 0, and ends with second sequence if l is 1.
Now what happens when we add a new element. Let’s say we have used i elements from sequence 1 and j elements from sequence 2, and the last element was from sequence 1.
I’ve written some psudocode to help you understand how it works.
It’s a bit difficult so spend some time seeing how I got them and you’ll surely understand.
Pseudocode
dp[i][j][k][l]=0;
if(last element==sequence 1){
if(jth element of seq2 == i th element of seq1){
dp[i][j][k][l]+=dp[i-1][j][k][sequence 2];
}
else{
dp[i][j][k][l]+=dp[i-1][j][k-1][sequence 2]
, }
if(i-1 the element of seq1==ith element of seq1){
dp[i][j][k][l]+=dp[i-1][j][k][sequence 1];
}
else{
dp[i][j][k][l]+=dp[i-1][j][k-1][sequence 1];
}
}
else{
if(jth element of seq2 == i th element of seq1){
dp[i][j][k][l]+=dp[i][j-1][k][sequence 1];
}
else{
dp[i][j][k][l]+=dp[i][j-1][k-1][sequence 1]
, }
if(j-1 the element of seq2==jth element of seq2){
dp[i][j][k][l]+=dp[i][j-1][k][sequence 2];
}
else{
dp[i][j][k][l]+=dp[i][j-1][k-1][sequence 2];
}
}
full code
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
using namespace std;
long long int ways[103][103][205][2];//
long long int find(int ,int ,int,int);
long long int a[103];
long long int b[103];
long long int n,m,k;
long long int p=100000007;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >>t;
while(t--){
cin>>n>>m>>k;
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<m;i++){
cin>>b[i];
}
for(int i=0;i<103;i++){
for(int j=0;j<103;j++){
for(int k=0;k<203;k++){
ways[i][j][k][0]=-1;
ways[i][j][k][1]=-1;
}
}
}
for(int i=0;i<205;i++){
ways[0][1][i][0]=0;
ways[1][0][i][1]=0;
ways[0][1][i][1]=0;
ways[1][0][i][0]=0;
ways[0][0][i][0]=0;
ways[0][0][i][1]=0;
//ways[1][1][i][1]=0;
//ways[1][1][i][0]=0;
}
if(a[0]==b[0]){
ways[1][1][1][0]=1;
ways[1][1][1][1]=1;
}
else{
ways[1][1][2][0]=1;
ways[1][1][2][1]=1;
}
ways[0][1][1][1]=1;
ways[1][0][1][0]=1;
long long int ans=find(n,m,k,0)+find(n,m,k,1);
// cout<<find(n,m,k,0)<<" "<<find(n,m,k,1)<<" \n";
while(ans<0){
ans+=p;
}
cout<<ans%p<<"\n";
}
}
long long int find(int nused,int mused,int block,int which){
//cout<<nused<<" "<<mused<<" "<<block<<" "<<which<<"\n";
long long int ans=0;
long long int p=100000007;
if(ways[nused][mused][block][which]!=-1){
//cout<<nused<<" "<<mused<<" "<<block<<" "<<which<<"\n";
// cout<<ways[nused][mused][block][which]<<"\n";
return ways[nused][mused][block][which];
}
if(nused==0 && mused>1){
if(which==1){
if(b[mused-1]==b[mused-2]){
ans=find(0,mused-1,block,which);
}
else{
ans=find(0,mused-1,block-1,which);
}
ways[nused][mused][block][which]=ans%p;
ans=ans%p;
return ans;
}
else{
return 0ll;
}
}
if(mused==0 && nused>1){
if(which==0){
if(a[nused-1]==a[nused-2]){
ans=find(nused-1,0,block,which);
}
else{
ans=find(nused-1,0,block-1,which);
}
ways[nused][mused][block][which]=ans%p;
ans=ans%p;
return ans;
}
else{
return 0ll;
}
}
if(which){
if(b[mused-1]==a[nused-1]){
ans+=find(nused,mused-1,block,0);
ans=ans%p;
}
else{
ans+=find(nused,mused-1,block-1,0);
ans=ans%p;
}
if(mused>1){
if(b[mused-1]==b[mused-2]){
ans+=find(nused,mused-1,block,1);
ans=ans%p;
}
else{
ans+=find(nused,mused-1,block-1,1);
ans=ans%p;
}
}
}
else{
if(nused>1){
if(a[nused-1]==a[nused-2]){
ans+=find(nused-1,mused,block,0);
ans=ans%p;
}
else{
ans+=find(nused-1,mused,block-1,0);
ans=ans%p;
}
}
if(a[nused-1]==b[mused-1]){
ans+=find(nused-1,mused,block,1);
ans=ans%p;
}
else{
ans+=find(nused-1,mused,block-1,1);
ans=ans%p;
}
}
ways[nused][mused][block][which]=ans%p;
return ans%p;
}
3 Likes
Thank you so much for spending this much time for my doubt. I really appreciate it 
1 Like
for(int i=0;i<103;i++){
for(int j=0;j<103;j++){
for(int k=0;k<203;k++){
ways[i][j][k][0]=-1;
ways[i][j][k][1]=-1;
}
}
}
Why are you assigning them to -1?
1 Like
Oh that’s because I don’t know the value yet. It’s a well known trick in memoisation. Sometimes, I may recursively call the function with the same parameters. So I store the answer in that. The first thing I do in the find function is check whether I’ve already calculated it yet. If I’ve already calculated it, I just directly return the answer.
2 Likes
Oh I understood. BTW, where can I learn DP from?
Atcoder dp contest. I’ve solved the first 20 or so, So if you have any doubt in the questions, you can ask me. This one was a bit hard, because It has 16 cases to check for. After you get comfortable with the way to derive the relation, it will be simple, just long.
1 Like
Thank you. Can I have your telegram/whatsapp/discord to contact you if I have doubts (if you don’t mind, of course)
Use my codeforces account if you want. It’s “everule”.
1 Like
I sent you a message. Thank you.