Shifts Problem Round G - Kickstart

help
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
21

yaa natural me thought of only natural numbers :sweat_smile:

22

Short summary:

  1. Use sieve logic. easy
  2. Greedy
  3. SOSDP
3 Likes
23

I memoized my recursive solution for Shifts problem using map of pairs but it gave memory limit exceeded for hidden case . Any reason for that ?

24

Number of distinct states would be 3^n(~3e9 for n = 20)

25

For the third one, I used Meet in the Middle!

26

I thought k = 1 to 100 in the first try got WA then k = 0 to 100 got WA then i thought why and who told me to put max k = 100 then i got it that k can be max 130 for the first subtask and then i tried k = 1 to k = 130 and got 1st test Accepted. Didn’t tried the bigger test case.

1 Like
27

Can someone please explain the concept behind problem Equation from Kickstart round G, I am really trying hard but I can’t even understand the editorial…
Thanks.

28

In shifts question my O(3^n) solution passes both test cases(Visible + Hidden). Here is my solution. I think there test cases are very weak for this question.

29

I also want to know the approach of the second ques the equation. I have a hard time decoding the editorial as well. Help is really appreciated.