Today, I was seeing tourist's submissions. He uses a very cool way to print the variables for the purpose of debugging. The function debug_out lists all variable names, followed by their values. I found it very interesting and convenient.

However, when you would like to print a long list of variables, it might be hard to match variables and their corresponding values. I made a few changes, and I would like to share the code with you. Please note that you need to define XOX (-D XOX should do the job). Therefore, when you are submitting your code, you do not need to remove or comment out lines including debug. Hope you'll find it useful.

#include <bits/stdc++.h>
using namespace std;
vector<string> vec_splitter(string s) {
	s += ',';
	vector<string> res;
	while(!s.empty()) {
		res.push_back(s.substr(0, s.find(',')));
		s = s.substr(s.find(',') + 1);
	}
	return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
	if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
	stringstream ss; ss << H;
	cerr << args[idx] << " = " << ss.str();
	debug_out(args, idx + 1, LINE_NUM, T...);
}
#ifdef XOX
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif
int main() {
	int x = -1, y = 10000;
	double z = 0.2;
	string s = "beginner1010";
	long long b = 1LL << 60;
	
	debug(x, y, z, s, b);
	
	double aux = 1010.0;
	string code = "code";
	
	debug(code + "forces",-aux / 10 * 2.3);
	return 0;
}

Results:

Line(34) x = -1,  y = 10000,  z = 0.2,  s = beginner1010,  b = 1152921504606846976
Line(39) code + "forces" = codeforces, -aux / 10 * 2.3 = -232.3

UPD 1: The code is further improved to handle the case when an operation is applied to variables in debug. The line number is added, and spookywooky's suggestion is applied. Please see the examples. Thank you all for your suggestions.

Today, I tried problem G from Education Round 45. My java implementation (64550159) gets time limit exceeded. It takes at least 4500 ms on test 5 while the same C++ implementation (64545259) on that test case takes only 600 ms.

I tried different things to optimize the Java implementation, but none could help. I believe there is something tricky that I am missing. I appreciate if you let me know which part of my Java implementation affects the overall performance.

BTW, in the C++ implementation, I used an array instead of queue<int>. I found queue so slow which causes time limit exceeded.

Hello,

I tried problem Segment Sum. The DP solution for this problem was pretty straightforward to me. I decided to implement it in Python (You may find the python code below in this post).

I used memorization technique, and the recursive function returns two numbers, i.e. my DP table maintains two values: current summation and number of ways under the mentioned criteria in our current state. After hours of debugging, I couldn't find any problem with my code. I decided to remove if dp[smaller][start][pos][mask][0] != -1: return dp[smaller][start][pos][mask] to see if there is any issue with the DP table. Surprisingly, it output correct results when I removed these two lines. It seems there is something wrong with returning tuples (or array of size 2 here) from a recursive function in Python.

To make sure that the method is correct, I reimplemented it in C++ and it got Accepted, as expected: 60403673. Could you please help me fix the issue in Python?

Python code:

import sys

mod = 998244353
MAX_LENGTH = 20
bound = [0] * MAX_LENGTH

def mul(a, b): return (a * b) % mod
def add(a, b):
    a += b
    if a < 0: a += mod
    if a >= mod: a -= mod
    return a

def digitize(num):
    for i in range(MAX_LENGTH):
        bound[i] = num % 10
        num //= 10

def rec(smaller, start, pos, mask):
    global k
    if bit_count[mask] > k:
        return [0, 0]
    if pos == -1:
        return [0, 1]

    # if the two following lines are removed, the code reutrns correct results
    if dp[smaller][start][pos][mask][0] != -1:  
        return dp[smaller][start][pos][mask]

    res_sum = res_ways = 0
    for digit in range(0, 10):
        if smaller == 0 and digit > bound[pos]:
            continue
        new_smaller = smaller | (digit < bound[pos])
        new_start = start | (digit > 0) | (pos == 0)
        new_mask = (mask | (1 << digit)) if new_start == 1 else 0

        cur_sum, cur_ways = rec(new_smaller, new_start, pos - 1, new_mask)
        res_sum = add(res_sum, add(mul(mul(digit, ten_pow[pos]), cur_ways), cur_sum))
        res_ways = add(res_ways, cur_ways)

    dp[smaller][start][pos][mask][0], dp[smaller][start][pos][mask][1] = res_sum, res_ways
    return dp[smaller][start][pos][mask]

def solve(upper_bound):
    global dp
    dp = 2 * [2 * [MAX_LENGTH * [(1 << 10) * [[-1, -1]]]]]
    digitize(upper_bound)
    ans = rec(0, 0, MAX_LENGTH - 1, 0)
    print(ans)
    return ans[0]

inp = [int(x) for x in sys.stdin.read().split()]
l, r, k = inp[0], inp[1], inp[2]

bit_count = [0] * (1 << 10)
for i in range(1, 1 << 10): bit_count[i] = bit_count[i & (i - 1)] + 1
ten_pow = [(10 ** i) % mod for i in range(0, MAX_LENGTH)]

print(add(solve(r), -solve(l - 1)))

I am trying to solve Morse Code. I failed to understand the solution after spending two hours reading others' codes. Despite an editorial, unfortunately, I cannot understand even a single word of it. With all due respect, I believe the editorial is not written well.

I appreciate if you explain the solution and let me know what exactly $$$f(l, r)$$$ and $$$g(l, r)$$$ are, and why we need them. That would be great if you can explain me why we need LCP, too.

Hello,

I have recently started learning Python. I tried F. Vus the Cossack and a Graph from Codeforces Round #571 (Div. 2). To solve this problem, first I wrote a recursive function to find an Euler circuit, and I got MLE (Memory Limit Exceeded). Using an iterative method (with stack) did not help me either.

You may find the Python implementation here in 59832390

I would appreciate if you give me some hints to make the implementation more efficient in terms of memory. Of course, any hint to make it faster is welcomed.

Today, I tried F2. Same Sum Blocks (Hard) from Codeforces Round #547 (Div. 3). Since $$$n$$$ can be as large as $$$1500$$$, I was struggling to come up with an $$$O(n^2)$$$ but I failed.

When I read the editorial, surprisingly, I found out that the writer's solution is $$$O(n^3)$$$. They used a Hashmap to speedup the whole process, and it seems that the number of different summation values of consecutive elements will be less than $$$n^2$$$. Though I cannot find any counterexample such that different sub-array sums can be as large as $$$n^2$$$ (or at least as large as $$$\frac{n \times (n - 1)}{2}$$$), I cannot convince myself an $$$O(n^3)$$$ approach can pass the system test.

I was wondering if you have any analysis to demonstrate that the optimization (using Hashmap) is sufficient, or if you know any bound on the number of different summation of consecutive elements in an arbitrary array.

Hello,

I tried to solve an interesting div1 500 problem from SRM 352 (of TopCoder). Here is the link of problem: https://community.topcoder.com/stat?c=problem_statement&pm=7481&rd=10709&rm=264976&cr=264869

After reading the solutions, I decided to re-implement an easy, yet clever solution by bmerry. The solution is written in C++. It is fast and can pass the system tests by taking at most 0.5 milliseconds. I wrote a very similar solution in Java:

public class FibonacciKnapsack {
	Long[][] items;
	long[] weightSum;
	long[] priceSum;
	long bruteforce(int idx, long C, int usedLast) {
		if(idx == items.length)
			return 0;
		if(weightSum[idx] <= C)
			return priceSum[idx];
		else if(items[idx][0] <= C && (usedLast == 1 || items[idx][0] != items[idx - 1][0])) {
			long a = bruteforce(idx + 1, C - items[idx][0], 1) + items[idx][1];
			long b = bruteforce(idx + 1, C, 0);
			return Math.max(a, b);
		} else {
			long a = bruteforce(idx + 1, C, 0);
			return a;
		}
	}
	public long maximalCost(String[] itemsString, String _C) {
		long C = Long.parseLong(_C);
		int n = itemsString.length;
		items = new Long[n][2];
		for(int i = 0; i < n; i ++) {
			StringTokenizer st = new StringTokenizer(itemsString[i]);
			items[i][0] = Long.parseLong(st.nextToken());
			items[i][1] = Long.parseLong(st.nextToken());
		}
		Arrays.sort(items, new Comparator<Long[]>() {
			@Override
			public int compare(Long[] o1, Long[] o2) {
				if(o1[0] != o2[0]) return o1[0] > o2[0]? -1: 1;
				return o1[1] > o2[1]? -1: 1;
			}
		});
		weightSum = new long[n];
		priceSum = new long[n];
		for(int i = 0; i < n; i ++) {
			for(int j = i; j < n; j ++) {
				weightSum[i] += items[j][0];
				priceSum[i] += items[j][1];
			}
		}
		long ans = bruteforce(0, C, 1);
		return ans;
	}
}

I expected to get a similar performance. However, it turns out to be so slow on the following test case (taking more than 5 seconds on my machine):

String[] items = {"196418 196418", "196418 196419", "317811 317811", "317811 317812", "514229 514229", "514229 514230", "832040 832040", "832040 832041", "1346269 1346269", "1346269 1346270", "2178309 2178309", "2178309 2178310", "3524578 3524578", "3524578 3524579", "5702887 5702887", "5702887 5702888", "9227465 9227465", "9227465 9227466", "14930352 14930352", "14930352 14930353", "24157817 24157817", "24157817 24157818", "39088169 39088169", "39088169 39088170", "63245986 63245986", "63245986 63245987", "102334155 102334155", "102334155 102334156", "165580141 165580141", "165580141 165580142", "267914296 267914296", "267914296 267914297", "433494437 433494437", "433494437 433494438", "701408733 701408733", "701408733 701408734", "1134903170 1134903170", "1134903170 1134903171", "1836311903 1836311903", "1836311903 1836311904", "2971215073 2971215073", "2971215073 2971215074", "4807526976 4807526976", "4807526976 4807526977", "7778742049 7778742049", "7778742049 7778742050", "12586269025 12586269025", "12586269025 12586269026", "20365011074 20365011074", "20365011074 20365011075"};
String C = "65902560198";
expected_answer = 65902560223L;

I am wondering what makes the Java code so slow. Also, it would be good to know if there is any way/trick to make it as fast as the C++ implementation.