Naim_Hasan's blog

By Naim_Hasan, 2 months ago, In English,

https://toph.co/arena?contest=mirror-nstu-ice-fest-regional-2020#!/p/beauty-factor

Above problem has almost same pattern as problem described below.

You are given an Array of integer numbers. You have to answer Q query.

For each query you will be given 3 integer- L, R, K; [ 1'based indexing ]

The answer is if you sort the Array elements from index L to R, then what will be the sum of first K element of the Array? { You can't sort the range [L , R] permanently ] }.

Example:

Array = { 8, 7, 6, 5, 4, 3, 2, 1 };

Lets answer 2 query.

Query 1: 5 8 3 Answer : 21 [ Because K < L, so sorting didn't affect our answer ]

Query 2: 5 8 6 Answer : 27 [ If we perform sort, then first 6 elements will be 8 7 6 5 1, so ans is 27 ]

{ I just learned Merge_Sort_Tree data structure and this problem came to mind. Type_1 query can be answered with prefix_sum algorithm. But how to handle Type_2 query? }

Read more »

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

By Naim_Hasan, 4 months ago, In English,

I have an array of strings.

I have to sort them in descending order. If 2 string have same length then we don't change their order.

So i wrote this code [Function in line 13 do the works mentioned above]

But for this given case below

17

sj a sa df r e w f d s a v c x z sd fd

Output: fd sa df sd sj d z x c v a s f w e r a

Right Output: sj sa df sd fd a r e w f d s a v c x z

[Problem is causing when 2 string have same length. Then those are automatically sorted lexicographic way. How to prevent it?]

[If i replace return a.length() > b.length();

in line 15 with return a.length() >= b.length();

then the code is crashed]

Read more »

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

By Naim_Hasan, 10 months ago, In English,

At first thanks to Arpa who has written a very clean and fast library for handling big size number in C++. With it, i added sqrt and pow function. Also overloaded post++, post-- operator. And instead of writing "bigint", we wrote "Int" so that it become easy to write and understand.

The modified code now can handle all these operation given below:

+, -, *, /, %, =, >, < ; +=, -=, *=, /=, %=, ==, !=, >=, <= ; ++pre, post++, --pre, post-- ; pow(a,b), sqrt(a), max(a,b), min(a,b) ; [ Here a is Int type and b is Int or other integer type ]

Here is the latest code.

https://github.com/NaimHasanPappu/Algorithm/blob/master/BigInteger.cpp

To check if the library is working smoothly, try This Problem

Read more »

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