[NEW] Add solution for Counting Towers

[vingoel26]

🎯 Problem Information

• Problem Name: Counting Towers
• CSES Link: https://cses.fi/problemset/task/2413
• Category: Dp
• Estimated Difficulty: Hard

💡 Proposed Approach

Describe the algorithm/approach you plan to use:

• The problem is solved using Dynamic Programming (DP) with two states for each position i:

  • dp[i][0]: number of valid configurations ending with one pattern
  • dp[i][1]: number of valid configurations ending with another pattern

• The recurrence relations are defined as:
  dp[i][0] = (2 * dp[i + 1][0] + dp[i + 1][1]) % mod
  dp[i][1] = (dp[i + 1][0] + 4 * dp[i + 1][1]) % mod

• Base case:
  dp[n][0] = dp[n][1] = 1

• The final answer is (dp[1][0] + dp[1][1]) % mod.

• The approach iterates bottom-up, calculating all states from n-1 to 1.

• Time Complexity: O(N)

• Space Complexity: O(N)

---

📝 Implementation Notes

Any special considerations or optimizations needed:

• Requires fast I/O (ios::sync_with_stdio(false) and cin.tie(NULL))
• Uses modular arithmetic (mod = 1e9 + 7)
• Handles large constraints (n ≤ 10^6) efficiently
• Possible optimization: reduce DP memory to O(1) by storing only next state
• Edge cases to consider:
• Smallest input (n = 1)
• Multiple test cases
• Large n (to verify modulo operations and performance)

---

🏷️ Labels

Please add appropriate labels:

• hacktoberfest
• good first issue
• help wanted
• dynamic-programming

---

👤 Assignee

• I would like to work on this issue
• I'm available for guidance/review

---

📎 Additional Context

This code implements a Dynamic Programming approach using a 2D state transition table.
It builds the solution bottom-up, ensuring efficient computation for large inputs and multiple test cases.
This pattern is common in problems involving state transitions and recursive relations.

---

🧠 Code Implementation

#include <bits/stdc++.h>
#define int long long
#define inp(n) \
  int n;     \
  cin >> n
#define vin(a) \
  for (int i = 0; i < n; ++i) \
  {                           \
      cin >> a[i];            \
  }
#define vout(a) \
  for (int i = 0; i < n; ++i) \
  {                           \
      cout << a[i] << ' ';    \
  }
#define pb push_back
#define ff first
#define ss second
#define viv vector<vector<int>>
#define nah cout << "NO\n";
#define yah cout << "YES\n";
#define fast \
  ios_base::sync_with_stdio(false); \
  cin.tie(NULL);                    \
  cout.tie(NULL);
#define vi vector<int>
#define vpi vector<pair<int, int>>
#define mod 1000000007
using namespace std;

/*
========================================
Author:         Vinayak Goel
Institution:    IIITL
May the WA avoid you
========================================
*/

viv dp(1000005, vector<int>(2, -1));

void solve()
{
  int n;
  cin >> n;
  dp[n][0] = 1;
  dp[n][1] = 1;

  for (int i = n - 1; i >= 0; --i)
  {
      dp[i][0] = (2 * dp[i + 1][0] + dp[i + 1][1]) % mod;
      dp[i][1] = (dp[i + 1][0] + 4 * dp[i + 1][1]) % mod;
  }

  cout << (dp[1][0] + dp[1][1]) % mod << endl;
}

int32_t main()
{
  fast
  int t = 1;
  cin >> t;
  while (t--)
  {
      solve();
  }
  return 0;
}

[vingoel26]

@ks-iitjmu please assign me the issue