Hi. I am trying to solve this problem.

For convenience, I have summarised the problem statement below:

Problem Statement

We are tasked to arrange X Apples, Y Cherries and Z mangoes on a line, Compute the number of valid arrangements (modulo 1e9 + 7). All X + Y + Z fruits must be used in a single arrangement.

A valid arrangement is defined as an arrangement in which no two fruits of a similar kind are adjacent (no wraparound).

Constraints: 1 ≤ X, Y, Z ≤ 2e5

Time limit: 2s

Example

Example of a valid arrangement for X = 2, Y = 2, Z = 2 is:

Apple Orange Cherry Apple Orange Cherry

Example of a invalid arrangement for X = 2, Y = 2, Z = 2 is:

Apple Apple Orange Cherry Orange Cherry

My analysis

If the constraints were smaller, an obvious dynamic programming solution would suffice. However, the large constraints here seem to point towards a combinatorics solution (which I cannot figure out).

Could someone please advise me on how to solve this problem?

Hi. I am trying to solve this problem.

For convenience, I have summarized the problem statement below.

Problem Statement

Given an array of length  ≤ 2e6 containing integers in the range [0, 1e6], find the longest subarray that contains a majority element (i.e. an element that occurs  > ⌊ N / 2⌋ times in a list of length N).

Time limit: 1.5s

Example

If the given array is [1, 2, 1, 2, 3, 2],

The answer is 5 because the subarray [2, 1, 2, 3, 2] from position 1 to 5 (0-indexed) has the number 2 which appears 3 > ⌊ 5 / 2⌋ times. Note that we cannot take the entire array because 3 = ⌊ 6 / 2⌋ .

My attempt

The first thing that comes to mind is an obvious brute force (but correct) solution which fixes the start and end indexes of a subarray and loop through it to check if it contains a majority element. Then we take the length of the longest subarray that contains a majority element. This works in after a small optimization. Clearly, this will not pass the time limit.

I also tried asking the same question on stack overflow, but did not receive a satisfactory answer (after several wrong suggestions and much discussion, I tried implementing the answer by Pham Trung that was given in the link, but it seems to fail on this case: [3, 3, 5, 2, 4, 1, 5]).

Could someone please advise me on a better approach to solve this problem?

Hi. I am trying to solve this problem.

For convenience, I have replicated the problem statement below:

A person is on floor N of a building. He has to take the lift down to floor 0. To use the lift exactly once, one token is needed. This lift is special as it can only travel downwards for one of the following levels each time it is used:

1, 5, 10, 17, 50, 100, 500, 1000, 5000, 10000

For example, if the person is standing on floor 6, one way to reach floor 0 is to take the lift down 5 floors, then take the lift again to go down 1 more floor (6 - 5 - 1 = 0). 2 tokens are used in this case.

The objective is to find the minimum number of tokens that the person needs to use to reach floor 0 from a given floor N. For the above example, the answer is 2.

My analysis:

This problem looks exactly like the classical coin change problem where we want to find the minimum number of coins to make up a given value. The latter problem can be easily solved using DP or BFS (or maybe matrix exponentiation?). Applying the same methods on this problem could earn us the points for all except the last subtask where N ≤ 1e9.

Could someone please advise me on a solution that would solve this problem in its entirety?

UPD: I managed to solve this problem (thank you misof for your clear and concise hint!).

My approach can be found here.

#include<bits/stdc++.h>

using namespace std;

int arr[] = { 10000, 5000, 1000, 500, 100, 50, 10, 5, 1 };

int n, k, ans = (int) 1e9;

int main() {
	cin >> n;
	while(k <= 4) {
		int cur = n, i = 0, t = 0;
		if(k * 17 <= cur) {
			cur -= k * 17;
			t += k;
		}
		while(cur) {
			t += cur/arr[i];
			cur %= arr[i];
			i++;
		}
		ans = min(ans, t);
		k++;
	}
	cout << ans << "\n";
	return 0;
}

Hi. I am trying to solve this problem.

For convenience, I have summarized the problem statement below (based on my understanding):

Given a directed graph with N vertices and E edges (with cycles and not necessarily connected), find the minimum number of edges that we need to retain such that connectivity between vertices is retained as given in the original graph.

Input size: 1 ≤ N, E ≤ 2e5
Time limit: 1s

For example, for the following graph:

We should retain the edges:

0 -> 1
1 -> 2
1 -> 3

So we must use a minimum of 3 edges.

Note that:
0 -> 2 is redundant as we can use the path 0 -> 1 -> 2 to get from 0 to 2.
0 -> 3 is redundant as we can use the path 0 -> 1 -> 3 to get from 0 to 3. (Thanks filippos for catching this mistake!)

This problem seems to be asking for the transitive reduction of a graph which can only be found in at least O(n²) based on what I found on Google and this clearly wouldn't pass the time limit. Furthermore, the list of AC solutions suggests that there is a linear time solution to this problem.

Could someone please advise me on how to solve this problem?

UPD Managed to solve this problem (thank you please_delete_account for your incredible patience and explanation!).

I indeed had a wrong understanding of this problem and overly constrained it.

For readers who are looking for the solution to this problem, I have posted my solution below:

#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 5;
int n, m, a, b, ans, par[maxn];
vector<int> to[maxn];
bool has[maxn], vis[maxn];
unordered_set<int> path;

int find(int u) {
	return par[u] == u ? u : par[u] = find(par[u]);
}

void dfs(int u) {
	vis[u] = 1;
	path.insert(u);
	for(int i = 0; i < (int) to[u].size(); i++) {
		int v = to[u][i];
		if(find(u) != find(v)) {
			continue;
		}
		if(vis[v] && path.find(v) != path.end()) {
			has[find(v)] = 1;
		}
		if(!vis[v]) {
			dfs(v);
		}
	}
	path.erase(u);
}

void addEdge(int u, int v) {
	to[u].push_back(v);
	par[find(u)] = find(v);
}

int main() {
	scanf("%d %d", &n, &m);

	ans = n;

	for(int i = 0; i < n; i++) {
		par[i] = i;
	}
	for(int i = 0; i < m; i++) {
		scanf("%d %d", &a, &b);
		addEdge(a, b);
	}
	for(int i = 0; i < n; i++) {
		int r = find(i);
		if(has[r]) {
			vis[i] = 1;
		}
		if(!vis[i]) {
			dfs(i);
		}
	}
	for(int i = 0; i < n; i++) {
		int r = find(i);
		if(vis[i] && !has[r]) {
			has[r] = 1;
			ans--;
		}
	}
	printf("%d\n", ans);
}

Hi. I have been experimenting with Python for CP lately. I read from various sources, including this, that running Python code in PyPy 2 will speed up runtime by a lot as compared to the Python 2 interpreter. Tests that I performed in the SPOJ enormous input test seemed to confirm this.

I recently tried to solve another problem on CodeForces using Python. I submitted the exact same code using both PyPy 2 and Python 2 options. However, the PyPy option clearly got TLE while the Python 2 option got AC comfortably.

My submissions using PyPy 2 and Python 2.

I am unable to explain this contradiction as I am new to Python. Is any Python expert here able to explain this strange occurrence please? Thanks in advance.

Hi. I am trying to solve this problem.

For convenience, I have replicated the problem statement below:

Given a list of N integers (non-distinct) where and each integer , sort the integers based on the lexicographical order of their prime factorization.

Example (the first number is N):

5
2 3 4 5 6

Expected Output:

2
4
6
3
5

Explanation:

2 = 2
3 = 3
4 = 2 * 2
5 = 5
6 = 2 * 3

Time limit is 2s and memory limit is 32MB.

My attempt:

I used a fast factorization method to factor each integer into its prime factors and store them into a 2D matrix, M. M[i][j] represents the j^th prime factor of the i^th integer in the list such that M[i][j] ≤ M[i][j + 1].

Now, I use a custom sort method to sort the list. Let's say we want to compare integers at position u and v in the list.The sort function will compare M[u] and M[v] using lexicographical comparison.

My code.

This method is correct but it will get MLE (not TLE surprisingly). I tried asking this problem on stackoverflow but could not obtain a satisfactory answer. Could someone please advise me on a better way to solve this problem?

p.s. not sure if this info would be helpful — this problem is tagged with dfs in the source.

Hi. I have always been curious about learning styles. Since this is a competitive programming site, I'll discuss purely about my learning in algorithms/programming. No, this is not another post about how to become red in 1 year or how to become as good as _________ (fill in the blank). I just wish to understand how people comprehend(difficult) stuff.

I have been dabbling with algorithms/competitive programming for almost a year. Some algorithms like binary search, sliding window, trivial DP are so easy to understand that simply anyone could learn it. However, there are also topics like complexity theory, max flow, DP optimizations, etc. that are really complicated. Any attempts to understand the copious mathematical proofs in topcoder articles, university lecture slides, etc. would make my head hurt. After many hours of trying to internalize those difficult concepts, I feel that I don't understand anything. When I run into this deadlock, I will just forgo the proof and learn about how the algorithm works. This makes me feel really uncertain as I didn't understand why it works (Maybe I am just stupid).

I was wondering, how do people even understand these complicated algorithms and proofs? Surely memorizing the algorithm isn't the right way to go? Would anyone care to share about how they learn algorithms? What would you do if you ran into the same situation as me?

Does anyone know/have any good K-D Tree implementation in C++/Java?

Hi. I am having problem trying to solve JOI 2013/2014 — Historical Research. The english problem statement can be found here.

For those who understand Japanese, the editorial can be found here

The input and output data can be found here

My approach is as follows:

Let product = element × frequency in subarray [L, R]

We use a BST to answer our max product queries and element updates efficiently, Each element of the BST would be  < product, element, frequency >  and the elements in the BST are sorted by product.

Let N be the number of elements in our array and Q be the number of queries.

Perform square root decomposition on the queries by breaking them into blocks and sorting them in increasing order of left bound followed by increasing order of right bound. Time-complexity of this operation is O(Q × logQ).

We keep 2 pointers to track the left and right bound of the subarray that we have calculated the element frequency for. Every time we shift the left pointer, we remove the elements from the left side of the subarray from the BST. Every time we shift the right pointer, we add the new elements in the subarray to the BST.

Of course, we have to update the product accordingly. Time-complexity of this operation is . This is because each query can only be in one block and block size is . Hence, the left pointer can only move by on each query (i.e. in total) and the right pointer moves by O(N) in every block and we have blocks. Hence, right pointer moves by in total. Finally, each movement incurs an update operation in the BST which is O(logN). That proves the time-complexity for this part.

Every time we need to query the maximum product, we just query the largest element in the BST, which is O(logN).

Hence, the total time-complexity is . However, 1 ≤ N, Q ≤ 100, 000, which implies that the algorithm will perform operations in the worst case (do note that the time-limit is only 4s). I tried coding this solution and as expected, it passed all but the last subtask (which uses the largest input).

Could someone please advise me on how I could optimize my solution's time-complexity?

I am trying to solve the HackerRank problem "Bytelandian Tours".

Here is the link to the problem.

I think that the problem requires us to count the number of Hamiltonian circuits in a general graph — which is a NP-complete problem. Hence, I think that there must be some way to avoid the direct enumeration of all possible Hamiltonian circuits like what this solution did. I am unable to comprehend the author's logic though. Could someone please advise me on how to solve this problem?

Thanks in advance.

Hi. I am having problem trying to upsolve the "Max Score" problem which was used in HackerRank's Rookie Rank 3.

Here is the link to the problem.

After reading the editorial, I am puzzled why the recurrence does not consider all permutations of elements in subset(S,i) because the order in which we choose the elements in the subset also affects the overall sum.

For easier reference, I have reproduced the puzzling part of the editorial here. Credits to HackerRank for the editorial.

I tried asking in the problem's forum but I have not received any reply for more than 3 weeks. Could someone please advise me why we do not need to consider all permutations of elements?

Thanks in advance.

There is a component in the bottom right of every contest page with the heading "Contest materials". However, this component seems to be missing from the contest page of round #415 (both div 1 and 2). Link.

Is it just me or this a bug?

I am trying to solve an interactive problem from atcoder's practice contest. The abridged problem statement is as follows:

Given the value of N where N ranges from [1,26] and Q where Q is the maximum number of queries that one can make, sort a list of distinct uppercase alphabets in ascending order. N indicates that there are N characters starting from 'A'. Hence, N = 5 means that our final list must contain 'A', 'B', 'C', 'D' and 'E'.

A single query is defined as printing out a string "? x y" where x and y represent the characters we want to check the relation between (e.g. "? A B"). The problem restricts the number of such queries to Q. Hence, we must determine the final order of the characters using at most Q queries.

For each query, we get a binary answer '<' or '>' from stdin. '<' indicates that x comes before y in the final list. '>' means otherwise.

Problem link: here (Do note that atcoder account is needed to view the task)

My attempt:

I tried using merge sort to solve the problem — I changed the comparison at the merging step to get the ordering of characters using the console. I managed to solve constraints for N=26, Q=100. However, the strictest task requires a solution that fulfils the constraints N=5, Q=7.

After some research, I found that merge sort's worst case number of comparisons is n * ceil(logn) — 2^(ceil(logn)) + 1 which gives 8 in this case. I couldn't find a better sorting algorithm that would solve the problem — I even tried STL sort which proved to be worse than merge sort.

Could anyone please advise me on how I could solve this problem?

U.D. I just revisited this problem today. I solved it by using a single comparison to detect if there were exactly 5 elements with at most 7-comparisons. If this were true, I hard-coded a separate comparison-efficient function to handle this. Otherwise, just use merge-sort.

AC code here.

I am trying to solve an algorithmic problem that is described as follows:

There are K types of items and 2 supermarkets. Each selling all K types of items but at different prices. Please find the maximum number of unique items that can be bought given that we can spend only X dollars in supermarket 1 and Y dollars in supermarket 2.

Bounds:

1 <= K <= 2000
1 <= X, Y <= 10000

Example:

K = 5, X = 6, Y = 12

Supermarket 1 (We have 6 dollars):

Type 1: 5
Type 2: 1
Type 3: 5
Type 4: 6
Type 5: 3

Supermarket 2 (We have 12 dollars):

Type 1: 3
Type 2: 5
Type 3: 4
Type 4: 6
Type 5: 7

In this case, the optimal answer would be 4 because we can buy item types 1 and 2 in supermarket 1, item types 3 and 4 in supermarket 2.

Problem source: here

I have interpreted it as a coin change problem where one must collect the maximum number of different denominations. Hence, I don't think that a greedy algorithm can work here (since it fails for coin change). More precisely, if one sorts the 2 item lists according to item-price pairs, it would clearly fail since one type of item may be very expensive in both lists.

The next method of my list is to use DP. But, I think DP might be too slow.

Could anyone please advise me on a better solution to solve this problem?

Edit:

I managed to solve the problem thanks to data_h and Deemo's help in the comments. The complete solution can be found here

Once again, thanks a lot for all your help!

I am trying to solve round #383 problem D (div 2):

Problem statement:here

I can complete every step up till the usage of DP. In my code, I used 2-D DP like what was mentioned in the editorial. Somehow, my code is failing the following test case:

10 5 100
6 18 35 6 87 58 4 53 37 71
465782 57034 547741 748298 315223 370368 679320 349012 9740 622511
1 2
10 9
6 7
3 6
7 1

Expected Output: 2050129
My Program Output: 1836591

My attempt:

#include <iostream>
#include <vector>
#include <unordered_map>
//#define debug
using namespace std;

#define ll long long
#define v64 vector<ll>
#define um unordered_map<ll,ll>
#define mp make_pair

ll n,m,w,a,b;

typedef struct woman {
	ll w, b;
} woman;

woman ww[1005];
ll par[1005], rk[1005],dp[1005][1005];
um cw, cb;
int val[1005];

ll find(ll x) {
	ll p = x;
	if(par[x]!=x) p = find(par[x]);
	return par[x] = p;
}

inline void un(ll x,ll y) {
	ll px = find(x), py = find(y);
	if(px != py) {
		if(rk[px] > rk[py]) {
			par[py] = px;
			rk[px] += rk[py];
 		} else {
			par[px] = py;
			rk[py] += rk[px];
		}
	}
}

ll solve(ll cur, ll t) {
	if(dp[cur][t]!=-1) return dp[cur][t];
	if(cur <= n && t>0) {
		if(ww[cur].w<=t) {
			if(val[find(cur)]) {	
				val[find(cur)] = 0;
				ll a1  = 0;
				if(cw[find(cur)]<=t) a1 = cb[find(cur)]+solve(cur+1,t-cw[find(cur)]);
				ll a2 = ww[cur].b+solve(cur+1,t-ww[cur].w);
				val[find(cur)] = 1;
				ll a3 = solve(cur+1,t);
				return dp[cur][t] = max(a1,max(a2,a3));
			} else {
				return dp[cur][t] = solve(cur+1,t);
			}
		} else {
			return dp[cur][t] = solve(cur+1,t);
		}
	}
	return dp[cur][t]=0;
}

int main(void) {
	#ifdef debug
		freopen("in","r",stdin);
	#else
		ios_base::sync_with_stdio(false);
		cin.tie(0);
	#endif
	cin >> n >> m >> w;
	fill_n(rk,n+1,1);
	fill_n(val,n+1,1);
	for(int i = 1; i <= n; ++i) fill_n(dp[i],w+1,-1);

	for(int i = 1; i <= n; ++i) {
		cin >> ww[i].w;
		par[i] = i;
	}
	for(int i = 1; i <= n; ++i) {
		cin >> ww[i].b;
	}
	for(int i = 1; i <= m; ++i) {
		cin >> a >> b;
		un(a,b);
	}
	for(int i = 1 ; i <= n; ++i) {
                cw[find(i)] += ww[i].w;
                cb[find(i)] += ww[i].b;
        }
	cout << solve(1,w) << endl;
	return 0;
}

If I remove the DP (from the solve function), my program will pass the test case. Hence, it is clear that my DP is wrong. However, I do not know how to write the DP properly. Could someone please advise me on why my code is wrong?

This was the given solution for round #383 (Div 2) problem C:

The problem statement: Here

The solution:

Make a directed graph and put edge from i and crushi. If the graph has vertex such that its in-degree is 0 then obviously answer doesn't exists. Otherwise the graph consists of some cycles. For each cycle suppose that its length is len. If it has odd length, add len to S, otherwise, add len / 2.

Answer is the LCM of numbers in S.

I am unsure why the LCM is the answer. Is anyone able to advise me?