Code Wars 2.0 Unofficial Editorials(Basic Ideas)

1

  1. Very simple. The answer is \lfloor{\frac{mn}{2}}\rfloor for all cases. If mn is even then you can get \frac{mn}{2} as the entire box can be filled with the sweets in this case. When mn is odd, you can tile the entire board except one square.This gives \frac{mn-1}{2} sweets. In either case the answer is \lfloor{\frac{mn}{2}}\rfloor.
    Complexity per test case O(1).
    Code is here.

  2. Nice DP. Truth be told Idk how my solution passed. The constraints were 10^7 and my sol was n^2!
    The idea is to make a dp array where dp[i] stores the least number of hops required to reach the i th position. Note that we can jump from a certain index j to another larger index i if and only if j + a[j] \ge i. and this takes 1 + dp[j] hops. So we can initially set a[i] = INF and then iterate through the array looking for indexes that satisfy j + a[j] \ge i and try to minimize dp[i]. Then our final answer is dp[i] if it is less than INF and -1 otherwise.
    Complexity per test case O(n^2)
    In the implementation INF = 1e9.
    Code is here
    Wrong implementations are here and here.Idk why you would want to view them but there they are.

  3. This one was a implementation problem. The idea is to precompute an array a[i] that stores the number of digits 7 in the range [0, i]. We can compute this by defining a function count7(n) that stores the number of 7 s in the base 10 representation of n. This function can be implemented to work in O(\log n) time. Now we can find a[i] by using a[i]= a[i-1] + count7(i). and a[0]=0.
    After computing this we can compute the answer of each pair (x, y) as follows. Our answer is just a[y] - a[x-1]. Convinced? You shouldn’t be! What happens if x = 0? To fix this we can just replace x with 1 and it will still be fine.(because 0 has no 7 's) Look into the code for more info on this.
    Complexity is O(1) per test case after the precomputation which is n\log n
    Code is here

Hope this helps…:slight_smile: :grinning: :smile: :grin:

2

I did the 3rd one with pre-computation as well. I dont have an idea how to solve it if n would have been >10^8 because we cant make an array of such size.
@moitbytes_1
if u have a better method do post the editorial

3

Another idea for the 2nd one. I haven’t implemented this approach so that is left as an exercise to the reader.

The idea is to make a directed edge between two nodes i,j if it is possible to reach j from i.Now we just have to find the minimum length between 1 and n.

@longtimenoshe2 did you solve the 2nd one in linear time? Or was ur complexity O(n^2) as well?

4

I had a O(n) solution for the 2nd one. I did not even bother trying O(N^2).

Let us define the reach of an element as the maximum index that can be reached from that element

We start from the 1st element, right now no hops are done.
In each iteration, we look at 2 things:

  1. is the reach of element greater than or equal to last element? If yes, then we have our answer by doing 1 hop.
  2. Otherwise, among all elements that can be reached from the current element, we see which one has the maximum reach. We hop to that element and repeat the iteration, until we reach the end

Why does it work?
At every kth step, our solution is going to give us the step that gives us the maximum possible reach in k+1 steps. Therefore, if there exists a solution of M steps, then our solution will give us the maximum possible index that can be reached in M steps as well.

Let our solution be to hop to i_{1},i_{2}....i_M

Base case:
reach(i_1) is the maximum index reachable in 2 steps by construction

Step Case:
Assume reach(i_{k-1}) is the maximum index reachable in k steps.
Let j be the maximum index reachable in k+1 steps. We will prove by contradiction so assume j>reach(i_k).
Then there must exist a jump from some index j1 to j such that j1 is reachable in k steps. Also j1<=reach(i_{k-1})
If the equality holds j1=reach(i_{k-1}), then the proof follows by construction itself.
If j1<reach(i_{k-1}) strictly, 2 cases arise:

  1. j1>=i_{k-1}. In this case j1 is reachable from i_{k-1}, so reach of j1 can not be more than reach(i_k) due to construction.
  2. j1<i_{k-1}. This means that there is some element before i_{k-1} with a reach more than reach(i_k). Let s be the largest index such that i_s<=j1<i_{s+1} where s is less than k-1. But i_{s+1} has more reach than j1. That concludes the proof.

P.S: I hope there will be a more simpler formal proof, and would welcome that

5

i was trying to solve in linear time got WA and then i didn’t upsolved it actually i started doing this contest around 20 mins before the contest ended :slight_smile: