sourabh_jangid's blog

By sourabh_jangid, history, 4 years ago, In English

You are given three numbers as input $$$A$$$, $$$B$$$, $$$K$$$.
Perform the given below steps K times:-
if $$$A$$$ <= $$$B$$$ then
$$$B$$$ = $$$B$$$ $$$-$$$ $$$A$$$
$$$A$$$ = $$$A$$$ $$$+$$$ $$$A$$$
else
$$$A$$$ = $$$A$$$ $$$-$$$ $$$B$$$
$$$B$$$ = $$$B$$$ $$$+$$$ $$$B$$$

After K steps output the values of $$$A$$$ and $$$B$$$.
$$$0$$$ $$$\leq$$$ $$$A$$$, $$$B$$$ $$$\leq$$$ $$$10 ^ {9}$$$
$$$1$$$ $$$\leq$$$ $$$K$$$ $$$\leq$$$ $$$10 ^ {10}$$$.
If someone can give some hints it will be helpful.

Full text and comments »

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

By sourabh_jangid, history, 4 years ago, In English

I encountered this problem in a contest, I was not able to solve it during the contest.
The problem is as follows:-
You are given an array $$$A$$$ where $$$A[i]$$$ is either $$$0$$$ or $$$1$$$ for $$$\forall$$$ $$$i$$$ $$$\leq$$$ $$$n$$$ $$$and$$$ $$$i$$$ $$$\geq$$$ $$$1$$$.
There is an array $$$P$$$ defined as follows:-
If $$$A[i] = 0$$$ then $$$,$$$ $$$P[i] = 0$$$.
If $$$A[i] = 1$$$ then $$$,$$$ $$$P[i] = A[i] + P[i - 1]$$$ $$$,$$$ for $$$\forall$$$ $$$i$$$ $$$\leq$$$ $$$n$$$ $$$and$$$ $$$i$$$ $$$\geq$$$ $$$1$$$.
Now you are given Q queries of two types:-
$$$1$$$ $$$L$$$ $$$R$$$ $$$,$$$ Invert the array $$$A$$$ from $$$L$$$ to $$$R$$$ i.e $$$($$$ If $$$A[i] = 1$$$, then make $$$A[i] = 0$$$ and vice versa $$$)$$$.
$$$2$$$ $$$L$$$ $$$R$$$ $$$,$$$ Output the sum of the array $$$P$$$ from index $$$L$$$ to $$$R$$$.
Note in the query of type 1, the array $$$P$$$ will also change accordingly. And assume $$$P[0] = 0$$$.
$$$1$$$ $$$\leq$$$ $$$N, Q$$$ $$$\leq$$$ $$$200000$$$
It will be helpful if someone can give some ideas.

Full text and comments »

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

By sourabh_jangid, history, 5 years ago, In English

I was solving 691E - Xor-последовательности, and in the problem asked to find number of ones in binary representation of a number, I was using C++ STL __builtin_popcount() function to find Number of ones, but when I submitted I got wrong answer verdict, and then I wrote my own function to count Number of ones and then my solution passed. Can anyone explain to me why this is happening? My AC 69283580 code and WA 69283537 code.

Full text and comments »

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

By sourabh_jangid, history, 5 years ago, In English

I am trying to solve 611D - New Year and Ancient Prophecy, I wrote 60357814 this solution. I think the Time Complexity of my solution is $$$O(n ^ 2\log{}n)$$$ but I am getting Time Limit Exceeded verdict. I want to know is my Time Complexity analysis is wrong because I saw many $$$O(n ^ 2\log{}n)$$$ solutions are accepted(like 15127310) but not mine.

Full text and comments »

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

By sourabh_jangid, history, 5 years ago, In English

I was trying to solve this problem (56E - Domino Principle). I am stuck on Test Case 30.(Link to my submission 58845497). I tried for hours but not been able to find my mistake. My algorithm is same as the editorial given, but it is giving wrong answer verdict on test case 30. Please help me in debugging the code, and also share some debugging technique, what you use during a contest.

Full text and comments »

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