Newton challenge August 2020 4th Problem

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;
	if (s.length()==0) {
		return 0;
    ll count=0;
    for (int i=0;i<s.length();i++){
    for (int i=0;i<26;i++){
        int l=arr[i].size();
        if (l>1){
            for (int j=1;j<l;j++){
    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;
	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))
    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))
    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 :sweat_smile:

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
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??