Today I have been wondering about a problem. Calculate the range xor of all the numbers between l and r which doesnt contain the letter 5.

Now the sum or count of all 5 letter less elements can be fairly easily solved using digit dp in their decimal form. Range xor on the other hand would require us to represent the number in binary form and essentially breaks down the information of whether the number had a letter 5 or not. Not only can I not keep track of a decimal letter in a binary number, the sub states in this dp are not independent from the original state either. By that i mean, say I place a 1 in some index, and count all the positioning of the remaining digits such that the remaining digits dont make up a 5. But obviously this state is dependent on the overall number we build and whether that has a 5 in it or not. Using digit dp for this problem thus becomes difficult.

How exactly can I solve this problem? This problem was inspired from some variations of 2036F.

Hello all today I struggled a lot with C2, especially because I am not used to using sets, actually not used to using any data structure other than map or vector, I have used queues for BFS only. So I have decided to spend a few days with them.

Please suggest some problems, which are not higher than maybe 2000 rated on CF equivalent, which cannot be solved in desired time or memory without specific data steuctures. One example is stacks for finding the nearest element smaller in the left/right using stack (or vector with push back). Another example maybe using sets to maintain indexes of appearances with updates, which was used in C2. Some people say some sorts of balanced paranthesis substring problems can be solved only using stack but I have only ever used a map for that purpose at best.

This problem was the first time I encountered a problem of DP on trees, and even with a decent amount of practice in DP, the states similar to that of "maximim score in the subtree of j considering j is taken or not", did not occur to me during the contest probably because such a state breaks quite easily when the coins are taken from let's say all the neighbours at a distance of <= 2.

This is the best I could come up with for the above variation:

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

void solve() {
    int n, c; cin >> n >> c;
    vector<vector<int>> adj (n);
    vector<int> a (n); for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n - 1; ++i) {
        int u, v; cin >> u >> v;
        --u, --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<vector<int>> dp (1 << 2, vector<int> (n)); //dp[i][j] = maximum coins from the subtree of j when i type of influence is faced by the parent
    //0: influence of no nodes in the subtree reach the parent
    //1: influence of the children only reaches the parent
    //2: influence of the current node only reach the parent (also means the current node is active)
    //3: influence of the current node and the children reach the parent (curr node active)
    auto dfs = [&] (auto&& self, i64 v, i64 p) -> void {
        dp[2][v] = a[v];
        dp[3][v] = a[v];
        for (i64 u: adj[v]) {
            if (u == p) continue;
            self(self, u, v);
            dp[0][v] += max(dp[1][u], dp[0][u]);
            dp[1][v] += max(dp[2][u], dp[3][u]);
            dp[2][v] += max(dp[1][u] - 2 * c, dp[0][u]);
            dp[3][v] += max(dp[2][u] - 2 * c, dp[3][u] - 4 * c);
        }
    };
    dfs(dfs, 0, -1);
    cout << max({dp[0][0], dp[1][0], dp[2][0], dp[3][0]}) << '\n';
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    while(T--) solve();
    return 0;
}

The above solution is wrong for the above problem, counterexamples are plenty. The reason is because the code only takes care of influence of children passed onto its parents, however it is easy to see that a node once picked not only influences it's children and parent, but also it's siblings, which is not taken care of. This is where the difference from the actual problem becomes apparent. Influence upto one units do not affect the siblings, hence the same state works for neighbour-only influence.

As a side effect however, the code works perfectly for a linear graph, i.e a tree with single children only, thus this code can be thought of as the solution to the problem when we have an array and we can pick elements at the cost of reducing it's neighbours upto 2 indices on both sides by c, with the goal to maximise the score.

Anyone knows any standard procedure for such problems?

Recently a friend and I have been discussing a problem we saw somewhere:

Alice and Bob are playing a game where they have n piles of stones. In one move one can pick a particular pile and remove all other. Then they have to split the chosen pile into exactly n piles with at least one stone each. One who doesn't have a move loses.

The constraint were: n <= 1e6, a[i] <= 1e18,

Initially I thought that the setup is very similar to a Sprague-Grundy problem. I can consider calculating the grundy values of a few number, and try finding a pattern relating to n. First of all calculating the grundy values are difficult to find in itself. I have to consider the transition: splitting the number into all possible multisets of size n, xoring the grundy values of the individual elements together and taking the mex amongst all possible multisets. This is in and of itself is a huge task to accomplish. However let's say we do it somehow. But I don't think these are the correct grundy values for the problem. Picking a pile is not independent of the other piles. Hence xoring is wrong. I have calculated the grundy values for a problem in which I split a pile into n piles. One who cannot have a valid move loses.

I wonder if this is even solvable by the Sprague-Grundy theorem? Can anyone please help me solve this problem? I welcome people to comment why or why not my initial setup for solving it by grundy values is correct or not.

I recently read about the Sprague grundy theorem on cp-algorithms, and I have been thinking about the extension of the example given in the website. Below I explain the game and the solution, can anyone with some experience on this theorem tell me if I am correct or correct me please? The game is as follows, we have several piles of stones. In one move we can pick a pile and then remove

i) if it has at least 3 stones then remove three numbers from it, then optionally we can split the pile into two parts.

ii) if at least two stones, we can remove two stones from it

iii) if it has only one stone then we can remove a single stone from it.

(as one may identify, this is similar to the example given the the cp-algorithms.com article on the Sprague-Grundy Theorem (crosses-crosses), only different thing is we have several strips, equivalently stone piles) A player has to do any one of the three moves in his/her turn. The one who has no moves loses as usual. My algorithm for solving this would be to calculate the grundy number for each pile (I will xor sum them later using bouton's theorem) the grundy number can be calculated by calculating the mex of G(n — 2), G(I — 2) xor G(n — I — 1) (for all I in 2 to n — 1) and G(n — 1). The term G(I — 2) xor G(n — I — 1) for each possible I is there to account for the optional splitting of the piles, which is indeed a valid state that the initial pile points to. Terms are added in the set (whose mex we will find later) keeping in mind that they satisfy the criteria, eg, G(n — 1) should be included in the set only when n == 1. etc. I calculate the mex recursively, then xor sum the result to find the grundy number of the final state.

Given an array, you can pick exactly $$$x$$$ (where $$$x \leq 3$$$) elements in one operation and decrease each of them by 1 (all picked elements must be at least 1). You then add $$$x$$$ points to your score. You need to maximize your points with these operations applied any number of times as long as it is possible.

I think you could use a priority queue to greedily pick the top $$$x$$$ largest elements and decrease them by 1, but the problem is that the elements can go up to $$$10^{16}$$$.

Also, the length of the array is at most 200.

I have n nodes and some edges connecting them. There are a few colored nodes (it is mentioned which ones) on some of these nodes. My task is to spread this color to the remaining computers.

I can spread a color from node i to j if j is adjacent to i, i already has an antivirus installed, either directly or has it installed previously from some other computer, at a cost of cost[i]. The cost array is given to us as input as well.

what is the minimum cost for spreading the antivirus? The constraints allow for an O(n^2) solution. (sorry for bad format, I am typing on my phone)

My friend asked me this problem which was asked to him in a recent Interview. Can anyone explain what topics i should learn to solve this problem? From the looks of it it seemz like i have to read MST, but I am not sure since the cost is node dependent and not edge so it is difficuly for me.

Hi the following was asked by Adobe on an OA a day ago. The OA is over.

You are given a tree of n nodes and each node has a number associated with it. These numbers range from 1 to n, inclusive. You have to output the number of edges which if removed, makes the maximum frequency of a node value of both the resulting trees to be <= k. k is given and is <= n. The value of n goes upto 1e5.

I tried dfsing the frequency but soon realised I cant have the frequency of each subarray without storing them somewhere, which obviously wouldnt work due to both MLE and TLE. Please help!

The other day someone asked a problem: where we are mining x amount of gold at the end of each day, and the collected gold can be used to buy some extra machines which in turn helps us dig more gold, the machines cost some amount of money each, but their production rate is same (= z). We want maximum gold at the end of the $$$K^{th}$$$ day This problem was pretty simple because the production rate was the same for all the machines.

My question is, if the production rate was different, then which machine would have been the optimal choice at the start of each day? This question can be reduced to the following: Consider an array: $$$a_1(K - i) - b_1, a_2(K - i) - b_2, \ldots, a_n(K - i) - b_n$$$, where $$$a_k$$$ is the production rate of the $$$k^{th}$$$ machine, $$$b_k$$$ is the cost of the $$$k^{th}$$$ machine, and $$$i$$$ is the $$$0-indexed$$$ day, changing which I want to observe the order of the elements. Here, each element of the array represent how much each machine will contribute to the total gold if it's bought at the start of the $$$i^{th}$$$ day. Now, slightly deviating from the original problem and ignoring that one machine can be bought only once, is there a way to find the maximum element for each $$$i$$$, from $$$0$$$ to $$$K - 1$$$ with $$$K \leq 10^5$$$?

I am new to graph theory and need some help. I have an undirected tree with a few coloured nodes. My task is to calculate the minimum distance from each node to any of the coloured nodes in $$$O(N)$$$. N is the number of nodes. The number of coloured nodes may be up to N.

My solution: Initialise an array of size N with infinity as the elements, this will represent my min distance array, say $$$A$$$. Change $$$A[i] = 0$$$, if $$$i$$$ is a coloured node. Run a dfs from each coloured node and each recursive call of the dfs ends if it either reaches a leaf or a node with $$$A[i]$$$ less than or equal to that of the parent. Store the distances on A along the way.

But I suspect that the complexity of this approach is $$$O(N^2)$$$, consider a tree with a root and many children, and let these children have many more single child each, and let the leaves be coloured, kind of like a flower. Since I don't know of a problem that is based on this, I cannot verify anything.

If anyone can prove if it's $$$O(N)$$$ or $$$O(N^2)$$$ then please help me. If it has bad complexity or downright wrong then please help me with a solution.

Another approach I though of was to simultaneously run a dfs from all the coloured nodes and end a recursive call of each node if it's reached a previously reached node, kind of like a radiation from the coloured nodes. But I don't even know if that's possible for me to implement.

help pls

This problem has been bugging me since morning today. I have a number K, and an array A with N elements. I can merge any amount of numbers in the array such that each element in the end is at least K. I want to merge minimum number of elements to achieve this, or in other words the final array should have maximum size.

Let's say $$$K = 6$$$ and $$$A = [4, 4, 5, 5, 6, 7, 9]$$$ (here size = $$$N = 7$$$) I have this proposed solution which I have not been able to prove/disprove with several random outputs.

The solution is: consider the subset of A containing all the elements which are less than K, which for this A is $$$A' = [4, 4, 5, 5]$$$, (size = $$$N' = 4$$$), my solution is:

For the given example, max length = 3 + min(2, 3) = 5, which corresponds to 9, 9, 6, 7, 9 after merging the 4s and 5s.

If anyone can help me give a counterexample or help me prove the solution, please do so.

How do I calculate the length of longest subarray ending at index $$$i$$$ $$$(1 \leq i \leq N)$$$ with elements smaller than or equal to $$$A[i]$$$ in an array A of length N for each $$$i$$$? $$$(1 \leq N \leq 10^6).$$$

I have tried a few different approaches with two pointers, tried using the merge sort algorithm to find the lesser than or equal to elements before each element but every approach I tried have obvious flaws.

Can anyone please help me with this? I would appreciate a solution without the use of data structures like segment trees or BIT and such, as I am yet to learn about these.