UNIX> cat input-1.txt 5 1 3 1 2 3 4 5 7 UNIX> ./a.out < input-1.txt 4 0 3 UNIX> |
To explain, spell[0] is 5. When it is combined with potion[0] (which is 1), its product is too small. So it is unsuccessful. However, its product with all of the other potions is greater than 7, so there are 4 successful potions. There are no successful potions with spell[1], and three successful potions with spell[2] (those potions are 3, 4 and 5). Hence the return value of [ 4 0 3 ].
Here is the other Leetcode example, plus two of mine:
UNIX> cat input-2.txt 3 1 2 8 5 8 16 UNIX> ./a.out < input-2.txt 2 0 2 UNIX> cat input-3.txt 4 24 10 19 22 25 14 20 15 7 14 10 6 17 5 13 5 7 27 11 10 13 1 25 16 80 UNIX> ./a.out < input-3.txt 4 19 14 19 19 UNIX> cat input-4.txt 6 24 13 17 7 27 30 29 42 39 27 29 4 9 25 39 6 14 38 47 16 29 21 42 5 48 14 14 35 16 15 15 43 2 10 47 18 17 34 1 1000 UNIX> ./a.out < input-4.txt 0 4 0 0 0 4 6 5 7 7 4 5 0 0 4 7 0 0 7 7 UNIX> |
Now, if you enter a single negative number to the program, it will generate a random, typically large example within the constraints. It runs the method and then prints the last element of rv. For example:
UNIX> echo -1 | ./a.out rv[4163] = 12183 UNIX> echo -2 | ./a.out rv[91243] = 4321 UNIX> |
Your program's output should match answers.txt, and it should run quickly. Let's say under 4 seconds total.
For every spell i,
For every potion j,
Test to see if i*j ≥ success.
Unfortunately, the running time of that is O(n2), where n is the
size of spells and potions (just assume they are roughly the same size).
That means the running time can be roughly 1010, which is way too slow.
So we have to try something else.
Index Value
0 1
1 5
2 5
3 6
4 7
5 7
6 10
7 10
8 11
9 13
10 13
11 14
12 14
13 15
14 16
15 17
16 20
17 25
18 25
19 27
|
To remind you, the spells are
4 24 10 19 22 |
And success is 80. So consider the first spell: 4. By division, we know that successful potions will have values ≥ 20. We can find the value 20 in the sorted array, and see that there are four values ≥ 20. So rv[0] is 4.
Similarly, the second spell is 24. Successful potions will have values ≥ 4. The smallest value ≥ 4 in the sorted array is 5, with an index of 1. Therefore, there are 19 successful potions, and rv[1] is 19.
And so on.
Key Val
1 20
5 19
6 17
7 16
10 14
11 12
13 11
14 9
15 7
16 6
17 5
20 4
25 3
27 1
|
Make sure you see how you can make that from the sorted vector above (you can make it more simply, but it may be easier to see how it is derived from the vector).
Now, when you consider a spell, you calculate the smallest successful potion value, and use the lower bound method of map to find the smallest value in the map greater than or equal to that value. That determination is done in O(log n) time, so you have:
UNIX> time sh tests.sh > /dev/null real 0m3.111s user 0m2.958s sys 0m0.129s UNIX> |
Index Value
0 1
1 5
2 5
3 6
4 7
5 7
6 10
7 10
8 11
9 13
10 13
11 14
12 14
13 15
14 16
15 17
16 20
17 25
18 25
19 27
|
You want to find the smallest potion whose value is ≥ 20. I'm not fond of my binary search, but I never am. I kept track of two values:
b sz middle-element action 0 20 Index 10: 13 Too small, set b to 11 and size to 9. 11 9 Index 15: 17 Too small, set b to 16 and size to 4 16 4 Index 18: 25 >= 0 20, keep b at 16 and set size to 2 16 2 Index 17: 25 >= 0 20, keep b at 16 and set size to 1 16 1 Index 16: 20 >= 0 20, keep b at 16 and we're doneSince there are 4 elements >= potions[16], the answer is 4.
Now, when you're done with your binary search, you need to consider that b may be the smallest index with a value ≥ 20, or the largest index with a value < 20. So you need to do a little work when your binary search is done to make sure you know what b is. This is one reason why I don't like writing binary searches...
Now, let's evaluate the running time:
UNIX> time sh tests.sh > /dev/null real 0m1.085s user 0m0.972s sys 0m0.100s UNIX> |
Spells
Value Original-Index
4 0
10 2
19 3
22 4
24 1
|
Potions:
Index Value
0 1
1 5
2 5
3 6
4 7
5 7
6 10
7 10
8 11
9 13
10 13
11 14
12 14
13 15
14 16
15 17
16 20
17 25
18 25
19 27
|
Now, we run through both vectors at the same time. We'll traverse spells from low to high and potions from high to low. Here's our starting points:
Spells
Value Original-Index
i --> 4 0
10 2
19 3
22 4
24 1
|
Potions:
Index Value
0 1
1 5
2 5
3 6
4 7
5 7
6 10
7 10
8 11
9 13
10 13
11 14
12 14
13 15
14 16
15 17
16 20
17 25
18 25
j --> 19 27
|
Now, we consider the value at index i, which is 4. We calculate that we need potions ≥ 20, so we decrement j until we have a value less than 20 (or we've run out of potions):
Spells
Value Original-Index
i --> 4 0
10 2
19 3
22 4
24 1
|
Potions:
Index Value
0 1
1 5
2 5
3 6
4 7
5 7
6 10
7 10
8 11
9 13
10 13
11 14
12 14
13 15
14 16
j --> 15 17
16 20
17 25
18 25
19 27
|
We know there are 4 values greater than potions[j], and the spell at index i was originally spells[0], so rv[0] = 4.
Now, we increment i:
Spells
Value Original-Index
4 0
i --> 10 2
19 3
22 4
24 1
|
Potions:
Index Value
0 1
1 5
2 5
3 6
4 7
5 7
6 10
7 10
8 11
9 13
10 13
11 14
12 14
13 15
14 16
j --> 15 17
16 20
17 25
18 25
19 27
|
We calculate that we need potions with values ≥ 10, so we decrement j until we get to a potion whose value is less than 10:
Spells
Value Original-Index
4 0
i --> 10 2
19 3
22 4
24 1
|
Potions:
Index Value
0 1
1 5
2 5
3 6
4 7
j --> 5 7
6 10
7 10
8 11
9 13
10 13
11 14
12 14
13 15
14 16
15 17
16 20
17 25
18 25
19 27
|
There are 14 potions with values greater than potions[j], and the original index of spell i is 2, so rv[2] = 14.
We increment i again:
Spells
Value Original-Index
4 0
10 2
i --> 19 3
22 4
24 1
|
Potions:
Index Value
0 1
1 5
2 5
3 6
4 7
j --> 5 7
6 10
7 10
8 11
9 13
10 13
11 14
12 14
13 15
14 16
15 17
16 20
17 25
18 25
19 27
|
We calculate that we need potions with values ≥ 5. So we decrement j until it is pointing to a value < 5:
Spells
Value Original-Index
4 0
10 2
i --> 19 3
22 4
24 1
|
Potions:
Index Value
j --> 0 1
1 5
2 5
3 6
4 7
5 7
6 10
7 10
8 11
9 13
10 13
11 14
12 14
13 15
14 16
15 17
16 20
17 25
18 25
19 27
|
So now we set rv[3] = 19. See how that works? Since we only traverse spells and potions once, we have:
Unfortunately, there is a subtlety here in that we have to sort spells, but we need to keep track of each value's original index. We could us a map for this, but then we're going to be as slow as solution 1, so that won't do. What I did was transform each value in spells to a long long. Call it x:
x = (value << 20) | index; |
When I sort the x's, they'll be in the same order as sorting the spells. However, I can extract the values from each x with (x > > 20), and I can extract the indices with (x & 0xfffff). This is because we know the values and indices are capped at 100,000, which is less than 220. Let me use the spells in input-3.txt as an example:
Value Original-Index x x-in-hex x>>20 x&0xfffff
4 0 4194304 0x400000 4 0
10 2 10485762 0xa00002 10 2
19 3 19922947 0x1300003 19 3
22 4 23068676 0x1600004 22 4
24 1 25165825 0x1800001 24 1
|
As you can see, the values are sorted by the spell value, but I can extract both the spell value and the original index from the x value.
It's not a bad exercise to program this one up -- when I did it, it was the fastest of the three. It was faster than 86% of the leetcoders:
UNIX> time sh tests.sh > /dev/null real 0m1.049s user 0m0.940s sys 0m0.091s UNIX> |