shareChat hackerearth test help

help
,
21

Btw how much did you score @arjun8115

22

prefix array for each character
(lower bound ,upperbound )for each query

23

Yeah, you are right, but i solved lot of questions where expected output is different from my code output, but i got full marks.

24

I got 156.

1 Like
25

I thought so but I got WA. The solution was passing almost every case I threw at it but still couldnot solve the issue…might have missed something :frowning:

26

Great!

1 Like
27

May be you are missing some corner cases. Like check for when k is equal to frequency of that character…

28

I put that as well…I wish I could share my solution

30

you dont even need binary search. You need to prepare a table for all the indexes of the lower case letters and then you can figure out the logic :slight_smile: . Hope you understand :slight_smile: . If you have any queries, feel free to post, will give out the detailed soln

31

How can we participate in this contest??:sweat_smile:

1 Like
32

Yeah bro pls share detailed solution

33

Question

Given a string Str of size N comprising lowercase English alphabets indexed from 1 to N. Answer the following Q Queries on the string which can be of either types:

  • L \ ch \ K : Find the largest index I such that there are exactly K repetitions of the character ch in the range 1 to I of the string Str.
  • S \ ch \ K : Find the largest index I such that there are exactly K repetitions of the character ch in the range 1 to I of the string Str.

Constraints

1 \leq T \leq 50
1 \leq N,Q \leq 10000

Solution:

Naive solution wont work as the constraints of N and Q are high enough to get TLE :slight_smile: . So we will build a lookup table to answer the queries in O(1) time.

Observation:

  • The answer to the query L \ ch \ K is ans - 1, where ans = the index of the (K + 1) \ th occurrence of the character ch in the string Str .

Note: Here is an edge case for the query type L \ ch \ K . Consider the string abaaba. Now for the query type L \ a \ 4 we need to print the length of the whole string as the largest index till the character a has occurance 4 will be the index of the last element of the array.

  • The answer to the query S \ ch \ K is the index of the Kth occurrence of the character ch in the string Str.

We create a array of vectors of length 26, say named look. Then we traverse the entire string and store the indexes of the characters in look . Then for each query we can use the stored values to answer the queries in O(1) time.

Overall complexity in answering all the queries is O(Q).

C++ Implementation:

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

#define pb push_back
#define mp make_pair
#define ll long long

void solve() {
	int n,q;
	cin >> n >> q;
	vector <int> look[26];
	string s;
	char ch;
	cin >> s;
	for(int i=0;i<n;i++) {
		ch = s[i];
		look[ch - 'a'].pb(i+1);
	}
	while(q--) {
		char choice;
		int k;
		cin >> choice >> ch >> k;
		if(choice == 'L') {
			if(k == look[ch - 'a'].size()) {
				cout << n << '\n';
			}
			else {
				cout << look[ch - 'a'][k] - 1 << '\n';
			}
		}
		else {
			cout << look[ch - 'a'][k-1] << '\n';
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	int t;
	cin >> t;
	while(t--) 
	solve();
}
5 Likes
34

This is the first time i have ever written a detailed solution of a problem :grin: :grin: . Suggestions on how i can improve are appreciated :slight_smile: .

1 Like
35

Can you elaborate this. How did you conclude your observation regarding the solution would be either 1 or 2?

36

Greedy + Disjoint set union will also work :slight_smile:

37

Yeah, answer can never be greater than 2. We can always find atleast a ‘g’ which share edges with atmost 2 ‘g’. So, just remove this 2 shared ‘g’ and hence that single ‘g’ is disjoint from remaining graph.
Hope it help.

38

What about

gdg
ggg
gdg

My friend gave me this case yesterday. He said that this question is better solved

  1. Disconnected = 0
  2. Articulation Point exists = 1
  3. Otherwise 2
1 Like
39

If nothing, take leftmost and topmost g to be at (I,J), other g can atleast be at (I+1,J) and (I,J+1) thus removing those two will always disconnect grid.

40

Hi, I also scored156/170 points, How much time did you guys take to score 156 points? Does time play a role in rankings.
I took 29min.

41

My code gives correct answer for this test case. So I dont think that this is one of those 2 testcases on which our code failed(Assuming @arjun8115s code also failed tc2 and 9)