How to solve 4th problem of Newton challenge.
The problem is this :-
Saloni has two sets A and B, both of having N distinct elements. Sets A and B have exactly N - K same elements (K <= N). Therefore, exactly K elements differ in sets A and B. Now you insert both the sets into two lists C and D. Now Saloni loves the scenario when C[i] != D[i] for any value of i from 1 to N. You are allowed to permute both the arrays C and D. Find the number of ways in which Saloni loves the permutation of the two arrays modulo 1e9 + 7. (The total number of ways to permute both arrays = N! * N! )
input :
q (no. of queries)
n and k
constraints :
1 <= q <= 1e5
1 <= n <= 1e4
0 <= k <= n
1 Like
i think a dp having the recurrence f(i+1,k+1)=(i+1-n0)*f(i,k)+(n0)*f(i,k+1) should be fine
i+1->index till which processing has been done
k->number of elements which differ n0=number of same different elements left
can you share a link so that i can try my code?
@codeguptaji Can you tell what is the problem with my code of Q3? It didn’t passed test case 1 and 2
#include <bits/stdc++.h>
using namespace std;
# define all(v) (v).begin(),(v).end()
# define pi pair<int,int>
# define ll long long
#define MOD 1000000007
int main(){
std::ios_base :: sync_with_stdio ( false );
std::cin . tie ( 0 ); std::cout . tie ( 0 );
string s;
cin>>s;
if (s.length()==0) {
cout<<"0"<<endl;
return 0;
}
vector<int>arr[26];
ll count=0;
for (int i=0;i<s.length();i++){
arr[s[i]-'a'].push_back(i);
}
for (int i=0;i<26;i++){
int l=arr[i].size();
if (l>1){
for (int j=1;j<l;j++){
count+=(j*(l-j)*(abs(arr[i][j]-arr[i][j-1])));
}
}
}
cout<<count<<endl;
return 0;
}
What is the problem in my code of Solution 2?
I saw other solutions they have calculated X but we know that beforehand. Didn’t we?
#include <bits/stdc++.h> // header file includes every Standard library
using namespace std;
int main() {
int n;
float k;
cin>>n>>k;
float x=0;
while ((n&1)==0) {/*cout<<(n&1)<<endl'*/n/=2;x+=1;}
if (k<=x) cout<<"0"<<endl;
else cout<<ceil((k-x)/4.0)<<endl;
return 0;
}
I also got wrong ans with this
while (!(n & 1))
{
cnt++;
n /= 2LL;
}
int need = k - cnt;
int ans = (ceil)(need / 4.0);
cout << ans << endl;
but AC with this
int cnt = 0;
while (!(n & 1LL))
{
cnt++;
n /= 2LL;
}
int need = k - cnt;
int val = 4;
int ans = (ceil)(need / (ld)(val));
cout << ans << endl;
I am not sure but i think dividing it by 4 might give some error when values are very big
so i first stored it in a long double and then did the same thing, and it worked 
1 Like
Might be 4.0 is not enough. @yatin_yk08 Thanks for the help!!
Also, can you help with it
1 Like
My approach was also similar to yours. But i’m unable to get this part of yours
count+=(j*(l-j)*(abs(arr[i][j]-arr[i][j-1])));
what i did was that i stored the answer for the next position of
my current character and my contribution of the current position could be calculated
with the help of the next character’s contribution
nex-> contribution of the next character
dif -> distance between cur and next position(i.e i+1)
so all the characters after my next character were at some distance from current position their contribution for current position now becomes
cur = dif*(no of characters after the next characters) +nex
add dif to cur as distance between cur and next position has not been taken yet.
and total contribution of the current character becomes = cur + dif.
string s;
cin >> s;
vii v[26];
int len = s.length();
fo(i, 0, len - 1) v[s[i] - 'a'].pb(i);
int ans = 0, sz;
int nex, id, cur, dif;
fo(i, 0, 25)
{
sz = v[i].size();
if (sz == 1) continue;
nex = 0;
rfo(j, sz - 2, 0)
{
id = (sz - 1) - (j + 1);
dif = v[i][j + 1] - v[i][j];
cur = dif + nex + dif * id;
ans += cur;
nex = cur;
}
}
cout << ans << endl;
1 Like
@yatin_yk08 My approach was to first store all the indexes that were friends in a vector for that character say arr[0]->‘a’ its vector contains all indexes in increasing order where ‘a’ occurred in string .
Then for all indexes given : a, b, c, d, e(size=5): we can calculate the total |i-j| contributions as:
for a-b length will be counted (index_of_b=1)*(size-index_of_b=5-1=4) Similarly length b-c will be counted (2)*(5-2) times ,length c-d will be counted (3)*(5-3), length d-e will be counted (4)*(5-4) times. So I added all of them and computed the result.
Is my approach wrong somewhere??