Problem A :

The ball is invisible for time: [S, T], which means it will be invisible for the section: [S*V, T*V]. To hit the ball by Akoi D must not lie in this section, that means D should be less than S * V or greater than T * V

Link to my code

Problem B:

Just a straight forward implementation, print those numbers which are not equal to X.

Link to my code

Problem C:

Key Point: There are no white cells inside the polygon of black cells, so, you can assume the polygon as a contiguous block of black cells, whose sides we have to find.

To find sides: For every black cell X, check its adjacent (left, right, up & down) cels (let's say each cell Y), we have to check the followings:

1. If Y is black then it doesn't contribute to the answer.

2. If Y is white, then check whether that edge is already added or not. If it is not added then add this side to the answer.

To check some side is added or not, you can use loops or maintain some data structure like set (in C++). I've used the set in my code.

Link to my code

Problem D:

Consider a vertical line that passes through the center of the circle (h, k). Iterate on the integer points (let say each point P) of that line such that those points lie inside the circle i.e. points: (h, k-r) to (h, k+r), r is the radius of the circle. For each point P, find the number of integer points on the left and right of P such that they lie inside the circle.

To find the number of points you can use the binary search.

NOTE: Maintain the precisions.

Link to my code

Problem E:

You can rephrase the problem statement to: for each node find the least weighted cycle or say it is impossible. To find the least weighted cycle one can use Dijkstra's algorithm. For each node s, find the shortest path to other nodes, and then go to those nodes and check for the cycle with the least weighted path.

Link to my code

Thanks :)

I want to iterate on masks such that all combinations of masks with only 1 bit missing first, then all combinations of masks such that 2bits are missing, and so on. This trick I need in TSP and I have used O(2^n) space. Is there any better way to do it in O(1).

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define sz(v) (int)v.size() 
#define all(v) v.begin(), v.end()

int main(){
    
    int n; cin >> n;
    vector <vector<int>> graph(n, vector<int>(n)); //adjacency matrix with weights
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        cin >> graph[i][j];
      }
    }
    vector <vector<int>> dp(n, vector<int>(1 << n, 2e9));
    for (int i = 0; i < n; ++i) {
      dp[i][(1 << n)-1] = graph[i][0];
    }

    //better way to apply masks? in O(1) space??
    vector <int> all_masks(1 << n); 
    iota(all(all_masks), 0);
    sort(all(all_masks), [&](int a, int b) {
      return __builtin_popcount(a) < __builtin_popcount(b);
    });

    reverse(all(all_masks));
   //here..
    for (int m: all_masks) {
      int x = __builtin_popcount(m);
      for (int i = 0; i < n; ++i) {
        if (!(m >> i & 1)) continue;
        for (int j = 0; j < n; ++j) {
          if (m >> j & 1) continue;
          dp[i][m] = min(dp[i][m], graph[i][j] + dp[j][m | (1 << j)]);
        }
      }
    }
    cout << dp[0][1] << endl;

    //finding path
    vector <int> path{0};
    int curr = 0;
    int mask = 1;
    while (mask != (1 << n)-1) {
      int dist = 2e9, node = -1;
      for (int i = 0; i < n; ++i) {
        if (mask >> i & 1) continue;
        if (dist > graph[curr][i] + dp[i][mask | (1 << i)]) {
          dist = graph[curr][i] + dp[i][mask | (1 << i)];
          node = i;
        }
      }
      assert(node >= 0);
      path.push_back(node);
      mask |= (1 << node);
      curr = node;
    }
    for (int i: path) cout << i << ' ';

    
    return 0;
}

Hello Codeforces, I was solving the problem, and I got the right idea, but there was a problem with choosing the index randomly using uniform_int_distribution<int>.

sol1: This gives me WA at test case 32 because I was trying to pick index directly.

sol2: Now, at this time I pick randomly with lower_bound, and it worked.

Is there any better way to choose index uniformly and randomly?

Thanks in advance:)

Hey everyone, could you plz help me in this past contest problem I think this could be done using DP and come you with some states but it doesn't work for every case or maybe this is a simple maths problem. I'm sharing the pdf of the problem state, link of the contest

Thanks in advance.

I was solving a problem on LightOj, my solution was correct but the problem was in the std::cout, then I replaced it to printf, then It worked fine. Plz anyone reply, why this happened.

solution without cout: link

Thanks in advance :)

Hey everyone, I was solving this trie problem. At first, I was trying to solve this using std::unordered_map which causes TLE, but then, I tried using static array, and then it worked fine.

Solution with std::unordered_map: (link) https://pastebin.com/LtLQ47fk

Solution using static array: (link) https://pastebin.com/BUDPhxXk

Is there is any way to optimize the std::unordered_map?

Is there any mistake in the unordered_map solution?

Is there something wrong?

I was learning Paint fence algorithm: n fences, k colors, how many ways to paint the n fences such that atmost 2 adjacent fences have the same color. For more details link.

I tried the standard solution, but I think this is wrong, or I did understand the problem wrong.

Look for the test case n = 4, k = 3, result from the standard algorithm is 66, but if I try the brute force method, then I got 60.

Standard DP approach counts 6 more than brute force.

My brute force code:

string s;
int n;
int ans;
void permute(int idx){
    if(idx == n){
        int cnt = 0;
        for (int i = 0; i < n-1; ++i){
            if(s[i] == s[i+1]) cnt++;
        }
        if(cnt <= 1){
            cout << s << endl;
            ans++;
        }
        return;
    }

    for (char ch: {'A', 'B', 'C'}){
        s[idx] = ch;
        permute(idx+1);
    }
}


int main(){
    cin >> n;
    s = "ABCD";
    permute(0);
    cout << ans;

    return 0;
}

I think standard code also counts these 6 permutations:

[AABB], [BBAA], [CCAA], [AACC], [BBCC], [CCBB]

Could you please explain what is wrong.

You are given a tree of n nodes rooted at 1. Each node of the tree has a color associated with it. Now you are given q queries. In each query, you are given a node number X and for each query, you have to mark the node X as special and all the other nodes in its subtree with the same color also as special. If a node is marked as special in the query then for all the other subsequent queries, it remains marked as special. For each query, you need to print the total number of special nodes in the tree after you perform the marking operation in the query.

input format: first-line: N, next N-1 lines: edges, next line with N integers: the color of the ith node, next line query: Q, next Q lines for jth query: X.

constraints: N, Q, X <= 1e5.

Sample input:

                    5              
                    3 1
                    3 2
                    2 4
                    2 5
                    1 1 2 2 1
                    4
                    2
                    4
                    5
                    1

sample output:

                 2 
                 3 
                 3 
                 4

my solution, but inefficient:https://ideone.com/whqXRa

I have used an efficient way to insert into the set from the rear end and delete it from another(like sliding window). DP array will store the addresses of the inserted node, when we need to delete that node, we don't need to apply to find() function. Just use that address then the node is deleted... I hope this will be helpful for somebody...

#include<bits/stdc++.h>
#define endl '\n'
#define F(i,a,b) for(int i=(int)a;i<=(int)b;i++)
using namespace std;

void solve()
{
    int t;
    cin >> t;

    while(t--)
    {
        string s;
        cin >> s;

        multiset <char> store;

        for(auto i: s) store.insert(i);

        string hash;
        cin >> hash;

        multiset <char> match;
        multiset<char>::iterator dp[hash.size()];

        bool possible = false;

        F(i,0, hash.size() -1)
        {
            dp[i] = match.insert(hash[i]);
             

            if(match.size()==store.size())
            {
                if(match == store)
                {
                    possible = true;
                    break;
                }
                else
                {
                    match.erase(dp[i-store.size()+1]);
                }

            }
        }

        if(possible) cout << "YES";
        else cout << "NO";

        cout << endl;

    }

}


int main(){
    
    solve();

    return 0;
}