Hints for Contest 3 problems:
The idea and motivation behind these hints is that you should only open them up after spending a decent amount of trying to solve the problem yourself. Also open the hints in sequential order.
Example: Try the problem for 40 mins, then open hint 1. Then using hint 1 only, try the problem for another 20-30 minutes. If still unable to make much progress only, then open hint 2 and so on.
The benefit of knowing a partial solution rather than the complete solution is that you can work out the later stages of the problem yourself, thus improving your problem solving skills.
TLDR; use the hints cautiously, if you start relying on them too much, it can hamper with your learning process.
Hint 1
Brute force O(NM) works but is slow, how about you sort A_i ’s and B_i ’s first
Hint 2
Don’t force the usage of maps/sets/any of the content taught this week. Treat this as a trick question, it doesn’t require any content taught in Week 3
Hint 3
Once A_i ’s and B_i ’s are sorted, then A_1 + B_1 < A_1 + B_2 < \dots < A_1 + B_M < A_2 + B_M < A_3 + B_M < \dots < A_N + B_M
Hint 1
Don’t think graph theory, don’t think DFS, think simpler
Hint 2
If cell (x, y) has plant, then assume all its 4 sides would have had a fence, so #fences += 4. But what if cell (x, y + 1) is also a plant, then remove the top fence, so #fences -= 1
And similarly what about (x, y - 1), (x + 1, y), (x - 1, y)
Hint 3
How do you represent such a large grid by a 2d array? You cannot. So you put all the plants into a “data structure” such that you can query if a certain cell, (i.e neighbours of a plant) are plants or not
Hint 4
“data structure” could be a “set<pair<int, int> >” or “map<int, set<int, int> >” or “map<int, map<int, int> >”
Hint 1
The full subtask is not that easy. How about we represent the entire array by a set S, where each element of the set S is a position where a new partition starts
Hint 2
How will we handle an update? If A_i is changed, firstly assume A_i got set to -1, so we assume to break into 3 partitions, one ending at A_{i - 1}, second one constitutes the single element A_{i} and third one starts at A_{i + 1} (i.e insert i, i + 1 into S). Now think A_i is actually set to the new correct value. So maybe it merges with the left partition, i.e check A_i \% A_{i - 1} == 0, if yes then remove i from S. Now check if it merges with the right partition, i.e check A_{i + 1} \% A_{i} == 0, if yes then remove i + 1 from S.
Hint 3
Handling query is basically asking for a given i, what is the just smaller than or equal element to i present in S. How do we find that? We first call auto it = S.upper_bound(i), then do it-- this ensures we are at the correct position.
Hint 1
This problem can be solved by PBDS as well as Sets
Hint 2
This hint is for those who wish to solve it using PBDS. For PBDS, broad idea is to brute force all subarrays. For a given subarray of length L, calculate M, such that M*L \geq K, i.e M = \left \lceil \frac{K}{L} \right \rceil. Now if all the elements of this subarray are present in PBDS, then you can find the {\left \lceil \frac{K}{M} \right \rceil}_{th} smallest element of this subarray using a find_by_rank in PBDS. Note that two different entries of the same element should be treated differently inside the PBDS data structure as well, maybe consider putting in pair<value, position> instead of just the value into the PBDS
Hint 3
For a solution idea using sets only, refer to “Alternate Solution” in the editorial of the problem here
Hint 1
What would be the brute force-ish greedy strategy? Use the soldier with highest A_i, then update that soldier, i.e set A_i = \left \lfloor \frac{A_i}{2} \right \rfloor, then again pick the soldier with the new highest A_i and keep on doing this
Hint 2
How to do this fast? Use Priority Queue / Set, can extract largest/smallest element of a priority queue/set
Additional Exercise
As an additional exercise, if you are able to AC this question using both priority_queue and sets, then try to compare the runtimes and see if there is any remarkable difference? How about discussing this in the discuss below with your findings
Hint 1
You want to have one DS (data structure), let this DS be X, that tells you for a given chef, which country they belong to and another DS, let this DS be Y, that given a country tells how many votes this country has as of now and finally another DS that tells you given a chef how many votes do they have, let this DS be Z. Now every mapping given originally between Chef and his country can be put in X, then every vote for a chef can update Z directly and Y indirectly (via usage of X)
Hint 2
X = “map<string, string>” or “unordered_map<string, string>”, Y = “map<string, int>” or “unordered_map<string, int>”, Z will be similar to Y
Additional Exercise
As an additional exercise, if you are able to AC this question using both maps and unordered_maps, then try to compare the runtimes and see if there is any remarkable difference? How about discussing this in the discuss below with your findings