Shifts Problem Round G - Kickstart

help
1

Probelm - Kick Start - Google’s Coding Competitions

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 :slight_smile:

1 Like
2

Did you completely the second question(The equation)?
If yes please share your solution, it would be really helpful.

1 Like
3

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?
If full, please share your approach. Would be helpful :slight_smile:

4

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-: qrLBIf - Online Java Compiler & Debugging Tool - Ideone.com

1 Like
5

I hope the link is working.:sweat_smile:

1 Like
6

No, it isnt working. Can you update it.

7

anyways got your account on kickstart. no need

1 Like
8

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
9

Thank you.:grin:

10

Kick Start - Google’s Coding Competitions here i guess u can download all my submissions

2 Likes
11

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

2 Likes
12

I just got partial in 2nd.

1 Like
13 
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();
14

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.

15

Right, even better than my solution.
Thanks.

16

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

1 Like
17

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
18

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 :expressionless:

1 Like
19

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

1 Like
20

some bad luck i would say. xD

1 Like