remidinishanth's blog

By remidinishanth, history, 4 weeks ago, In English,

Hello,

I have a clear idea of implementing Suffix Links and I know how to build suffix links efficiently. I'm stuck with Output links, that is how to print the matched strings?

Suppose we have patterns:

i & in & tin & sting and the given string is sting

We miss both tin and in because each is a proper suffix of stin (Because suffix link of stin goes to n in tin and suffix link of n in tin goes to n in in).

How do we address this?

Could someone share Implementation details of Aho-corasick automata?

Thanking you in Advance.

Read more »

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

By remidinishanth, history, 6 weeks ago, In English,

Hello,

Can someone explain the logic [and formal proof why this logic works] to solve this problem?

https://csacademy.com/contest/round-64/task/limited-moves/

Consider a heap of N objects. Two players take turns playing the following game:

At his very first move, the first player removes from the heap between 1 and N-1 objects After that, at each step the player to move can remove any number of objects between 1 and the number of objects removed by the other player at the previous move When the heap becomes empty, the player to move loses the game.

[UPD.]

I know that removing the number of objects from Last on bit works. The Last on-bit, I mean the below.

int k=0;
while( n % (1<<(k+1)) == 0)
            k++;
printf("%d",(1<<k));
fflush(stdout);
n -= (1<<k);

I need a formal proof/Argument that why is this working. Or why this is guaranteed to work?

Thank you.

Read more »

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

By remidinishanth, history, 7 weeks ago, In English,

Reading Integers until End of file:

int a[110];
for(i = 0; scanf("%d", &a[i])!=EOF; i++);

Because scanf will return the total number of input successfully scanned.

Reading date

int day, month, year;
scanf("%d/%d/%d", &month, &day, &year);

Helps when input is of format

01/29/64

Read Binary string

char str[20];
scanf("%[01]s", str);
printf("%s\n", str);

%[01]s – Read only if you see 0’s and 1’s. Shorthand for matching characters in the seq [01] can also be extended for decimals using %[0-9]s. Similarly, %[abc]s – Read only if you see a, b, c. [...] read till these characters are found. [^...] read until these characters are not found.

char s[110];
scanf(“%[^\n]s”, s);

Here,we have [^\n]. The not operator (^) is used on the character \n, causes scanf to read everything but the character \n – which is automatically added when you press return after entering input.

Read but donot store. (use * assignment suppression character)

scanf("%d %*s %d", &a, &b);

The above segment can be used to read date format and do not store the month if the format is dd month yyyy (06 Jan 2018).Read the desired input, but do not store.

To read char

char c;
scanf("%*[ \t\n]%c",&c);
scanf(“%2d”, &x);

In this example we have, a number located between the % and d which in this case is 2. The number determines the number of integers our variable input (of integer type) will read. So if the input was “3222”, our variable would only read “32”.

End of File

while (scanf() != EOF){
   //do something
}

Example from CP1

Take this problem with a non-standard input format: the first line of input is an integer N. This is followed by N lines, each starting with the character ‘0’, followed by a dot ‘.’, then followed by an unknown number of digits (up to 100 digits), and finally terminated with three dots ‘...’.

Input:-

 3
 0.1227...
 0.517611738...
 0.7341231223444344389923899277...

One possible solution is as follows.

#include <cstdio>
using namespace std;

int N;         // using global variables in contests can be a good strategy
char x[110];  // make it a habit to set array size a bit larger than needed

int main() {
  scanf("%d\n", &N);
  while (N--) {                  // we simply loop from N, N-1, N-2, ..., 0
    scanf("0.%[0-9]...\n", &x);   // `&' is optional when x is a char array
                         // note: if you are surprised with the trick above,
                      // please check scanf details in www.cppreference.com
    printf("the digits are 0.%s\n", x);
} } // return 0;

Please feel free to add more in comments. Thank you for reading. Learn and let learn.

[UPD]

Scanf with search sets

We used hyphen in format string: dd-mm-yyyy

If we want more than one option: hyphen or slash: - or / then use search set %[-/]

Store the search string in a character variable

#include <stdio.h>
void main()
{
    int date, month, year;
    char separator[2];
    printf("Input the date:");
    scanf("%d%[-/]%d%[-/]%d", &date, separator, &month, separator,&year);
    printf("Date: %d\n", date);
    printf("Month: %d\n", month);
    printf("Year: %d\n", year);
}

Examples

Input the date:31-12-2013
Date: 31
Month: 12
Year: 2013
*** another input ***
Input the date:14/1/2014
Date: 14
Month: 1
Year: 2014
*** another input ***
Input the date:26/2-2014
Date: 26
Month: 2
Year: 2014

The more simplified version using the above-mentioned assignment suppression operator.

scanf("%d%*[-/]%d%*[-/]%d", &date, &month, &year);

More Info:

That the terminal is line-buffered means that it submits input to the program when a newline character is encountered. It is usually more efficient to submit blocks of data instead of one character at a time. It also offers the user a chance to edit the line before pressing enter.

Thanks

UPD 2

stringstream

You are given a String Rectangle consists of four integers separated by single spaces, with no additional spaces in the string. The first two integers are the window coordinates of the top left pixel in the given rectangle, and the last two integers are the window coordinates of its bottom right pixel.

     string rectangle;
     cin>>rectangle;
     istringstream ss(rectangle); 
     int x1,y1,x2,y2; 
     ss >> y1 >> x1 >> y2 >> x2;

Thank you

Read more »

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

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

Given an array of N integers, you are given two types of queries:-

Type 1 ::: x y

Append y after index x (array size increases by 1 after every type 1 operation )

Type 2 ::: print

Print the array

What is the efficient way to solve this problem?

Type 2 query takes O(n) time.

So the problem can be solved in O(n^2).

If we are given information that there are many many operations of Type 1 than Type 2 can we reduce the complexity?

For example, if we are given that Type 2 operations are <= sqrt(N) or so?

Thanking you.

UPD: Suppose if the query is like find the maximum in [l,r] range etc

Read more »

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

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

I am posting this just for beginners like me so that we can use such tricks in future and as both the problems are almost similar I just posted them together not to get confused in case.

Q1.

You are given an array of N integers. Suppose you are allowed to change an element into any integer with one operation. Find the minimum number of operations to make the array strictly increasing. (Note that the elements can become <1). The given array contains N positive integers.

  • 1 ≤ N ≤ 10^5
  • 1 ≤ ai ≤ 10^9 for 1 <= i <= N

Example:

1) N = 5
1 2 2 3 6
Sol: 1 2 3 5 6. So the answer is 2

2) N = 3
1 1 1
Sol: −1 1 2. So the answer is 2

3) N = 6
4 2 4 4 6 8
Sol: 1 2 4 5 6 8. So the answer is 2

4) N = 7
1 2 2 2 3 4 5
Sol: -1 0 1 2 3 4 5. So the answer is 3.

Here is how we can solve this problem:

Suppose the problem was simply named Non-decreasing Array. Obviously, you want to keep as many numbers as possible unchanged. It follows that you can select the longest non-decreasing subsequence and modify all the other elements so that they'll respect the rule (by making them equal to values from the subsequence we've extracted accordingly). Back to our problem now, we're looking for a Strictly Increasing Array. If we make another ci = ai - i, the answer is the equal to (n - the longest of the non-decreasing subsequence with no negative number) and for the longest non-decreasing subsequence, a O(nlogn) solution can be used.

Why does this work?

Consider for some i and j, ci <= cj then ai - i <= aj - j that implies ai + j - i <= aj , which means we have enough space to fit a strictly increasing array between i and j.

Q2.

Now consider the same problem but with the condition that the resulting sequence should only contain positive integers.

Here is how we can solve this problem:

For each element of the modified(or resulting) sequence we have bi >= i (1<=i<=n) and we need to find the longest increasing subsequence of the original sequence ai and ai >= i. We keep such ai unchanged and other values can be changed into the value as their index.

Then we should modify the above solution such that we have to consider longest non-decreasing subsequence only among those numbers such that ai - i >=0 but not the whole array ci. This ensures that the resulting array has the integers which are positive and forms strictly increasing sequence. Because in this way we make sure that all the elements such that ai < i initially have to be changed.

Another way is to modify the algorithm to only use positive numbers is to append a whole lot of numbers at the start of the array .i.e. change 1,2,9,10,3,15 to -5,-4,-3,-2,-1,1,2,9,10,3,15. Then you can be sure that the optimal answer will never decide to make the 1 go negative because it would cost so much to make all the negative numbers smaller. You only need to add N dummy nodes (the same as the length of the sequence, not the maximum number i.e 10^9 ).

Example:

Original sequence 1,2,2,2,3,4,5
Add dummy elements at start -5,-4,-3,-2,-1,1,2,2,2,3,4,5
Subtract off position in array -5,-5,-5,-5,-5,-4,-4,-5,-6,-6,-6,-6
Find longest non-decreasing sequence -5,-5,-5,-5,-5,-4,-4,*,*,*,*,*
So answer is to change 5 numbers. 1 2 3 4 5 6 7

[REF.]

https://www.codechef.com/SMHT2014/problems/SMHTD
https://www.hackerearth.com/problem/algorithm/find-path/ &
https://csacademy.com/contest/round-61/task/strictly-increasing-array/

Read more »

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

By remidinishanth, history, 5 months ago, In English,

How does this work?

  • llui mul_mod(llui a, llui b, llui m){
  • llui y = (llui)((float64)a*(float64)b/m+(float64)1/2);
  • y = y * m;
  • llui x = a * b;
  • llui r = x-y;
  • if ( (lli)r < 0 ){
  • r = r + m; y = y-1;
  • }
  • return r;
  • }

For example if we do c = (a+b)%m;

What if a+b itself causes the overflow that is a+b is larger than the size of typeof a or b.

Doesn’t x in the above code cause overflow that is a*b is larger than a size of llui.

Here llui means long long unsigned int and lli means long long int and float64 stands for long double

Read more »

 
 
 
 

By remidinishanth, history, 11 months ago, In English,

UVa 11173 — Grey Codes with a one-liner bit manipulation expression for each test case, i.e. find the k-th Gray code.

Solution is k^(k>>1)

Let’s reverse the UVa 11173 problem above. Given a gray code, find its position k using bit manipulation.

Solution: ????

Read more »

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