Editorial for Equation, Modulo Equality, Long Beautiful Integer

Problem Discussed Today: 
  1. Equation ( 1269A )
  2. Modulo Equality ( 1269B )
  3. Long Beautiful Integer (1269C)
Editorial

This is a simple question, from the Codeforces editorial answer is 9n & 8n. Initially, I was not aware of this so I have tried the brute force as the value on n<=10^7 which will pass all the test cases in a given time limit.

I have taken b=1 and a=b+n and increment both a and b until both a and b are composite.
The complexity of this solution is O(n).

Solution Link: Solution



This is also a simple question as n<=2000 so we can go for a solution running in quadratic time complexity. So for this, I have sorted array b.

Now how should we choose x? Anyway, the x can take only the value from the (b[i]-a[i])%m as (a[i]+x)%m = b[i].
so for this, I have found all the difference (b[i]-a[0])%m as anyone value which we will get here must satisfy all other. I.e. for anyone x, (a[i]+x)%m will be equal to b[i]. For Comparision purpose I am using sort as this will make our comparison simple. 

Sorting can be done in O(nlogn) time complexity. This should be done for all x, which at max can be n distinct number. So the total running time complexity of this solution is O(n^2logn). Which will pass in given time limit?

Solution Link: Solution



This is a little bit tricky problem, for which I have struggled a lot.
The problem simply says that find the number greater or equal to the given number X, such that a[i]=a[i+k].

So for this, the pattern should repeat, like if we that this example,
8 2
12345678

13131313 ( is the solution in which pattern is repeating )

So for this what we do, we take first k string and repeat it to get a string of size n, like here we will get 12121212 now check whether this is greater than or equal to given X if it is then done. Else get the last non-nine element in a string of size k from the beginning and increase it by 1 and all the 9 coming after that to be 0.
And using this string generate a pattern string of size n which we will get 13131313.

Solution Link: Solution

That's all for this editorial. If you have any new approach or any query then we would like to discuss it with you for which we can use either comment section or slack.

Thank You

Comments

  1. nice approach for first problem,I couldn't get the idea.

    ReplyDelete

Post a Comment