ICPC Amritapuri Practice Session #6 [Team Contest] Announcement

Hello CodeDrills,
ICPC Amritapuri Regional will be hosting next team practice round on CodeDrills on Tuesday, 13th April 2021. There will be 5 problems to be solved in 2.5 hours.

Contest Details

Registration

  • You will need to create a team on the contest page in order to participate.
  • Team size can be upto 3.
  • While creating the team, add the registered emails of other users to invite them to join your team. They will get an invite email, ask them to accept.
  • For more details on team registration, refer this guide.

Note : Register your teams & accept invites before the start of the contest. This won’t be allowed after contest starts!

Prizes

  • Cash prizes of INR 35000 for top 15 teams.
  • 1st Place — INR 5000
  • 2nd, 3rd Places — INR 4000 each
  • 4th, 5th, 6th Places — INR 3000 each
  • 7th, 8th, 9th, 10th Places — INR 2000 each
  • 11th, 12th, 13th, 14th, 15th Places — INR 1000 each
  • Only Indian participants are eligible for prizes but everyone can participate.
  • Prize money is per team.

Joining me on the problem setting panel are:

I would like to thank all of them for the round preparation. Along with them I would also like to thank

I hope you will enjoy solving the problems. Any feedback is appreciated after the contest.

Good Luck & Have Fun!
Hope to see you participating!!

2 Likes

Reminder: contest starts soon!

1 Like

Was anyone able to AC the last problem in Java? I have similar solution to the editorial but I kept TLE

import java.io.*;
import java.util.*;

public class Main {
    final int IMAX = Integer.MAX_VALUE, IMIN = Integer.MIN_VALUE;
    final long LMAX = Long.MAX_VALUE, LMIN = Long.MIN_VALUE;

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter w = new PrintWriter(System.out);
        int T = in.ii();

        Main ok = new Main();

        for (int i = 0; i < T; i++)
            ok.solve(in, w);
        w.close();
    }

    static class Node {
        Node n0;
        Node n1;
        int count;

        Node() {
            n0 = null;
            n1 = null;
            count = 0;
        }
    }

    Node root;

    void insert(int val) {
        Node tmp = root;
        for (int i = 31; i >= 0; i--) {
            if ((val & (1 << i)) == 0) { // current bit is 0
                if (tmp.n0 == null)
                    tmp.n0 = new Node();
                tmp = tmp.n0;

            } else {
                if (tmp.n1 == null)
                    tmp.n1 = new Node();
                tmp = tmp.n1;
            }
            tmp.count++;
        }
    }

    long count(Node cur, int i, int val, int high, boolean less) {
        if (cur == null)
            return 0;
        long res = 0;
        if (less)
            return cur.count;
        if (i < 0)
            return res;
        if ((high & (1 << i)) == 0) { // current high bit is 0
            if ((val & (1 << i)) == 0) {// current val bit is 0
                res += count(cur.n0, i - 1, val, high, less);
                if (less)
                    res += count(cur.n1, i - 1, val, high, less);
            } else { // current val bit is 1
                if (less)
                    res += count(cur.n0, i - 1, val, high, less);
                res += count(cur.n1, i - 1, val, high, less);
            }
        } else { // currrent high bit is 1
            if ((val & (1 << i)) == 0) {// current val bit is 0
                res += count(cur.n0, i - 1, val, high, true);
                res += count(cur.n1, i - 1, val, high, less);
            } else {
                res += count(cur.n0, i - 1, val, high, less);
                res += count(cur.n1, i - 1, val, high, true);
            }
        }
        return res;
    }

    public long countPairs(int[] nums, int low, int high) {
        root = new Node();
        long res = 0;
        for (int num : nums) {
            res += count(root, 31, num, high + 1, false);
            insert(num);
        }
        return res;
    }

    public long max_val(int[] nums) {
        long res = 0;
        for (int num : nums) {
            res = (res | num);
        }
        return res;
    }

    public void solve(InputReader in, PrintWriter w) {
        int n = in.ii();
        long k = in.ll();
        int[] nums = in.nextIntArray(n);
        long left = 0;
        long right = max_val(nums);
        long res = right;
        while (left <= right) {
            long m = left + (right - left) / 2;
            long count = countPairs(nums, 0, (int) m);
            if (count >= k) {
                res = Math.min(res, m);
                right = m - 1;
            } else {
                left = m + 1;
            }
        }
        w.println(res);
    }

    public static class InputReader {

        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int snext() {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) {
                curChar = 0;
                try {
                    snumChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int ii() {
            int c = snext();
            while (isSpaceChar(c)) {
                c = snext();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = snext();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long ll() {
            int c = snext();
            while (isSpaceChar(c)) {
                c = snext();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = snext();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public double nextDouble() {
            return Double.parseDouble(readString());
        }

        public int[] nextIntArray(int n) {
            int a[] = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ii();
            }
            return a;
        }

        public long[] nextLongArray(int n) {
            long a[] = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = ll();
            }
            return a;
        }

        public String readString() {
            int c = snext();
            while (isSpaceChar(c)) {
                c = snext();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = snext();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public String nextLine() {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = snext();
            } while (!isEndOfLine(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

    class Pair<S extends Comparable<S>, T extends Comparable<T>> implements Comparable<Pair<S, T>> {
        S first;
        T second;

        Pair(S f, T s) {
            first = f;
            second = s;
        }

        @Override
        public int compareTo(Pair<S, T> o) {
            int t = first.compareTo(o.first);
            if (t == 0)
                return second.compareTo(o.second);
            return t;
        }

        @Override
        public int hashCode() {
            return (31 + first.hashCode()) * 31 + second.hashCode();
        }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Pair))
                return false;
            if (o == this)
                return true;
            Pair p = (Pair) o;
            return first.equals(p.first) && second.equals(p.second);
        }

        @Override
        public String toString() {
            return "Pair{" + first + ", " + second + "}";
        }
    }
}
1 Like

I think Taranpreet got AC. Here is his submission - CodeDrills

1 Like

I am not able to understand why is this code getting runtime error for test case 0 for problem - Sorted XOR Problem
Is there any way to see test cases after the contest is over? At least to see where a code like mine is failing

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define _USE_MATH_DEFINES
#define _MATH_DEFINES_DEFINED
using namespace __gnu_pbds;
using namespace std;
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
    
#define ll long long int
#define pb push_back
#define eb emplace_back
#define rep(i , j , n) for(ll i = j ; i < n ; i++)
#define pre(i , j , n) for(ll i = j ; i >= n ; i--) 
#define all(x) x.begin(), x.end()
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pl;
typedef vector<int>		vi;
typedef vector<ll>		vll;
typedef vector<double>	vd;
typedef vector<bool>	vb;
typedef pair<ll,ll> 	pll;
typedef vector<vector<ll>> vvll;
#define M_PI       3.14159265358979323846
#define br "\n"
#define ff first
#define ss second
#define debug(a...) cout<<#a<<": ";for(auto it:a)cout<<it<<" ";cout<<endl;
#define working cout << "Working till here" << endl;
#define MAXIM 1000101
const ll MAX = 2e5 + 1;
ll mod = 1e9 + 7;

ll n,k;
vll arr;

struct TrieNode{
    TrieNode *child[2];
    ll cnt;
    TrieNode() {
        child[0] = child[1] = NULL;
        cnt = 0;
    }
};

void insert(TrieNode *root, ll N){
    pre(i,31,0){
        bool x = ((N) & (1LL << i));
        if(root->child[x] == nullptr) root->child[x] = new TrieNode();
        root->child[x]->cnt += 1;
        root = root->child[x];
    }
}

ll cnt(TrieNode *root, ll N, ll K){
	ll c = 0;
	pre(i,31,0){
        if(root == nullptr) break;				
		bool x = (N & (1LL << i));
		bool y = (K & (1LL << i));
		if (y) {
			if(root->child[x]) c += root->child[x]->cnt;
		    root = root->child[1 - x];
		}
		else root = root->child[x];
	}
	return c;
}

bool check(ll mid,vll &arr,ll k){
    TrieNode *root = new TrieNode();
    ll ans = 0;
    map<ll,ll> m;
    rep(i,0,n){
        ans += cnt(root,arr[i],mid);
        ans += m[(arr[i]^mid)];
        m[arr[i]]++;
        insert(root, arr[i]);
    }
    return (ans >= k);
}

void solve(){
    arr.clear();
    cin >> n >> k;
    arr.resize(n);
    rep(i,0,n) cin >> arr[i];
    ll lo = 0,hi = (1LL<<31) - 1LL;
    while(lo < hi){
        ll mid = lo + (hi - lo)/2;
        if(check(mid,arr,k)) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << br;

}
 
int main(){ 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
 
    ll t = 1;
    cin >> t;
    rep(i,0,t){
        // cout << "Case #" << i + 1 << ": ";
        solve();
        // test();
    }
}
1 Like

I submitted your code. submission → CodeDrills
Notice that its AC on smaller cases. Test cases 1,2,3 are large cases. Getting RE because you are allocating too much memory. Add a destructor to your trie and try.

1 Like

Actuallty I don’t quite get for what reason is my code getting RE at #0 in problem Sort the array,

Sry but am unable to get the submission link of my code in the submission tab, thus am pasting it here

btw I have tried a lot of diff. values for N, incase someone feels that it’s value is quite low.
I request someone to just point some mistake, in case u have question in logic/code ping me pls

/*
ॐ नमो भगवते वासुदेवाय नमः
*/

// Problem Link:- https://codedrills.io/contests/amrita-icpc-practice-session-6/problems/sort-the-array

#include<bits/stdc++.h>
using namespace std;
#define int long long

bool sqrtt(int x){

    int val = sqrt(x);
    if(val*val == x){
        return true;
    }
    return false;
}

const int N = 300000;
int lp[N+1];

void seive(){
    vector<int> pr;

    for (int i=2; i<=N; ++i) {
        if (lp[i] == 0) {
            lp[i] = i;
            pr.push_back (i);
        }
        for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
            lp[i * pr[j]] = pr[j];
    }
}


int par[N], sz[N];
struct DSU {

  int connected;

  void init(int n) {
    for(int i=0;i<=n;i++){
      par[i]=i;
      sz[i]=1;
    }
    connected=n;
  }

  int getPar(int k){
    while(k!=par[k]){
      par[k]=par[par[k]];
      k=par[k];
    }
    return k;
  }

  int getSize(int k){
    return sz[getPar(k)];
  }

  void unite(int u, int v){
    int par1=getPar(u), par2=getPar(v);
    if(par1==par2)
      return;
    
    connected--;

    if(sz[par1]>sz[par2])
      swap(par1, par2);

    sz[par2]+=sz[par1];
    sz[par1]=0;
    par[par1]=par[par2];
  }
  
};

DSU dsu0;

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie();

    seive();
    int t;cin>>t;
    while(t--){

        int n;cin>>n;
        if(n <= 1){
            cout<<"YES"<<"\n";
            continue;
        }
        int arr[n];
        vector<pair<int,int>> a;
        for(int i=0;i<n;i++){
            cin>>arr[i];
            a.push_back({arr[i],i});
        }
        dsu0.init(n);
        sort(a.begin(),a.end());


        vector<int> repp;
        for(int i=0;i<n;i++){
            
            int val = arr[i];

            int tot = 1;
            int in = 0;
            if(val == 0){
                repp.push_back(0);
                continue;
            }
            while(val > 1){

                int one = lp[val];
                if(one == 1 || one == 0){
                    break;
                }
                int cnt = 0;
                int times = val;
                while(times%one == 0){
                    times /= one; 
                    cnt++;
                    if(times <= 1){
                        break;
                    }
                }
                val = times;
                if(cnt%2 == 0){
                    continue;
                }
                else{
                    tot *= one;
                    in = 1;
                }
            }
            if(in == 0){
                repp.push_back(0);
            }
            else{
                repp.push_back(tot);
            }
        }


        multiset<int> st;
        map<int,int> mp;

        int b[n];
        for(int i=0;i<n;i++){
            b[i] = repp[i];
            // cout<<b[i]<<" ";
        }
        // cout<<"\n";

        map<int,vector<int>> mpr;

        for(int i=0;i<n;i++){

            bool value = sqrtt(b[i]);
            if(value){
                st.insert(i);
            }
            mp[b[i]]++;
        }

        // 1) 4 9 5 5 16 12 27

       
       if(st.size() != 0){
            int onee = *st.begin();
            st.erase(st.equal_range(onee).first);
            for(auto x : st){
                dsu0.unite(onee,x);
            }
       }

        for(int i=0;i<n;i++){

            if(mp[b[i]] > 1){
                mpr[b[i]].push_back(i);
                // cout<<i<<" is inside "<<b[i]<<"\n";
            }
        }

        // cout<<"-----------------"<<"\n";
        int vis[n];
        for(int i=0;i<n;i++){
            vis[i] = 0;
        }
        for(int i=0;i<n;i++){
            if(vis[i]){
                continue;
            }

            if(mpr[b[i]].size() == 0){
                continue;
            }
            int valva = mpr[b[i]][0];
            vis[valva] = 1;
            for(int j=1;j<mpr[b[i]].size();j++){
                vis[mpr[b[i]][j]] = 1;
                dsu0.unite(valva,mpr[b[i]][j]);
            }
        }

        bool ok = 1;
        for(int i=0;i<n;i++){

            int correct = a[i].second;
            // cout<<"corr = "<<correct<<"\n";
            if(i == correct || par[correct] == par[i]){
                ok &= 1;
                // cout<<"parent of "<<i<<" = "<<par[i]<<"\n";
                // cout<<"parent of "<<correct<<" = "<<par[correct]<<"\n";
            }
            else{
                ok &= 0;
            }
            // cout<<"---------------------------"<<"\n";
        }

        if(ok == 1){
            cout<<"YES"<<"\n";
        }
        else{
            cout<<"NO"<<"\n";
        }
    }
}

A small overview of what am trying to do:-

  1. I keep dividing the elements by their smallest prime factors, and store only those primes which have odd power.
  2. Then I try to find the numbers which are actually themselves squares, and merge them together using DSU
  3. Secondly I check if there are any similar valued number in the array
  4. Lastly I just check using DSU are the parents same of the index with which I want to swap…
1 Like

Thanks I will try to submit again after the changes.
Also a suggestion - Is is possible for you guys to make test cases visible like codeforces or atcoder(Atcoder has provided a link for all the test cases).

1 Like

Can someone help me find the issue? I really need help in it

1 Like

It seems you are factorizing the elements of the array. The swap criteria is on the position of the array (i.e. indices) so you should be processing all indices from 1 to n instead of arr[i].

3 Likes

Hey deepa I just can’t thank u much, that was just such a bad mistake from my side, I really spent the entire 2 hrs of the contest on this problem and I would have wasted more of my time if u hadn’t saved me
Thank u again :blush:

3 Likes