Does bitset optimize time ? or memory only?

Let there is an array ara[n] and a bitset a , both has size n. . if we access the array with a for loop as for(int i=0;i<n;i++)ara[i] the complexity is O(n). Now if we access the bitset as for(int i=0;i<n;i++)a[i] then what is the complexity? O(n) or O(n/32)??

I know the basic of IDA* search, heuristic function etc. . But I can not solve this problem of lightoj . http://lightoj.com/volume_showproblem.php?problem=1121&language=english&type=pdf . here time limit is 2.00 second and Memory limit is 32 MB . But there are also a same problem on UVa online judge . . https://uva.onlinejudge.org/external/101/10181.pdf . It's time limit is 15.00 seconds. I can solve this in .750 second. . But in lightoj time complexity is very tight so I am getting TLE everytime. . I have used manhatton distance here as heuristic. . My code for Lightoj problem is . https://pastebin.com/QSCXhSMp . I have also tried manhatton distance with linear conflict as heuristic but could not get accepted !! Where is the problem?? I think on lightoj there are many(100) test cases . So i need to optimize it . How to optimize ??

There are many famous topics such as Dp, graph theory, Combinatrics.

We know different algorithms and approach such as bitmask DP technique , memorization technique, iteration technique.

Or in graph theory we know BFS, DFS< Dijkstra , MST, Eular trail/circuit and many more.

As a beginner I have learned those famous techniques and many variation by solving problems on different oj.

But now I see that a difficult problem have been appeared , though I have learned this topics I fail many times to solve their variation .

Those variation are always untold or not seen on blogs . But it is hard for me to solve those variation by my own as I am a beginner.

Such as I have learned Eular trail/circuit, I have solved several problems and I thought I could be able to solve any problem related to eular trail/circuit .

But then I stuck on a problem and couldn't solve it , I tried it many hours . Then I searched for solution and seen that , this problem was chinese postman problem . Then I learned about chinese postman and solved this.

Same way I learned tiling DP .

Now I think I should know about those topics which are always untold.

Please tell me as much topics as you can , please give me the link if you can .

Or at least tell as much topics as you can.

I think this will help beginners like me.

Hello, I know how chinese postman algorithm works. But my confusion is on complexity. Is it possible to solve this on polynomial time?? because, if there are n odd vertices , then they can be paired (n-1)*(n-3)*(n-5)*.....1 So , to generate all possible pairing we need massive time if n is big.

So, My first question is , Is it possible to calculate pairing with any algorithm in polynomial time??

And, Is there another approach where pairing is not needed and can be solved on polynomial time??

Please answer.

There are many tutorial of math sites. But I need a any tutorial of vector from a competitive programming point of view. Can someone provide any??

i use 2D array for trie.

I want to learn how to declare memory of 2D array.

let i will insert n string , each string's length will be at most m.

Now how to declare 2D array and why??

please explain.

There are two famous way for implementing trie.

One is by linked list and other is by 2D array.

Now I want to know which will be better.

I think 2D array is better for time but it needs too much space than linked list.

Please someone explain time and space complexity of those 2 approach.

If there are any better approach then tell.

I created a set of structure and sorted was manually. See the code...

class edge    {
public:
    int u, v, w;//variables on set
    edge()  {}
    edge(int a, int b,int c)  {
        u = a;
        v = b;
        w = c;
    }
    bool operator < ( const edge& z ) const {
        return w < z.w;//compare as your wish 
    }
};
set<edge> e;

Then tried to insert some element as u v w

1 2 10

1 3 8

3 2 3

1 4 3

1 3 6

2 1 2

But 1 4 3 didn't added. Then i used multiset and it worked . why?? we know set doesn't contain duplicate element. But there are no duplicate.

I am a beginner. I know basic of KMP, suffix array. I can also generate prefix function,lcp(longest common prefix) only. Please provide some good problems on them. Please try give mainly DIV 2 C and D type(codeforces is better, but you can give also from any other judge) . Because I am a beginner a solved only 4 or 5 problems of those algorithm. If there are good problems harder than Div2 C or D or any other online judge which should be solved to become better , Give them too I will solve them later.

I have a solution of a problem as, h(n) = 26*h(n-1) + 26^(n-3) — h(n-3). n<=10^9.

how to create matrix on this relation?? Is it possible ?? If not how to solve it??

1268 — Unlucky Strings PDF (English) Statistics Forum Time Limit: 2 second(s) Memory Limit: 32 MB

Mr. 'Jotishi' is a superstitious man. Before doing anything he usually draws some strange figures, and decides what to do next.

One day he declared that the names that contain a string S as substring is unlucky. For example, let S be 'ab', then 'abc', 'cabe', 'pqqab', 'ab' etc are unlucky but 'ba', 'baa' etc are not.

So, he gives you the string S and asks you to find the number of names of length n, which are lucky, that means you have to find the number of strings that don't contain S as substring. Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 109). The next line contains the allowed characters for a name. This non-empty line contains lowercase characters only and in ascending order. The next line contains a string S (1 ≤ length(S) ≤ 50), and S contains characters from the allowed characters only. Output

For each case, print the case number and the total number of names that don't contain S as substring. As the number can be very large, print the number modulo 232. Sample Input

Output for Sample Input

3

3

ab

ab

4

acd

ca

5

ab

aaa

Case 1: 4

Case 2: 55

Case 3: 24

Is it possible to get the length of biggest substring which is palindrome on a string on O(n)??

Problem link: https://uva.onlinejudge.org/external/116/p11651.pdf . I know how to convert it to matrix exponentiation, On my solution the matrix is 77*77 size. as there are 200 test case and the matrix may be powered to 10^9 , It will case time limit exceed though O(n^3log(m)). How to make it time efficient ??

Sometimes there are two different recursive function for even and odd n. Such as if n is even, then f(n) = f(n-1)/2, otherwise (if n is odd) f(n) = 3f(n-1) + 1.

I know basic of matrix exponentiation on many variation but now i am facing problem on it.

please someone explain.

What is set covering problem??
How to get a optimal solution(not greedy approximate) ??
which algorithm is needed??

Problem link:http://mirror.codeforces.com/contest/339/problem/C

My solution :http://mirror.codeforces.com/contest/339/submission/27780404

You see here on my function dfs. it is calling new 9 dfs function.(because the vector size can be at most 10 ). so the complexity should be 9^n. Where n can be at most 1000.

I think it's because the programme need not traverse all the state. Before traversing all states it get the answer and return.

Please tell my assumption is right or not?

Be kind to me because it is my first blog.