# Shifts Problem Round G - Kickstart

My solution -

Using recurssive brute force of time complexity 3^n.
I got 1st Test case to pass, but i don’t think it will pass the hidden one.
How did you optimize the solution or how did you solved it?

Thank you

1 Like

Did you completely the second question(The equation)?

1 Like

No, i was constantly getting wrong answer on that.
So i skipped it.
Anyone else has done 2nd , plz share your approach.

Have you solved 1st one partial or full?

Ya I solved the 1st question fully.

Basically for all i for 1 to N calculate the total number of factors, that would simply be n divided by i.(store these values in an array)
Now for all the torn pages, compute the factors of the page number in O(sqrt(N)).
Decrement 1 from that index which is a factor of the torn page number.

Solution-: https://ideone.com/qrLBIf

1 Like

I hope the link is working.

1 Like

No, it isnt working. Can you update it.

anyways got your account on kickstart. no need

1 Like

Sorry but now I have not enough time to explain the approach.
I hope the code is clear enough.
Otherwise, I will go back here later.

``````public static long solve(int from, int n, long m, long[] cnt) {
if(m < 0)
return -1;
if(from == -1)
return 0;
long done = 0;
for(int e = from; e >= 0; e --) {
long kk = solve(e - 1, n, m - ((1L << e) * (n - cnt[e]) + done), cnt);
if(kk == -1) {
done += (1L << e) * cnt[e];
continue;
}
return (1L << e) | kk;
}
return done <= m ? 0 : -1;
}

public static void main(String[] args) throws IOException {
final int MAXE = 50;
int t = in.nextInt();
for(int tc = 1; tc <= t; tc ++) {
int n = in.nextInt();
long m = in.nextLong();
long[] a = in.nextLongArray(n);
long[] cnt = new long[MAXE + 1];
for(int e = MAXE; e >= 0; e --)
for(long ai : a)
if((ai & (1L << e)) != 0)
cnt[e] ++;
out.write("Case #" + tc + ": " + solve(MAXE, n, m, cnt) + "\n");
}
out.flush();
}``````
1 Like

Thank you.

2 Likes

You can also obtain O(NlogN) instead of O(N^1.5) by using the approach used for the Sieve of Eratosthenes

2 Likes

I just got partial in 2nd.

1 Like
``````int t = in.nextInt();
for(int tc = 1; tc <= t; tc ++) {
int n = in.nextInt();
int m = in.nextInt();
int q = in.nextInt();
int[] p = in.nextIntArray(m);
int[] r = in.nextIntArray(q);
boolean[] notOk = new boolean[n + 1];
for(int pi : p)
notOk[pi] = true;
long[] sum = new long[n + 1];
for(int ri : r)
sum[ri] ++;
long ans = 0;
for(int i = 1; i <= n; i ++) {
if(sum[i] == 0)
continue;
long cnt = n / i;
for(int j = i; j <= n; j += i)
if(notOk[j])
cnt --;
ans += sum[i] * cnt;
}
out.write("Case #" + tc + ": " + ans + "\n");
}
out.flush();``````

For partial, i looped k from 1 to 1000, but it was giving wrong answer. Why?
Also for 1st testcase constraints were smaller.
0 ≤ M ≤ 100.
0 ≤ Ai ≤ 100, for all i.
So i thought, it would work, but it didn’t.

Right, even better than my solution.
Thanks.

My solution worked for partial.
I looped k from 1000 to 0:stuck_out_tongue_winking_eye:

1 Like

I looped from 100000 to 1. Here’s my code snippet. It gave me partial

``````for(i=100000;i>-1;i--){
x=0;
for(j=0;j<n;j++){
x+=(a[j]^i);
}
if(x<=m){
k=i;	break;
}
}
cout<<k<<endl;``````
1 Like

I looped from
k=1 to k=1000(inclusive)
and just now i submitted using
k=0 to 1000 (inclusive) and it got acceted .
Lol

1 Like

Just programming things, , but k=0 was also possible

1 Like

some bad luck i would say. xD

1 Like