Output-only tasks have become quite popular in the OI scene, although less so than interactive tasks. Sometimes, a good score on such tasks is crucial in determining which medal you get (take IOI 2017 Nowruz, for example). How does one prepare to face such tasks? Is it recommended to learn evolutionary algorithms, ML, etc? I found it very difficult to find nice, clean implementations of them that can be modified to suit each problem.

You are given two arrays of integers a, b both with length n <= 10^5. For each 0 <= x <= n print the sum of a[i]*b[x-i] for all 0 <= i <= x.

It's obvious this can be done in quadratic time, but can we do any better?

Given a set of n integers S, with no elements divisible by n. Prove that there exists a subset of S that has a sum divisible by n. In this case, n should be > 1.

I'm pretty trash at mathematical proofs. Can someone help me out?

Picking the base and mod for string hashing is very important in decreasing the probability of hash collisions. How much are the guidelines affected by the problem itself? So far, I've read that the base should be larger than the alphabet, and the mod should be really large (but not overflow). But is there anything else?

Problem Statement: There exists a single player game called "Pair of Fours". In this game, there are four types of cards, labeled 'U', 'B', 'O' and 'N'. There are N cards in total, and initially they are arranged so that no adjacent cards are of the same type. The game goes as follows:

1. The player chooses a card and removes it. This means the cards on the left and the right are now adjacent.
2. While the (now adjacent) left and right cards are of the same type, remove both cards and add one to the score.
3. If there are no cards left, the game ends. Otherwise, go back to step one.

Sample case:

13
N U B O B U O N B O N U O

I came up with an O(n^3) DP solution, but since n <= 1000, it definitely gets TLE verdict:

dp[i][j] = max(dp[i][k]+dp[k+1][j], dp[i+1][j-1]+(a[i] == a[j]))

Is there a way to optimize this, or is DP not the correct train of thought?

Problem Statement: Click

It definitely requires convex hull optimization, but I'm not sure how to merge the sets properly. I've thought about the usual "merge the small subtree to the large subtree" trick, but it doesn't seem to work. Is there anything I'm missing? And also, which variant of the convex hull optimization should I use? Does it require the fully dynamic variant?

Hi. I'm currently trying to solve this problem, and since I can't solve it, I looked at the editorial.

It said: Let V be the largest coin value, and call this type of coin silver and all other coins brass. It is not difficult to prove that for any change amount of at least V^2, it is possible to use at least one silver coin (hint: consider the partial sums modulo V), and hence that in making change of at least 2V^2 there can be at least V silver coins. Now if Farmer John pays at least 2V^2, and hence pays with V coins, then a similar argument shows that some set of them adds up to a multiple of V and at most V^2, which can be cancelled out with the silver coins in the change. So the change amount can never exceed 2V^2.

What does this mean? And how do we prove this?

I've searched and searched for a proper place to submit COCI problems and there just aren't any that are constantly updated and contain the entire archive. The best I've found for now is DMOJ, but it's still not updated to a satisfactory level. Is there any online judge I might have missed? Is there a group on CF that contains the problems? And can the admins add the problems to Gym?

So, just a few hours ago, we finished a contest on a Thai site, namely Codecube. The round consisted of 6 problems to solve in 3 hours. I was feeling confident at first ACing two problems in 15 minutes. Then came the third problem, which was a typical two pointers + data structures. I was almost certain I could solve the problem, and started to code the solution. Many minutes passed by, and I finally got the solution. I submitted it, and got a WA slapped on my face. So, I simply moved on to the fourth problem and ACed it, because finding bugs is time consuming. I later returned to the third problem, and tried finding the bug for almost an hour with no luck, only to find out that the only line I messed up on was: freopen("data.txt", "r", stdin);, which I forgot to uncomment. I later submitted after the contest and got AC just with that line commented out. Absolutely disappointing.

As many of us know, the freopen command is used to redirect stdio to file IO. This is particularly useful when testing your program on a local machine because you can avoid copying and pasting the test data every time you want to debug. However, one of the problems I have experienced when using it is I forget to uncomment it out when submitting. This is a huge problem, especially on CF where many points are deducted for resubmission. I don't know if it's bad luck, but this has happened to me several times already. For anyone who is experiencing the same problem, I think the solution here is simply to write comments to remind yourself. Has this ever happened to any of you guys? Or is it just me being awfully stupid?

Extremely large tests are very hard to debug, because we are not able to understand the input anymore. The only choice that is left is to go back and look at the code, to potentially find any flaws. I find it quite hard to do this, as sometimes it is very hard to find the bug just looking at the code, especially when the code is confusing.

I was about to finish a problem called "Hotels" from POI, but I got 99%. There was only one case wrong and it was one of the larger cases (N = 5000). Now I'm stuck, because I couldn't find anything wrong with the code, even though it is relatively short. I used an approach similar to this.

I'm also quite confused, because I got OK verdict and got 9/10 points for the test case even though one of the subtests was wrong when I checked. Am I not supposed to get 5 points or so?

See screenshot

Would you guys be so kind to point out if I did anything wrong? Also, how do you guys deal with situations where you have to debug large tests?

#include <bits/stdc++.h>
using namespace std;

int n;
long long ans, tmp[5001], sum[5001], p[5001];
vector<int> g[5001];

void dfs(int u, int p, int d) {
	tmp[d]++;
	for(int i = 0, v = g[u][i]; i < g[u].size(); i++, v = g[u][i]) if(v != p) dfs(v, u, d+1);
}

int main() {
	scanf("%d",&n);
	for(int i = 1,u,v; i < n; i++) {
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i = 1; i <= n; i++) {
		fill(sum+1, sum+n+1, 0);
		fill(p+1, p+n+1, 0);
		for(int j = 0; j < g[i].size(); j++) {
			fill(tmp+1, tmp+n+1, 0);
			dfs(g[i][j], i, 1);
			for(int k = 1; k <= n; k++) {
				ans += tmp[k]*p[k];
				p[k] += tmp[k]*sum[k]; // distributive property
				sum[k] += tmp[k];
			}
		}
	}
	printf("%lld", ans);
}

From my perspective, I feel like many DP problems are really hard to code and easy to bug out, especially when there are many dimensions and you have to check the upper and lower bounds for each of them. Also, I find that when debugging DP problems with many dimensions, it becomes very tedious and the printing format gets very messy, which makes it really hard.

This particularly caused me to fail in the last round (369), since I couldn't get my code right on C, Do you guys have any tips on how I could improve?

Also, for a slow coder like me, would you recommend iterative or recursive DP? Which is easier and faster to code?

Hi all,

I've been wanting to start training in acm.timus.ru lately, but I don't really know where to start. It allows you to sort the problems by difficulty, but I really have no idea how it compares to CF problems. If I want to start at Div 2. D/E, what's the lower and upper bound of the difficulty level that I should be looking for?

Hi all,

After being in the competitive programming community for a year now, I've noticed that some people tend to use Python for the first Div.2 problems. I'm starting to want to do that too, since it's faster and easier to code. However, the resources online involving Python for competitive programming are fairly limited. Any recommendations on how I should start?

Hi all. This morning I tried to look for some problems by tag, so I ticked the "show tags for unsolved problems" box, but nothing changed. I also went into settings and tried changing some of the options, but when I pressed save, everything reverted back to what is was before! Is anyone experiencing the same issue? If so, are there any solutions?

Hi all. I've been trying some bitmask+DP problems lately, and I've found one that is a little too challenging for me: 510D - Fox And Jumping. I looked at the editorial, and the first thing they tell us is that the problem reduces to finding a set of lengths such that GCD is 1 and has minimal cost. Would anyone be so kind to explain how this works? Thanks in advance.

Hi, I've just come across this problem, and I thought it was really nice. I feel like I need a lot more practice with problems such as these. Anybody know of any similar good ones here on codeforces that are for div. 2? Anything that's DP + greedy is also fine. Thanks in advance.

Does anyone know how to manually check coded solution against large tests? Many of the new USACO problems haven't been uploaded to an online judge that I know of yet, so I would like to check the solution myself. Obviously, I can't go through each line of the test and compare their output to my output. Any suggestions?

Problem Statement (story changed so it's easier to understand): The are N problems and M programmers. The ith programmer (1 <= i <= M) can complete the task in ti minutes. Each programmer solves on problem at time. What is the shortest time required for all the programmers to finish all of their tasks?

Example:

Input: N = 5, M = 2, t1 = 7, t2 = 12

Output: 24

Any suggestions? Thanks.

Hi. I've submitted some code here, and I don't see anything wrong with it yet. It works fine when I compile it on my machine with C++11, but when I submit, the program just prints a random long long. Can anybody find the flaw? Thanks.

Submission: 18021654