mahmoud_arafa's blog

By mahmoud_arafa, history, 2 months ago, In English,

During official programming contests, we (our team) used to use printed references (codes) for algorithms during the contest. When I had my first coding test for a job interview, the rules are different; we can't use references/copy codes.

So I asked a friend about this; what are the algorithms allowed to look on during a coding test. He told me that advanced algorithms like Maximum Flow are allowed to look on during a coding test, yet ones like BFS, DFS and Dijkstra are supposed to be known without being looked on during the test.

But for online contests, aren't we allowed to look on BFS, DFS, ... etc during the contest? Do things are same for coding test?

That's something I need to discuss with others.

Read more »

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

By mahmoud_arafa, 3 years ago, In English,

Hello,

I tried to solve this problem using memoization (top-down DP) but the complexity of my code is too damn high!

Here is my code.

Can anyone help me solve this problem using memoization?

Read more »

Tags dp, math
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Hello,

Can anyone help me with a tutorial for this problem?

I had an idea using binary search. We can sort the array, then each time we look for the next nearest point using binary search. After that we remove that point from the points list and then we look for the next nearest point and so on. But the drawback is the 'erase' step, which takes O(N) complexity. That changes overall complexity from O(N log N) to O(N * [log N + N]) which is O(N^2).

So any help here please?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Hi, I hope this blog entry finds you well and you are doing fine,

I was wondering if somebody can share with us a simple tutorial for the problem above. There doesn't exist a tutorial for this round.

Read more »

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

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

Hello,

Here is the problem link.

Here is my submission.

I am applying lazy propagation but I don't know why I got TLE. Any help?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By mahmoud_arafa, 5 years ago, In English,

Hello everyone.

Here is the problem link.

Here is my code link.

BFS works right but my idea takes too long time to process. I tried to optimize it as much as possible but I couldn't optimize anymore. Any help?

Read more »

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

By mahmoud_arafa, 5 years ago, In English,

Hello. I'm getting WA for this problem.

Here is the problem link.

Here is my code link.

Can anyone help me with a test case?

Read more »

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

By mahmoud_arafa, 5 years ago, In English,

Hi,

I have just watched a tutorial about "Bits". I need to solve some easy problems so I can increase my understanding for bits. I've noticed that many CF rounds involve bits problems, and I couldn't solve a single one during the rounds.

If you know some problem(s), please comment with them. Also, if I need to revise some topics, please comment with them too.

Thanks in advance.

Read more »

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

By mahmoud_arafa, 5 years ago, In English,

Hi.

I was trying to solve this problem. Here is the problem link.

If n = 4, k = 0, the apples are of weight 1, 2, 3, 4.

If he eats apple #1:

If apple #1 is sweet, then he must eat apples of total weight 1.

If apple #2 is sweet, then the total weight is 3.

If apple #3 is sweet, then the total weight is 6.

If apple #4 is the sweet one, then he must must eat apples of total weight 6 also.(because he will know the answer regardless of the taste of apple #3)

Then we have total answer of: 1 + 3 + 6 + 6 = 16.

Why the answer in this case is equal to 13?

Thanks in advance.

Read more »

Tags dp
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By mahmoud_arafa, 5 years ago, In English,

Hi.

I'm looking for DP problems that involve printing the items that give the optimal answer(involves reconstructing the optimal items), like printing the Knapsack items for example.

If you know any similar problems, please comment with them.

Thanks in advance.

Read more »

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

By mahmoud_arafa, 5 years ago, In English,
Tags dp
 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

By mahmoud_arafa, 5 years ago, In English,

Hi,

I got WA for this problem. I hope that you can help me.

Problem Link: http://www.spoj.com/problems/FP/

My idea is sorting the numbers in non-increasing order, then applying (0/1) logic, either I take the element, or I leave it.

My code: http://ideone.com/wJaQoR

Read more »

Tags dp
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it