Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

parag776's blog

By parag776, history, 13 months ago, In English

Suppose I have a list of strings S, each string at most 50 characters long. I'm looking for a data structure and algorithm that can handle the following query efficiently:

Given another list of strings G (a small list of at most 20 strings), I want to find the lexicographically smallest subset of at most 15 strings from S. The result should satisfy the condition that each string in G is a substring of each and every string in the result. i need fast query.

I've searched extensively but couldn't find a satisfactory answer. Most solutions I found address the case with a single string in G, but I need to handle multiple strings as stated above.

Example: S: ["hello my", "yuck ", "mr elan", "now is the", "parag", "hello", "yustuc"] Query1: G: ["el", "m"] Query2: G: ["yu", "uc"] Desired Result1: ["hello my", "mr elan"] Desired Result2: ["yuck", "yustuc"]

If anyone has insights or knows the answer, please share your knowledge.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By parag776, history, 18 months ago, In English

we have any arbitrary set of numbers such that the length of the set is greater than every number in the set and sum of all the numbers in the set is even, then this forms a graph with those numbers being the degree of the each vertex respectively in the graph. is always true?

I could not find the answer to it. maybe I did not look hard enough.

explanation with example:

suppose there is a set {4, 2, 4, 6, 2, 3, 1}

here every number in the set is less than 7 (length of the set) and sum of the numbers is 22 which is even, then this set can be converted to a graph of 7 vertices with those numbers as their degrees.

(a simple graph)

can someone Please answer.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it