inception_95's blog

By inception_95, history, 6 years ago, In English

One of the main problem of solving 'ACM ICPC Live Archive' problems is that if you get stuck, you have no editorials. So I came here seeking for help.

Problem

Anyone have any hints or solution ideas of this problem or the topics I may need to know?

Full text and comments »

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

By inception_95, history, 6 years ago, In English

Efficient and easy segment trees

So I was reading this blog and tried to modify the "Increment modifications, queries for maximum" for sum queries, but the query function isn't working. Here is my implementation :

Code

What's the problem? How can I fix it?

Full text and comments »

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

By inception_95, history, 6 years ago, In English

After watching this video Algorithms Live! Episode 3 — Rolling Hashes and Bloom Filters, I tried to implement pull character from last by myself and applying it on this problem here:

Problem: 1423. String Tale

Code : My code

Is my implementation wrong? if so, what is wrong in this? or can anyone give a code that works like the same principle as the video and works perfectly?

Thanks in advance.

Full text and comments »

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

By inception_95, history, 6 years ago, In English

The idea of the problem is to take all the queries at first, insert the strings and store the id(s) in the trie. Then when searching for the strings we look at the id and if it is less than the id of that query, that means it has been inserted before this query and so the output is "YES" or else "NO".

Can you show me where the problem is? Useful testcases will also be appreciated.

Thanks in advance.

Problem link: ADAJOBS — Ada and Jobs

Code: Solution Code

Full text and comments »

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

By inception_95, history, 6 years ago, In English

Can anyone give some problem links where the concept of 'Center of a tree' is needed?

Full text and comments »

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

By inception_95, history, 7 years ago, In English

There is an array of n numbers and after m number of steps, one needs to answer the query. In every step from 1 to m, we calculate the cumulative sum. Then queries are asked, which index contains which number in the array.

For example, if n = 5, m = 3, the array = 2,4,3,9,1

we conduct the m steps.

[2,6,9,18,19]

[2,8,15,33,52]

[2,10,25,58,110]

If the query is 2, the answer will be 25.

Constraints: 1<=n,m<=10^5

How can I solve this problem?

N.B: It just came to my mind. I didn't find any such problem in any OJ. If you can, please provide the link. And sorry for bad english.

Full text and comments »

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

By inception_95, history, 7 years ago, In English

Edit: AC

In this problem, one needs to compute Minimum spanning tree w query times! As running MST on the full graph every time will surely lead to TLE, my idea is to only work with the MST I get after each query! But it's unexpected for me to get MLE! I've just taken two adjacency list for only 205 nodes and simple a 205 size array. How can it lead to MLE? Plz help!

The full problem description can be found here: 1123 — Trail Maintenance

My Code

Thanks in Advance

Full text and comments »

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

By inception_95, history, 7 years ago, In English

In what cases are Bi-Directional BFS useful? I've solved some problems but haven't found such cases where this bi-directional bfs solution is obvious! Can someone please explain how I can understand where to use bi-directional bfs or not and specially what problems it actually deals with?

Thanks_in_Advance! :)

Full text and comments »

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

By inception_95, 7 years ago, In English

Understanding something in one's mother language is always easy and long lasting. For that cause, I've started writing a contest blog for programmers in Bengali. Here's the link:

https://returnzerooo.wordpress.com/

I hope it will help all Bangladeshi Programmers and those who know Bengali. Useful suggestions will be highly appreciated!

Edit:

To get updated about the new blog posts you can follow this facebook page: https://www.facebook.com/returnzerooo/?fref=ts

Full text and comments »

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