Hey!

Consider the following solutions for the CSES problem Coin Combination I (Time Limit is 1s):

#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1000000007;
 
int dp[1000001];
vector<int> v;
 
int main() {
        cin.tie(0)->sync_with_stdio(0);

	int n, x; cin >> n >> x; v.resize(n);
	for (auto &x : v) { cin >> x; }
	dp[0] = 1; for (int i = 1; i <= x; i++)
		for (int j = 0; j < n; j++) if (v[j] <= i)
			dp[i] = (dp[i] + dp[i - v[j]]) % mod;
 
	cout << dp[x] << '\n';
}

#include <bits/stdc++.h>
using namespace std;
int mod = 1000000007;
 
int dp[1000001];
vector<int> v;
 
int main() {
        cin.tie(0)->sync_with_stdio(0);

	int n, x; cin >> n >> x; v.resize(n);
	for (auto &x : v) { cin >> x; }
	dp[0] = 1; for (int i = 1; i <= x; i++)
		for (int j = 0; j < n; j++) if (v[j] <= i)
			dp[i] = (dp[i] + dp[i - v[j]]) % mod;
 
	cout << dp[x] << '\n';
}

Note that using const or constexpr in the first solution is the same since we are initializing a global variable with a prvalue literal.

The first solution passes with Runtime ~0.58s in the worst test case, whereas the second solution gives a TLE outcome.

It seems that reading from compile time constants may be twice as fast as reading from arbitrary variables. Is there a particular reason for this?

EDIT: Big thanks to AkibAzmain and MattTheNub, I got the following answers:

• Compile time constants are inlined by the compiler which saves multiple machine register reading operations.
• When $$$mod$$$ is constant the modulo operator uses a technique called Barret Reduction to speed up computations.

Hello,

I have the following graph problem: Given is a Complete Bipartite Graph $$$G = (L, R)$$$ where $$$|L| = N \leq 100$$$ and $$$|R| = M \leq 10$$$ and an $$$N \times M$$$ array $$$C$$$ where the cost of the edge from the $$$l$$$th node of $$$L$$$ to the $$$r$$$th node of $$$R$$$ is given by $$$C[l][r] \leq 10^5$$$. I need to select a subset $$$S \subseteq E(G)$$$ of the edges such that:

• Every node $$$u \in L$$$ appears in exactly one edge of $$$S$$$
• Every node $$$v \in R$$$ appears in an odd number of edges of $$$S$$$

The cost of the selected set $$$S$$$ is defined as the sum of costs of individual edges of $$$S$$$. I have to find the set $$$S$$$ with the minimum cost.

I tried to reason about the optimal odd assignment being a small $$$(-1/0/1)$$$-deviation of the optimal assignment where nodes of $$$R$$$ can appear any number of times but I figured out this is not true.

One other approach I tried is to find an initial one to one matching $$$L'$$$ between $$$R$$$ and $$$L$$$ and then consider remaining nodes of $$$L$$$ as pairs and perform Min Cost Flow on the Tripartite Graph $$$G' = (L - L', M, R)$$$ where $$$M$$$ has a node for every pair of nodes in $$$L - L'$$$. But I couldn't prove that this will yield an optimal assignment for the original problem.

I think we should use the fact that $$$M$$$ is very small, that the bipartite graph is complete (anything can go to anything), and maybe that costs aren't arbitrarily large. Any help would be highly appreciated.

Thank you!

EDIT: Figured it out, turns out it was just Bitmask DP.

Hello,

I was wondering if there's any trick that allows us to iterate over the boundary of an $$$N \times M$$$ grid using a single loop instead of 4 or 2.

To iterate over the whole grid for example we can iterate from 0 to $$$NM$$$ and have $$$i = x / M$$$ and $$$j = x \% M$$$.

So is there any smart thing like this to do for the boundary only (i.e pairs $$$(i, j)$$$ such that either $$$i = 0$$$ or $$$i = N - 1$$$ or $$$j = 0$$$ or $$$j = M - 1$$$)

Thanks for future help!

EDIT: Problem Solved!

if (!inside(x + dx[d], y + dy[d])) {
    d++;
}

x += dx[d];
y += dy[d];

for(int x = 0; x < n * m; x++) {
    int i = x / m, j = x % m;
    cout << i << ' ' << j << '\n';
    x += (m - 2) * (m != 1 && i != 0 && i != n - 1 && j == 0);
}

Hello everyone,

I've been working on implementing some data structure, and the following question crossed my mind:

In terms of performance, is it better to use STL functions in my class or write them from scratch? For example, if I have a vector and I need to find it's prefix sum, do I write a typical for-loop or use the partial_sum function is the "numeric" library. (This is not my only problem but just an example to explain my question)

In terms of readability I have no doubts that STL is more convenient, but I'm not sure about performance.

Any help would be appreciated. Thank you :)

Hello everyone,

I've noticed in the last contest (Codeforces Round 632 (Div. 2)) many people including me had this issue in 1333D - Challenges in school №41 where our verdicts changed from TLE to AC by just changing every "endl" to '\n'.

TLE Submission: 75902058

AC Submission: 75903554

I knew before that "endl" does some flushing business and this usually takes (Maybe I'm wrong) time but I knew also that the following lines disable this thing: (Maybe I'm also wrong)

ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);

But I still got an issue using "endl" so can someone explain if possible how does endl work exactly and what do the lines above change about using cin/cout/endl?

Thank you!

Hello everyone,

Consider the following problem: given a tree of N node (N <= 10^5), find the size of all subtrees of the tree, assuming the root of the tree is at node 0(or 1).

This problem is fairly easy using recursive DFS traversal of the tree, but as every recursive approach we might get a stack overflow exception if we run it on a list of 10^5 nodes for example.

So my question is: Is it possible to compute these values iteratively (ie. using iterative DFS or possibly BFS or some other approach) instead of recursively?