OmaeWaMouShenDeiru's blog

By OmaeWaMouShenDeiru, 3 years ago, In English,

Hey, some problems that requires cumulative frequencies asks for range update and range queries.

This problem in it's simplest form can be solved using segment tree with lazy propagation.

It can also be solved using binary indexed tree, but using it here differs from using it with range update and point query, or point update and range query.

Now I read couple of articales about it, but they all give a breef explanation about direct solution only, that two BITs needed.

I still can't understand why this problem occers and how was this solution invented.

Can someone please explain this topic.

Thanks :D

Edit: This is a link to one of the explanations for this problem.

Read more »

Tags bit
 
 
 
 
  • Vote: I like it  
  • +6
  • Vote: I do not like it  

By OmaeWaMouShenDeiru, history, 3 years ago, In English,

Hey,

For problem: Lauren And Inversions

My code pass all but two huge cases.

What is wrong with my approach ?

Read more »

 
 
 
 

By OmaeWaMouShenDeiru, history, 3 years ago, In English,

This is the problem statement.

In My solution I precalculate the sortedness between existing values and save it in global variable sum

Then I calculate the value val[i][j] where i represent the index of a position with missing value in the given sequence and j represent the index of one of the missing values in vector want,

then I find the rest of sortedness values using TSP function, I used map because the state would be too big to fit in an array.

But the solution didn't pass.

Is there any other optimizations to be considered for my implementation.

Thanks.

Read more »

 
 
 
 

By OmaeWaMouShenDeiru, 3 years ago, In English,

Hey all,

So the best thing to do after a contest is to read editorals for problems that I read and couldn't come up with a solution during the contest.

But I find that most editorials are hardly helpful, because all I find is a direct explanation of the solution.

What I'm saying is that it is better to explain the steps you took to reach that solution, how you thought and came up with it, like sometimes I think of a bruteforce solution and then I conclude something that reduce it to better or simpler solution.

Looking forward to reading more opinions about this.

Read more »

 
 
 
 
  • Vote: I like it  
  • +77
  • Vote: I do not like it  

By OmaeWaMouShenDeiru, history, 4 years ago, In English,

Hey all,

I always felt that programming contests differ from CF To TC to ACM etc,,

Do these contests have different styles in the problems they present.

And does improving my skills in one or two of them should reflect on the others ?

Read more »

 
 
 
 
  • Vote: I like it  
  • +15
  • Vote: I do not like it  

By OmaeWaMouShenDeiru, history, 4 years ago, In English,

Hey,

What is the concept behind graph problems test case generation.

How can I write a random test case generator ?

Read more »

 
 
 
 
  • Vote: I like it  
  • +7
  • Vote: I do not like it  

By OmaeWaMouShenDeiru, history, 4 years ago, In English,

Hello,

I'm trying to solve the last problem in this contest.

and this is my code, my idea is to change every strongly connected component into one node because the cost of travailing between it's nodes is ZERO, this can be done by removing all bridges and then applying union find on elements of the other edges.

Then I create new adjList using elements of the removed edges "i.e bridges", the new graph will form a tree.

Then I apply DFS two times to find the longest path in a tree.

Last step is to follow the longest path and save the sum of edges on the sides of each node, take the maximum sum between the left and right sum.

Sometimes it returns TLE and sometimes RTE.

What could be the mistake, and is there a better way to solve it.

Thanks.

EDIT: now this code gets WA

Read more »

 
 
 
 
  • Vote: I like it  
  • +1
  • Vote: I do not like it  

By OmaeWaMouShenDeiru, history, 4 years ago, In English,

Hey,

Are there any plugins or tools available for codeforces contest, like those for TC ??

Read more »

 
 
 
 
  • Vote: I like it  
  • +9
  • Vote: I do not like it  

By OmaeWaMouShenDeiru, history, 4 years ago, In English,

Hello CF and TC people,

I installed Greed plugin following steps in this link

But I keep getting this screen when I open any problem in the arena

PS: Im using elementary os luna

Any help would be appreciated.

Thanks :D

Read more »

 
 
 
 
  • Vote: I like it  
  • +3
  • Vote: I do not like it  

By OmaeWaMouShenDeiru, history, 4 years ago, In English,

Hay codeforces, Is it possible to solve standard RMQ problem using binary indexed tree with conserving LogN queries ?

Read more »

 
 
 
 
  • Vote: I like it  
  • +8
  • Vote: I do not like it  

By OmaeWaMouShenDeiru, history, 4 years ago, In English,

Hello,

This is an interesting data structure problem.

It can't be solved with regular insertion and print.

Who do you think it can be solved ??

Read more »

 
 
 
 
  • Vote: I like it  
  • -3
  • Vote: I do not like it  

By OmaeWaMouShenDeiru, history, 4 years ago, In English,

Hello,

As I was trying to solve ZigZag problem on topcoder the weirdest thing happend.

#include <bits/stdc++.h>
using namespace std;
class ZigZag {
public:
	int longestZigZag(vector<int> arr) {
		int dp[55], state[55];
		memset(dp, 1, sizeof dp);
		cout << dp[0] << endl;
		memset(state, 0, sizeof state);
		for (int i = 0; i < arr.size(); ++i) {
			for (int j = 0; j < i; ++j) {
				if ((j == 0 || (arr[i] - arr[j] < 0 && state[j] > 0)
						|| (arr[i] - arr[j] > 0 && state[j] < 0))
						&& dp[j] + 1 > dp[i])
					dp[i] = dp[j] + 1, state[i] = arr[i] - arr[j];
			}
		}
		return dp[arr.size() - 1];
	}
};

as I ran the given code, the cout statement gives 16843009.

I removed it and initialized every element int the first loop and it worked.

Read more »

 
 
 
 
  • Vote: I like it  
  • -8
  • Vote: I do not like it  

By OmaeWaMouShenDeiru, history, 4 years ago, In English,

for this problem on spoj, Im getting WA and I don't know why !!

This is my code

Any hints ??

Read more »

 
 
 
 

By OmaeWaMouShenDeiru, 4 years ago, In English,

Hello,

In this blog, I would like to ask for your training experiences.

The ACM local contest will be in three month, and the regional contest is in December, and I believe I still have enough time to improve my skills.

I'm fast in reading problem statements and coding whenever I understand the problem completely. I know basics of graph theory problems, number theory, dynamic programming, and working on improving my data structure skills.

But whenever I participate in a codeforces contest, I feel there is a lot of skills I'm missing.

So it would be very kind of you to share or provide a good training schedule for the amount of time left before the coming contests.

Read more »

 
 
 
 
  • Vote: I like it  
  • +7
  • Vote: I do not like it  

By OmaeWaMouShenDeiru, 4 years ago, In English,

hello,

for this problem, all I could come up with is to find all divisors of 'b' that are less than or equal to 't' using O(sqrt(n)) but It will get TLE for such input limits " < (1<<54)".

any hints for a better aproach ?

thanks :D

Read more »

 
 
 
 
  • Vote: I like it  
  • -2
  • Vote: I do not like it  

By OmaeWaMouShenDeiru, 4 years ago, In English,

hey guys :D

I have this small math problem,

( a * b ) mod n = 1

Given a, n:

find the smallest value of 'b' that satisfies the equation above.

any Idea about how to find the answer better than linear time search.

Read more »

 
 
 
 
  • Vote: I like it  
  • -3
  • Vote: I do not like it  

By OmaeWaMouShenDeiru, 4 years ago, In English,

Hey you guy's :D

Im wondering, given a number as input, what is the best way to find the smallest palindromic prime number greater than the given number.

Assume the answer fits in long long int as in c++

Read more »

 
 
 
 
  • Vote: I like it  
  • -1
  • Vote: I do not like it  

By OmaeWaMouShenDeiru, 4 years ago, In English,

Hello,

I went through some problems that needs hashing or can be efficiently solved using hashing.

But it is still hard to understand this topic.

can any one please provide a tutorial link for me.

Thanks :D

Read more »

 
 
 
 

By OmaeWaMouShenDeiru, 4 years ago, In English,

I'm trying to solve this problem

My algorithm is, after reading the graph, I run SPFA function from every node and calculate the shortest path from it to every other node, my state is the current node and the number of edges and the value of previous edge, then copy the result -which is stored in 2D array cost- in the array dp[x];

at the query part, i just read source and destination and maximum number of edges, the go from 0 to maximum possible number of edges and get the result.

this code gets WA on the judge but I think it can pass the time limit.

This is my code.//Removed

Any help ??

Edit: I changed the code into Dijkstra and Got AC, code.// Removed

But I still don't know why the first code is Wrong!!

Edit_2: Solved :D, it turns out that my SPFA code didn't handle multiple edges quite will.

Read more »

 
 
 
 
  • Vote: I like it  
  • +8
  • Vote: I do not like it  

By OmaeWaMouShenDeiru, 4 years ago, In English,

Hello ,

I tried to solve this problem using subset sum algorithm and precalculation for all numbers which satisfy the given condition, But i got alot of TLE.

is there any fast subset sum algorithm better than O(n^2) ??

This is the problem :http://www.ahmed-aly.com/p.jsp?ID=172

And this is my code : Edit after AC :D

Thanks

Read more »

 
 
 
 
  • Vote: I like it  
  • -2
  • Vote: I do not like it  

By OmaeWaMouShenDeiru, 4 years ago, In English,

For this problem on spoj: http://www.spoj.com/problems/ODDDIV/

Code Removed After AC :D

I went through the following steps to solve it: 1_ generate all primes to sqrt(1^10) to use them in prime factorization

2_ pre calculate number of divisors for numbers in range (1 — 100000)

3_ answer each query in O(n) time, I found that only perfect square numbers have odd number of divisors, so I only need to check if(fact_num[i] == k)from x to sqrt(y)

Any help to improve my time ??

Read more »

 
 
 
 

By OmaeWaMouShenDeiru, 5 years ago, In English,

Any ideas of how to solve this problem ??

http://uva.onlinejudge.org/external/100/10085.html

Read more »

 
 
 
 

By OmaeWaMouShenDeiru, 5 years ago, In English,

Hello, I would like ask to how is new rating calculated after each round ??

Read more »

 
 
 
 
  • Vote: I like it  
  • -4
  • Vote: I do not like it  

By OmaeWaMouShenDeiru, 5 years ago, In English,

Hello codeforces community I wanna learn how to use Fread Fwrite for faster I/O.

If you have any useful example, I will be thankful :D.

Read more »

 
 
 
 
  • Vote: I like it  
  • +3
  • Vote: I do not like it  

By OmaeWaMouShenDeiru, 5 years ago, In English,

Hello programmers,,

I read someones code a couple days earlier and i saw a piece of code using __typeof operator as a shortcut of a for loop. What is this operator and can it be used ?? Thanks :D

Read more »

 
 
 
 
  • Vote: I like it  
  • +1
  • Vote: I do not like it