Secret.Codes's blog

By Secret.Codes, 15 months ago, , 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)??

By Secret.Codes, history, 21 month(s) ago, , 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 ??

By Secret.Codes, history, 23 months ago, , 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.

By Secret.Codes, history, 23 months ago, , 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?? By Secret.Codes, history, 2 years ago, , 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??

By Secret.Codes, history, 2 years ago, , 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??

By Secret.Codes, history, 2 years ago, , 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.

By Secret.Codes, 2 years ago, , 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.

By Secret.Codes, history, 2 years ago, , 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.

By Secret.Codes, history, 2 years ago, , 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??

By Secret.Codes, history, 2 years ago, , 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

By Secret.Codes, history, 2 years ago, , Is it possible to get the length of biggest substring which is palindrome on a string on O(n)??

By Secret.Codes, history, 2 years ago, , 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 ??

By Secret.Codes, history, 2 years ago, , 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.

By Secret.Codes, history, 2 years ago, , What is set covering problem??
How to get a optimal solution(not greedy approximate) ??
which algorithm is needed??

By Secret.Codes, history, 2 years ago, , 