Блог пользователя jarvis_yash

Need help to solve this proble
Автор jarvis_yash, история, 8 месяцев назад, По-английски

Given an array of strings A of size N and two integers B and C Let D be the number of strings of length C that contain exactly B of the strings in words as substrings. Return D modulo (10+9).

|A|<=6 |A[i]|,C<=50 B<=N

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

original problem

→ Ответить
  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    u got solution for it ? ( it was asked in placement test )

    → Ответить
    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      if it was one string then we would have done dp with kmp but writing 6 kmp functions(in worst case) dont see me optimal in this case...i am also curious for the approach

      → Ответить
  • »
    »
    8 месяцев назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    .

    → Ответить
»
8 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Here's a brute force approach using dfs. not sure if it will suffice

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

const int MOD = 1e9 + 9;

int dfs(string curr_str, vector<string> &A, int B, int C)
{
	if (curr_str.size() == C)
	{
		int count = 0;
		for (auto &s : A)
		{
			if (curr_str.find(s) != string::npos)
			{
				count++;
			}
		}
		return count == B ? 1 : 0;
	}

	int total = 0;
	for (char ch = 'a'; ch <= 'z'; ++ch)
	{
		total += dfs(curr_str + ch, A, B, C);
		total %= MOD;
	}

	return total;
}

int required_substrings(vector<string> &A, int B, int C)
{
	return dfs("", A, B, C);
}

int main()
{
	vector<string> A = {"z", "zz", "zzz", "zzzz"};
	int B = 2;
	int C = 3;
	cout << required_substrings(A, B, C) << endl; // Expected output: 50
	return 0;
}

Your code here...
→ Ответить