Contest 3 - Hints to Problems [OFFICIAL]

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.

  1. Distinct Pairs - DPAIRS
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

  1. Fencing - FENCE
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> >”

  1. Yet Another Partition Problem - EXUNC
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.

  1. Yet Again a Subarray Problem - SUBPRNJL
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

  1. Save Konoha - SAVKONO
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 :slight_smile:

  1. Chef of the Year - CVOTE
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 :slight_smile:

17 Likes

I think there is a problem with the 5th Question Code : SUBPRNJL . I cant view the question. Anyone facing this issue :neutral_face:

1 Like

YES.

One can refer the following solution for EXUNC:
https://www.codechef.com/viewsolution/31955845

1 Like

@sidhant007 For the question Save Kanoha, I don’t think (it’s a guess) that the problem can be solved using set container in C++ as the nature of the set is, it only stores distinct elements. If you use set then as in the problem it is not said that each A_{i} will be distinct or even if it is said there is higher chance that when the power of soldier gets halved, it becomes equal to another soldier.

The problem is a specific to priority queue or max heap if you are using C Progamming because of the maintenance of the largest element in the sequence after A_{i} is halved.

Although I would be interested in the logic of solving the problem using set.

3 Likes

For any question that can’t be done by sets because of the distinct property, the most common hack is to put in a pair in the set where the second element of the pair is a timestamp which differs for each element, thus ensuring no two elements are same (alternatively use a multiset, but while using multiset be careful on how you do the erase), for SAVKONO something like this:

set<pair<int, int> > S;
for(int i = 1; i <= n; i++) {
   cin>>a;
   S.insert({a, i});
}
while(K > 0) {
    pair<int, int> tmp = *S.rbegin();
    S.erase(S.rbegin());
    K -= tmp.first;
    S.insert({tmp.first / 2, tmp.second});
}
17 Likes

@sidhant007 Thanks for the hack! :slight_smile:

@sidhant007 Hi Sidhant. Solved the SAVKONO problem now. I want some help on finding its time complexity. Is it appropriate to paste the code here and express my view on its time complexity?

Sure. I would recommend posting an ideone link but yeah do share your views :slight_smile:

@sidhant007 can you please explain the 2nd form of the query of the question: EXUNC ?

2 \ i - Given i , output the smallest j such that S_i = S_j . That is, the leftmost index which belongs to the same subarray as the ith element.

@sidhant007 Hi. I will paste it here so that you dont have to switch between ideone and this space.

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

int main() {
	// your code goes here
	ios::sync_with_stdio(0);
	cin.tie(0);
	//Power is denoted by p
	int t;
	cin >> t;
	while(t--){
	    int pPain,total_sol;
    	cin >> total_sol >> pPain;
    	priority_queue<int> sol;
    	int power;
    	for(int i=0;i<total_sol;i++){
    	    cin >> power;
    	    sol.push(power);
    	}
    	
    	int count = 0;
    	while(sol.top() > 0 && pPain > 0){
    	    pPain -= sol.top();
    	    sol.push(floor(sol.top()/2));
    	    sol.pop();
    	    count++;
    	}
    	if(pPain > 0){
    	    printf("Evacuate\n");
    	}
    	else{
    	    printf("%d\n",count);
    	}
	}
	
	return 0;
}

So in the worst case all our soldiers’ powers are exhausted.
Each solidier’s power takes \lfloor log A[i] \rfloor +1 to get to 0. So in case of n soldiers it takes \lfloor log A[0] \rfloor +1 + \lfloor log A[1] \rfloor +1 + ... \lfloor log A[n] \rfloor +1 .
This is equal to \lfloor log (p) \rfloor + n where p is the product of all array values.
Since we are pushing and popping during each operation and each push or pop is O(log n), is the final complexity O(\lfloor log (p) \rfloor.2 logn+ 2nlogn ) ? Can we remove \lfloor log (p) \rfloor.2 logn and constant 2 to get the final complexity as O(nlogn) ?
Suggest your views on this approach. :slight_smile:

4 Likes

That’s why my solution was not accepted many times. because i used set.

hi all,
can anyone suggest what is the problem with my solution for problem DPAIRS? i have followed Sidhant’s approach exactly. Below is the link to my code:

@sidhant007, what is the problem with doing s.end() in the first line of the while loop?

@swagata93 Your solution code is not there as you have shared Code-Chef IDE link. Share the My Submissions links or use pastebin.

1 Like

@striker22 thank you so much. Below is the link:
https://www.codechef.com/viewsolution/32135018

Your source-code is not giving correct answers for the given test-cases in the problem statement.
Moreover, I don’t know about the approach because I haven’t seen the videos.

As far as the problem is concerned you should read the problem statement carefully, let me give you a hint, the problem is asking to print N + M - 1 pairs each in the form (A_{x}, B_{y}), such that the sums A_{x}+B_{y} are all pairwise distinct.
That means, take the min value from the sequence B and pair it with each and every element of the sequence A after this you will get N pairs now you need M - 1 pairs to get a total of N+M - 1 pairs, so, take the max element from A and pair it with every element of B except the min element of B because you have already created that pair before so now you get M - 1 pairs and that is what we wanted i.e. N + M - 1 pairs.

The problem with your code is you are changing the initial ordering of the elements (due to sort() function) hence you are getting WA hence don’t change the initial ordering.

For Reference: Competitive-Programming/Code-Chef/Distinct-Pairs at master · strikersps/Competitive-Programming · GitHub

2 Likes

oh I got it. Thank you so much!

Hello Sir @sidhant007 , Can you please tell me why am i getting TLE in Save Konoha.
My Code:->w1mVne - Online C++0x Compiler & Debugging Tool - Ideone.com
It will really helpful If anyone can help. Thanks.

@anon98533376 Its because you are not taking care of the evacuate condition which leads to infinite loop while(z > 0).

Consider the following test case:

5 1000
14 12 32 14 22

Output should be:

Evacuate

But your program goes into infinite loop.

Update-1: Change your while() loop as follows:

ll count = 0, i = n;
while (z > 0 && !s.empty()) {
    ++count; --i;
    auto it = --s.end();
    z = z - it->first;
    ll y = it->first;
    s.erase(it);
    y = y / 2;
    if(y) {
        s.insert(make_pair(y, i));
    }
}
if(z > 0) {
    std :: cout << "Evacuate" << std :: endl;
    continue;
}
cout << count << endl;
1 Like