Contest 2 - Hints to Problems [OFFICIAL]

[techie_pals]

Hints for Contest 2 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. Rectangle - ZCO15004

Hint 1

We can dismiss all those rectangles that are not bounded by the plane or a point on all 4 sides since their sides can be extended to form a more optimal rectangle.

Hint 2

If we fix the point that is on the boundary of the top edge of the rectangle (call it pnt) , the sides will be bounded by the first point (on both left and right) such that its y is less than pnt.y. If no such point exists then it will be bounded by the plane

Hint 3

If we sort all points from left to right, we can find the left-right binding points for each point using this algorithm: Find the nearest smaller numbers on left side in an array - GeeksforGeeks

Hint 4

The case where the top edge of the rectangle is touching the plane is solvable by realising that these rectangles are formed between adjacent points. Therefore we can take 500 * max difference of x between adjacent points

2. Chefs in Queue - CHFQUEUE

Hint 1

For all points i, find the smallest point j such that (j>i) and a(j)<a(i).

Hint 2

After doing this for all i, multiple the answer (initially 1) by (j-i+1)

Hint 3

This can be done fast using this algorithm: Find the nearest smaller numbers on left side in an array - GeeksforGeeks

3. Compilers and parsers - COMPILER

Hint 1

Find the first ‘break point’ in the string. A point i is a ‘break point’ if it is the first point such that the frequency of ‘>’ (from index 0 to index i) is greater than the frequency of ‘<’. Note that all prefixes ending at location j where (j>=i) are invalid

Hint 2

The second condition for a prefix being valid is that the frequency of ‘<’ is equal to frequency of ‘>’

Hint 3

Maintain a stack in which you push an element whenever you encounter ‘<’ and pop an element whenever you encounter ‘>’

Hint 4

If you need to pop an element but the stack is empty, this is a break point

Hint 5

The answer is the last i such that i<break point, and the stack is empty after you have completed the appropriate operation for the character at s(i)

4. Matched Brackets - ZCO12001

Hint 1

Maintain a stack in which you push an element whenever you encounter ‘(‘ and pop an element whenever you encounter

Hint 2

The maximum nesting depth is simply the maximum size of the stack at any point in time.

Hint 3

Let’s push all of the ‘times’ at which the stack became empty into a vector (including time 0). If at index i (0 based indexing), the stack becomes empty, push (i+1) into the vector.

Hint 4

The maximum length of a subsequence is simply the maximum difference between adjacent elements in the vector.

5. Wormholes - ZCO12002

Hint 1

Store the contest start and end times in a pair vector.

Hint 2

Sort the use times of both wormholes in ascending order.

Hint 3

For each contest, find the latest time at which you can arrive and the earliest time at which you can leave.

Hint 4

You can find the latest arrival time by doing an upper bound search on the start time of the contest (and decrementing the pointer) and you can find the earliest leave time by doing a lower bound search on the end time of the contest.

Hint 5

The answer is simply the minimum of (leave time - arrival time + 1)

6. Penalty Shoot-Out II - PSHOT

Hint 1

At any point, we know that team A will the game iff, despite missing all of their remaining shots and team B scoring all of their remaining shots, their score will be higher than team B’s score. The inverse is true for team B winning.

Hint 2

Denote team B’s current score by C(B), team A’s current score by C(A), team A’s remaining shots by R(A), team B’s remaining shots by R(B). At any point, team A is winning iff (C(A) - C(B)) > R(B). The inverse is true for B winning.

Hint 3

The implementation for this problem can be simplified by using a queue of pairs. Push pairs in the format {0/1 (for miss or goal), 0/1 (0 indicates team A, 1 indicates team B)}

Hint 4

Keep on popping elements from the queue and updating the scores as required. Break as soon as our win condition has been reached or if the queue is empty.

7. Chef and Street Food - STFOOD

Hint 1

store all of the values in the array and the answer is simply the maximum of (p(i)/s(i)) x v(i) across all N types of street food.

8. Stupid Machine - STUPMACH

Hint 1

Each box i can contain a maximum of S(i) tokens. However, whenever you put a token into the ith box, you are also putting a token into boxes 0…(i-1).

Hint 2

The practical maximum capacity of each box is minimum of S(0), S(1), … , S(i))

Hint 3

Run a for loop from 0 to n-1 and find the practical max capacity for each point by keeping track of the prefix minimum

Hint 4

Finally, the answer is simply the sum of practical max capacity across all boxes.

9. Not All Flavours - NOTALLFL

Hint 1

While running our algorithm, we will need to keep track of the frequency of each cake flavour in the range. To do this, maintain an int array “arr” (with all elements initialised to 0) where arr(i) represents the number of cakes with flavour i in the range.

Hint 2

In order to keep track of the number of unique flavours in a range, simply increment the amount whenever a flavour frequency changes from 0 to 1 and decrement it whenever it changes from 1 to 0.

Hint 3

If a range (l, r) contains less than n flavours, we can consider this to be a valid range and check if it is the largest.

Hint 4

If a range (l, r) is valid, we should check if range (l, r+1) is also valid. If range (l, r+1) is not valid, we need to contract it until we get a valid range.

Hint 5

In order to contract a range, we can either do (l, r-1) or (l+1, r). Note that if range (l, r) is invalid, we have already visited range (l, r-1). Therefore, it would be redundant to visit it again. Hence it would be optimal to increase the lower bound and check.

[prabhat_7]

hey, i need Rectangle Editorial or its hint, plz add that too.

[izhang05]

Is there a hint for Infix to Postfix?

[animi_murali]

For COMPILER prob, how is this <<>><> valid? If this is valid, the count should be 4 right?

[fkhjoy]

The count should be 6 because there are 3 valid pairs each having length 2.
First << after this when > comes we can pair <> and only < left. Then > comes and paired.
Then <> comes together and paired.

[deepraj99]

6

[dracule_62]

what is the ans for this case <<<<> ???

[deepraj99]

ans - 2

// you can understand by it…
while( n>0 ){
if( ch[i] == ‘<’ )
st.push(’<’);
else{
st.pop(); }
count += 2; }

[supandeep]

It’s ans should be 0 since there is no valid pair from start.
If the input is like <><<< then it’s output should be 2

[animi_murali]

**how come this solution is wrong atleast for subtasks?** code - CHFQUEUE
    int ans = 1;
    for (int i = 0; i < n; i++)
    {
        int j = i;
        while (j < n)
        {
            if (arr[j] < arr[i])
            {
                ans = ans * (j - i + 1);
                // std::cout<<"index i- " << i<<" index j - " << j <<"aaj -"<< j-i+1 <<" ans- "<<ans<< std::endl;
                break;
            }
            j++;
        }
    }
    std::cout << ans % 1000000007 << std::endl;

[rishi18]

I don’t get where I am wrong in PSHOT

try:
    for i in range(int(input())):
        n = int(input())
        s = input()
        s = list(s)
        c = 0
        d = 0
        e = n
        g = n
   
        for i in range(len(s)):
            if(i%2 == 0):
                c += int(s[i])
                e -= 1
            else:
                d += int(s[i])
                g -= 1
            if(c > d + g):
                print(i+1)
                break
            elif(d > c + g):
                print(i+1)
                break
            elif(c == d and i == 2*n-1):
                print(i+1)
                break
            
            
except EOFError:
    pass

please help me

[rishi18]

Whats wrong in my code of COMPILER

for i in range(int(input())):
    s = input()
    a = 0
    b = 0
    c = 0
    if(s[0] == '>'):
        a = 0
    else:
        for i in s:
            if(i == '<'):
                b += 1
            else:
                c += 1
        if(b == c):
            a = b + c
        else:
            d = min(b, c)
            a = 2*d
    print(a)

[kush419]

A doubt in hint 1 of problem Compilers and parsers.
All prefixes ending at location j such that j<i should be invalid na?
Or am I interpreting it wrongly?
say for example
<<> is an invalid prefix. (j = 2, indexing from 0, i does not exist)
however
<>> is a valid prefix, right? (j = 2 and i =2)
Thank you.

[soham04]

PLEASE TELL ME WHERE AM I GOING WRONG ?

#include <iostream>
#include <bits/stdc++.h>
#include <limits>
#include <unordered_map>
#include <vector>
#include <string>

using namespace std;

int main()
{
    int t;
cin >> t;
while (t--)
{
    int n;
    string str;
    cin >> n >> str;
    int a = 0, b = 0;
    int i = 0;
    for (i = 1; i <= str.length(); i++)
    {
        if (((i) % 2 != 0) && str[i - 1] == '1')
        {
            a++;
        }
        if (((i) % 2 == 0) && str[i - 1] == '1')
        {
            b++;
        }

        if (i % 2 == 0)
        {
            int tmp = str.length() - i;
            int e = tmp / 2;
            int o = tmp / 2;
            if (a > e)
            {
                break;
            }
            if (b > e)
            {
                break;
            }
        }
        else
        {
            int tmp = str.length() - i;
            int e = (tmp / 2) + 1;
            int o = tmp / 2;
            if (a > e)
            {
                break;
            }
                if (b > e)
            {
                break;
            }
        }
    }
    cout << i << endl;
}
return 0;
}

[gaurav_5542]

When i run below solution for NOTALLFL problem than it shows me an partially corrected solution. It will be great help if someone will help out with this problem.
# cook your dish here

def main():
    for T in range(int(input())):
        N,K = list(map(int,input().split()))
        segment = dict()
        max_segment_length = 0 
        for i in input().split():
            if int(i)<=K :
                if segment.get(i) is None:
                    if len(segment)+1 < K:
                        segment[i]  =  1
                    else:
                        # print(segment)
                        t = sum(segment.values())
                        max_segment_length= max(max_segment_length , t)
                        segment = dict()
                        segment[i] = 1
                else:
                    segment[i] += 1
        # print(segment)
        t = sum(segment.values())
        max_segment_length= max(max_segment_length , t)
        print(max_segment_length)        

                    
                    
if __name__ == '__main__':
    main()  

As I had run through possible testcase but still it is working. i can not able to troubleshoot.

[renol_27]

this is wrong because you are calculating the total answer first and than taking its mod. In such a case the variable with data type int(or long long) will already shoot out of bounds and will start storing garbage values.
(ab)%N=(a%Nb%N)%N
use this property and change ans=((ans%N)*(j-i+1)%N)%N to keep int within bounds

[liveon21]

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> oset;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename
enable_if<sizeof dud(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge range(c i, c j) { return rge{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(…);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << “(” << d.first << ", " << d.second << “)”;
}
sim dor(rge d) {
*this << “[”;
for (auto it = d.b; it != d.e; ++it)
*this << “, " + 2 * (it == d.b) << *it;
ris << “]”;
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(…) " [” << #VA_ARGS ": " << (VA_ARGS) << "] "
using ll = long long;

void test_case() {
int n;cin>>n;
string s;cin >> s;
vector hash;
string k="";
for(int i=0;i<n;++i)
{
if(s[i] == ‘+’ || s[i] == ‘-’)
{
if(hash.empty()) hash.push_back(s[i]);
else
{
while(true)
{
if(hash.empty()){
hash.push_back(s[i]);
break;
}
else if(hash.back() == ‘(’)
{
hash.push_back(s[i]);
break;
}
else
{
k += hash.back();
hash.pop_back();
}
}
}
}
else if(s[i] == ‘*’ || s[i] == ‘/’)
{
if(hash.empty()) hash.push_back(s[i]);
else
{
if(hash.back() == ‘+’ || hash.back() == ‘-’ || hash.back() == ‘(’)
hash.push_back(s[i]);
else
{
while(true)
{
if(hash.empty()){
hash.push_back(s[i]);
break;
}
else if(hash.back() == ‘(’ || hash.back() == ‘+’ || hash.back() == ‘-’)
{
hash.push_back(s[i]);
break;
}
else
{
k += hash.back();
hash.pop_back();
}

				}
			}
		}
	}
	else if(s[i] == '^')
	{
		hash.push_back(s[i]);
	}
	else if(s[i] == '(')
		hash.push_back(s[i]);
	else if(s[i] == ')'){
		while(true){
			if(hash.back() == '('){
				hash.pop_back();
				break;
			}
			else
			{
				k+= hash.back();
				hash.pop_back();
			}
		}
	}
	else
	{
		k+=s[i];
	}
	
}
int size = hash.size();
for(int i = size-1;i >= 0;--i)
{
	k += hash[i];
}
cout << k << '\n';

}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
while(T–){
test_case();
}
}

can any one tell me what is wrong in my solution?

[anon81091548]

https://www.codechef.com/viewsolution/33614457
I am getting WA. can anyone help me?
Thanks in advance.

[ag0965]

in Chef queue question for the given input n = 4, k = 2, a = [1,2,1,2] shouldn’t answer should be 5
For a[3] = fearfulness 1, a[2] = fearfulness 1, a[1] = fearfulness 2, a[0] = fearfulness 1,
total fearfulness = 5.
What am I missing?

[d_k2402]

// Wormholes
/* subtask 1 test case 4 and testcase 6 showing wrong answer /
/ i m not able to understand whats wrong with my code plz any one can help me out …*/

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

int main() {
// your code goes here
int n,x,y;
cin>>n>>x>>y;
vector<pair<int, int>> element;
int arr1[x];
int arr2[y];
long long ans=INT_MAX;
for(int i=0;i<n;i++)
{
int s,e;
cin>>s>>e;
element.push_back(make_pair(s,e));
}
for(int i=0;i<x;i++)
cin>>arr1[i];
for(int i=0;i<y;i++)
cin>>arr2[i];
sort(arr1,arr1+x);
sort(arr2,arr2+y);
for(int i=0;i<n;i++)
{
int u=upper_bound(arr1,arr1+x,element[i].first)-arr1;
int l=lower_bound(arr2,arr2+y,element[i].second)-arr2;
if(u<x && l<y&& u>=0)
{
long long k=arr2[l]-arr1[u-1]+1;
//cout<<arr1[u-1]<<" “<<arr2[l]<<”\n";
ans=min(ans,k);
}

}
cout<<ans<<"\n";
return 0;

}