SPOJ.com - Problem SORTOUT

SORTOUT - Mahammad and strings

#sorting

Professor Mahammad was busy with working their machine learning project in XYZ University. His team collected many data for the analysis of specific procedures. As the length of individual data objects were quite large, he used a popular hashing technique for getting a unique identifier for each data. Unfortunately, the hashing function generated similar result strings for data. As it is not suitable for the project, he started to think what to do with those strings. Suddenly, he came up with a new idea for a problem for beginners. Now he asks, for the given strings in each query, how many lexicographically smaller or equal strings exist in the input?

Input

First line of the input contains two positive integers N and Q, respectively, the number of input strings and the number of queries.

The following N lines represent the strings generated from the procedure.

Finally, the next Q lines contain the query strings which you need to process.

The input section contains strings with only lowercase English letters.

Output

For each of the Q lines, you need to output the number of equal or lexicographically smaller strings.

Note: The sum of the lengths of the input and query strings does not exceed 200000, separately.

Example

Input:
4 3
fury
fuzzy
dizzy
future
fuzz
evil
freeze

Output:
3
1
1

Submit solution!

hide comments

< Previous 1 2 Next >

	vineetjai: 2020-09-05 10:12:29 Use "\n" instead of endl. Expected Complexity: O(nlogn+q*logn)
	hodobox: 2018-12-31 04:02:15 I agree with wisfaq. A O(n^2) or O(nq)-ish solution won't run in a fast language (C++) even in 5s if the cases are strong, so the only way to get AC even with a 1s limit would be with a correct algorithm anyway. Like this, it's just turning down solvers for no reason - not preventing any excess 'bad solutions', just TLE'ing correct ideas in a slow language/with a small constant. And this is especially if it's 'for beginners' - you wouldn't want them to have to switch language, or have to optimize constants even if their idea is right, would you?
	julkas: 2017-09-30 14:53:21 I think time limit is OK. You must find the best algo. Good problem.
	[Rampage] Blue.Mary: 2017-09-30 11:45:44 If the constraints are set to "The total length of input string doesn't exceed 5000000" and "time limit is 3 seconds", we may not waste so much time quarrel with each other.
	wisfaq: 2017-09-30 10:15:23 No need to change the time limit if the problem is moved to tutorial Otherwise I disagree with BlueMary.
	Min_25: 2017-09-30 04:54:46 "The sum of the lengths of the input and query strings does not exceed 200000" is not correct. (at least, it can be > 390000.) re: they are less than 200000, SEPERATELY. Please write it in the description. The current description is a bit ambiguous. And please write that each string does not contain whitespaces. re: done, thank you. (Re) Thank you ! Last edit: 2017-10-01 16:51:52
	[Rampage] Blue.Mary: 2017-09-30 01:21:57 It seems that Java is too slow for this problem. Nevertheless, I don't think the time limit should be changed, because not all problems are designed to be solved in any programming language. If you prefer same kind of problems of long time limit, consider problem CLONE. Last edit: 2017-09-30 01:36:42
	wisfaq: 2017-09-29 20:54:16 I don't think your answer is a proper reply to my post. I don't have seen any solutions in Java or Pypy so far. I will only agree with you if Bluemary (or someone else) solves the problem in Java or Pypy on SPOJ. Last edit: 2017-09-29 21:02:39
	wisfaq: 2017-09-29 10:10:17 Some languages have a rather long start up time on SPOJ (e.g. Java and Pypy). Therefore time limits shouldn't be shorter than 0.5 sec. If the problem is for beginners it should be placed in tutorial as you can guess from the name of that collection. re: you are not obliged to solve the problem, thus no changes will be made on constraints. There is a nice approach for solving the problem which is applicable to even Java and Python. If you need further help, you can ask [Rampage] Blue.Mary. :) Last edit: 2017-09-29 11:05:42
	testing java: 2017-09-29 00:10:20 Was there some huge performance upgrade between g++ 4.3.2 and gcc 6.3? i tried sending exactly same code using different compilers and gcc 6.3 results with AC and g++ 4.3.2 with TLE. Apart from that - I find it rather unpleasant, when someone sets time limit so tight that i can't get AC using java (so i get AC in another lang and downvote problem just to show my dissatisfaction). This time limit - it is whole new level... like really, what's the point? To make people use this particular version of compiler? Or you just like to piss off people on the internet? re: We just wanted to make people think about intended solutions, rather than 3 lines of code. As it's for primarily beginners, you could skip the problem, you are not obliged to solve it. Moreover, the problem can be solved in Java as well, even under half time limit. <3 Last edit: 2017-09-29 07:04:14

Submit solution!

Added by:	mahmud2690
Date:	2017-09-25
Time limit:	0.100s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All
Resource:	Me, MYSELF & I