### mahmoud_arafa's blog

By mahmoud_arafa, history, 2 months ago, ,

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.

• +5

By mahmoud_arafa, 3 years ago, ,

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?

• 0

By mahmoud_arafa, history, 3 years ago, ,

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).

• 0

By mahmoud_arafa, history, 3 years ago, ,

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.

• +2

By mahmoud_arafa, history, 4 years ago, ,

Hello,

Here is my submission.

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

• 0

By mahmoud_arafa, 5 years ago, ,

Hello everyone.

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?

• -1

By mahmoud_arafa, 5 years ago, ,

Hello. I'm getting WA for this problem.

Can anyone help me with a test case?

• -6

By mahmoud_arafa, 5 years ago, ,

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.

• +8

By mahmoud_arafa, 5 years ago, ,

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?

• 0

By mahmoud_arafa, 5 years ago, ,

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.

• +4

By mahmoud_arafa, 5 years ago, ,

• -3

By mahmoud_arafa, 5 years ago, ,

Hi,

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