nik09877's blog

By nik09877, history, 4 years ago, In English

Came In the Recent Leetcode Contest,Don't know where my code went wrong Link To The Problem ~~~~~ You are given two integer arrays nums1 and nums2 of length n.

The XOR sum of the two integer arrays is (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n — 1] XOR nums2[n — 1]) (0-indexed).

For example, the XOR sum of [1,2,3] and [3,2,1] is equal to (1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4. Rearrange the elements of nums2 such that the resulting XOR sum is minimized.

Return the XOR sum after the rearrangement. ~~~~~

Constraints:

n == nums1.length
n == nums2.length
1 <= n <= 14
0 <= nums1[i], nums2[i] <= 10^7
int dp[21][(1 << 21)];
class Solution
{
public:
    int solve(int i, int mask, int &n, vector<int> &a, vector<int> &b)
    {
        if (i == n)
            return 0;

        if (dp[i][mask] != -1)
            return dp[i][mask];

        int answer = INT_MAX;
        for (int j = 0; j < n; j++)
        {
            if (mask & (1 << j))
                answer = min(answer, a[i] ^ b[j] + solve(i + 1, (mask ^ (1 << j)), n, a, b));
        }

        return dp[i][mask] = answer;
    }
    int minimumXORSum(vector<int> &a, vector<int> &b)
    {
        memset(dp, -1, sizeof dp);
        int n = a.size();
        return solve(0, (1 << n) - 1, n, a, b);
    }
};

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

By nik09877, history, 4 years ago, In English

Getting WA on test case 4 . The link to the question https://mirror.codeforces.com/edu/course/2/lesson/6/3/practice/contest/285083/problem/B Can anyone help? what am i doing wrong?

#include <bits/stdc++.h>
#include <stdio.h>
#define repll(i, a, n) for (lli i = a; i <= n; i++)
#define lli long long int
#define ii int, int
#define pii pair<int, int>
#define pll pair<long, long>
#define plli pair<long long int, long long int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vlli vector<long long int>
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0)
using namespace std;
const int mod = 1000000007;

lli n, k, l, r, mid, ans(-1);
vlli a;

lli segments(lli target)
{
    lli cnt(0), sum(0);
    repll(i, 0, n - 1)
    {
        if (a[i] > target)
            return k + 1;
        sum += a[i];
        if (sum > target)
        {
            cnt++;
            sum = a[i];
        }
    }
    cnt++;
    return cnt;
}
void solve()
{
    cin >> n >> k;
    a.resize(n);
    
    repll(i, 0, n - 1) cin >> a[i], r += a[i];
    
    l = 0, r += 10000;
   
    while (l <= r)
    {
        mid = (l + r) / 2;
        lli seg = segments(mid);
        if (seg == k)
        {
            ans = mid;
            r = mid - 1;
        }
        else if (seg > k)
        {
            l = mid + 1;
        }
        else
            r = mid - 1;
    }
    
    cout << ans << endl;
    return;
}
int32_t main()
{
    fastio;
    int t = 1;
    while (t--)
    {
        solve();
    }
}

Full text and comments »

  • Vote: I like it
  • -3
  • Vote: I do not like it