aakarshmadhavan's blog

489C Problem
By aakarshmadhavan, history, 6 years ago, In English

I am following Ahmed Aly's Ladder for Div2C problems and I am ... stuck on the first problem :(

489C

I have made a recursive solution very easily but it has timed out. I am thinking of somehow memoizing my solution but I am not sure how to do it.

I thought of memorizing using accumulated sum, but that gives wrong answers for many cases. I am not sure how to memoize from recursive. Here is my code for lowest number for example:

Map<Integer, String> memo = new HashMap<>();
public String lowest(int sum, String cur){
		if(sum > s || cur.length() > m) return "-1";
		if(sum == s && cur.length() == m) {
			map.put(sum, cur);
			return cur;
		}
		if(map.containsKey(sum)) return map.get(sum);

		for(int i = 0; i < 10; ++i){
			if(cur.isEmpty() && i == 0) continue;
			String next = lowest(sum + i, cur + String.valueOf(i));
			if(!next.equals("-1")){
				map.put(cur, next);
				return next;
			}
		}
		if(!map.containsKey(cur)) map.put(cur, "-1");
		return "-1";
	}

Without memo it works, but with it I am failing. Thanks very much

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I don’t really understand your solution. There’s no need of any memoisation. It’s a very simple greedy question.

I’ll just describe the solution for the maximum case. We want to maximise the prefix. Put as many 9s in the front as possible.

Here is some explanation and some code.

→ Reply