MrPaul_TUser's blog

By MrPaul_TUser, history, 2 months ago, In English

Ideas: MikeMirzayanov

1560A - Dislike of Threes

Tutorial
Solution

1560B - Who's Opposite?

Tutorial
Solution

1560C - Infinity Table

Tutorial
Solution

1560D - Make a Power of Two

Tutorial
Solution

1560E - Polycarp and String Transformation

Tutorial
Solution

1560F1 - Nearest Beautiful Number (easy version)

Tutorial
Solution

1560F2 - Nearest Beautiful Number (hard version)

Tutorial
Short solution
Long solution
 
 
 
 
  • Vote: I like it
  • +73
  • Vote: I do not like it

»
2 months ago, # |
Rev. 5   Vote: I like it -8 Vote: I do not like it

Very Good Round with Balanced Problemsets! Problem C was very interesting to me. Thanks!

»
2 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Great problemset and quick editorial.

»
2 months ago, # |
  Vote: I like it +42 Vote: I do not like it

Thank you for the round! Problems were interesting and of the right difficulty for a Div. 3.

For problem F1, there's a simpler solution:

Simply generate all beautiful numbers for $$$k = 2$$$, my program counts about $$$80,000$$$. Link

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Can you please explain what i,j,k,l,m denote in your code?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i and j are the two digits that are in the number. k is the number of digits in the number. I use l as a bitmask to determine which digits are i and which are j. Then I loop over the digits of the bitmask with m and construct the new number, which I insert into the set. I don't let i == j by setting j = i + 1 since that is already covered when the bitmask is all 0 or 1.

»
2 months ago, # |
  Vote: I like it -30 Vote: I do not like it

Prob C was very interesting ngl.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it -35 Vote: I do not like it

    Completely agree ! Pre-computing all powers of 2 upto 10^18

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    One great observation was that the leading row in the table was forming an arithmetic progression with common difference of 2.Great problem

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 3   Vote: I like it +1 Vote: I do not like it

      Well, not the row elements, but the differences between consecutive elements form an arithmetic progression with a common difference of 2. This is because $$$\sum\limits_{i=0}^{k}2k+1 = k^2$$$ and every element in first row will obviously be $$$k^2 + 1$$$ and numbers $$$2k+1$$$ form an arithmetic progression with a common difference of 2.
      Using this, we can also solve it in less than $$$\mathcal O(\sqrt k)$$$. The time complexity will depend on how you calculate the square root.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Great approach can you please give me this particular solution....if you don't mind pls

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Pardon the late response. Here's the pseudocode.

          n = floor(sqrt(k))
          d = k - n * n
          if d = 0:
              return (n, 1)
          else if (d <= n + 1):
              return (d, n + 1)
          else
              return (n + 1, (n + 1 - (d - (n + 1)))
          

          This works in $$$\mathcal O(1)$$$ once you calculate square root.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    gives me old spoj problems vibe.

»
2 months ago, # |
Rev. 2   Vote: I like it +22 Vote: I do not like it

I liked all problems. For F I made a dp with bitmasks (normal dp on digits), you could've set the constraints to disallow this solution, because it was pretty brainless (no cases to think about, just "brute-force")

O(T * 2^LEN * LEN), where LEN is the number of digits of N.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    But don't you think this thing is above Div3 level for like 98% official particpants of Div3?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +25 Vote: I do not like it

      idk I never went to Div3 before, thinking carefully about many cases can be harder and more tricky.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it -19 Vote: I do not like it

        yeah, that's your tunnel vision right there.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    I implemented a similar solution (126326225) with complexity O(LEN * 1024) per test case. However, I feel considering a Div. 3 round, it wouldn't be brainless for official participants to think of a Digit DP there. However, what could have been changed was that instead of bombarding with 10^4 test cases, the length of the number could have been increased to let's say N <= 10^1000.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Could you elaborate on how the recurrence of the dp worked?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Isn't it O(T*2^LEN)?

    EDIT: No, there is popcount in every recursion

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can avoid popcount by having a 4th argument (which you don't need to use for memoization). So, ll dp[1<<10][10][2] but the function ll solve(int mask, int pos, bool flag, int popcount) { ... } . But this does not change the complexity

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did the same solution and it got hacked. Did yours pass?

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it +5 Vote: I do not like it

    linkret I see no do major difference in our approach ( sorry , if there is) Can you tell why mine is TLE ? Here is my submission 126427896

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think it's better to always count the bits, and immediately return INF if there are too many, instead of just doing it in the end.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hey [user:linkert] even after that , for clearing the array the whole complexity is (10^4 * 2^10 * 10 * 2) . Shouldn't it be TLE ?

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          2*10^8 is fast enough for Codeforces, even 10^9 is, too. My solution is about 100ms.

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it +6 Vote: I do not like it

            Counting bits worked and AC

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Hey , can you explain the approach a bit too?

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it +4 Vote: I do not like it

      DP (memoized recursion). Use a bitmask to remember which digits from 0 to 9 have already been used. The number of 1s in this bitmask will tell you the number of different digits you had used: it must not exceed K.

      In the DP, try out every possible digit for the current position, and move to the next position, adding it to the bitmask.

      Also you will need to keep track of a 3rd state, weather the number you are currently building (from left to right) is already larger than the target number N, or not. Whenever you choose a digit larger than the corresponding digit of N, from then on you will always be larger and those dp states are allowed to choose any digits. But if you are not already larger than N, then it is not allowed to choose the current digit that is LESS than the corresponding digit of N. And if you choose the same digit, then the next recursion call still has to be careful (since it is not yet larger). You can google "digit dp" to get a better explanation about this part.

»
2 months ago, # |
Rev. 2   Vote: I like it +22 Vote: I do not like it

Just curious, how did you come up with problem E? What motivated this particular string construction?

It was a nice problem :)

»
2 months ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it
A clean solution for C
»
2 months ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

I'm not pretty good at math, so I solved C using binary search.

I noticed that the last number of the $$$i_{th}$$$ row is $$$i^2$$$, so I do a binary search to find the row which $$$n$$$ belongs to. Then the starting number of the new column is $$$i^2 + 1$$$ (let's call this $$$start$$$), thus the number $$$corner$$$ at the position $$$(i + 1, i + 1)$$$ is $$$start + i$$$.

I finally check whether $$$n$$$ exceeds $$$corner$$$ or not, if it does then the answer is $$$(i + 1, i + corner + 1 - n)$$$, else the answer is $$$(n - start + 1, i + 1)$$$

Here's my submission

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    pretty smart vision :)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved using the same approach!

    Also, binary search was not necessary for finding the nearest square since the constraints allowed a linear search algorithm. :)

»
2 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Why does the short solution in F2 work in m^2 ? Couldn't figure it out:(

Btw problems are pretty good!!

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Suppose n = 789152352 and k = 3. Then the algorithm takes you to:

    789200000

    789300000

    789400000

    789500000

    789600000

    789700000

    Now this is a special point in the algorithm. The fourth character of the number is now among the 3 previously used digits, and now you just have to fill the 0's.

    This act of "filling in the 0's" is O(M^2). (For each of the 0's, you have to do O(M * B) work where B the base, in this case the number is base 10 so B = 10. And there are O(M) 0's. So in total it is O(M^2 * B). Or just O(M^2) since B = 10, is a constant.)

    There is another case, where you have to "loop around" because the character that was being incremented (in this case the 1 got incremented to 2, 3, .., then 7) hit 9 and then looped back around to 0. For example, if:

    n = 456713538, k = 3. Then you have to do:

    456800000

    456900000

    457000000

    But you still end up with a state where now you just have to "fill in the 0's". Again O(M^2).

»
2 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Example test cases were really handy for giving AC in one go.. DigitForces

»
2 months ago, # |
  Vote: I like it -17 Vote: I do not like it

My O(1) solution to the problem C. CLICK

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    it is O(40000 * 100)

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh my bad, I thought anything that goes on before any input is taken comes into compile time. So I mistook my O(40000*100) as O(1) as it didn't depend on n. Thanks for helping, a newbie here :)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    As a newbie I just wanted to show my solution and hopefully get some feedback ( which apparently I got ). Maybe my rating is what made you all to downvote. I was working hard, but now I'll double my hard work. Ciao :)

»
2 months ago, # |
Rev. 7   Vote: I like it +3 Vote: I do not like it

Problem A could be solved in $$$\mathcal{O}(1)$$$ time complexity:

  1. The unit digit is cyclic, and the cycle's length is 10.
  2. The sequence of remainders when dividing by 3 is cyclic, and the cycle's length is 3.

Let's define $$$f(x)$$$ to be $$$1$$$ if Polycarp likes $$$x$$$, and $$$0$$$ otherwise. Then, $$$f(x)$$$ is cyclic, and its cycle's length is $$$lcm(3, 10) = 30$$$.

We can compute the number of liked numbers among the first $$$30$$$ positive integers, let's call it $$$M$$$. Let's also say that there are $$$T$$$ contiguous ranges of size 30 between 1 and the number we're looking for (excluding that number).

Then $$$T \cdot M < K$$$, which means that $$$T = \left\lceil\frac{K}{M}\right\rceil - 1$$$. Now, we just need to find the $$$(K-T\cdot M)$$$-th liked number strictly greater than $$$30\cdot T$$$, which is less than 30 steps away from $$$30\cdot T$$$.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me that in the problem B can there be any testcase like:-

1 2 2

as 2 people are in the circle 1 is next to 2 and we have to output the person next to 2.

While I am hacking my solution by myself it's showing invalid input

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it was a good round, at least for new users like me.

»
2 months ago, # |
  Vote: I like it -15 Vote: I do not like it

MrPaul_TUser the solutions to problems A, B and C are possible in O(1) too. Will it be fine if you can please publish my O(1) solutions?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problemset was great. First 3 questions were easy to solve. I got stuck at D and wasn't able to solve.

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I solved D 30s after contest got over. Worst feeling ever :/

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I submitted E after a min, and man I felt sed cause my rank was pretty low and I hadn't solved D

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      E was easier to observe, but I wasted all my time on F1 and couldn't even solve it. Bad luck for me.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

" Let's iterate a prefix of n starting from the empty one so that the prefix will be the prefix of x. This prefix must contain only the digits a and b" can someone explain what this means. Problem F1

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Look at my submission for problem D. Link: https://codeforces.com/contest/1560/submission/126381278

Why this is getting TLE

»
2 months ago, # |
  Vote: I like it -27 Vote: I do not like it

MathForces

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem С is possible to generate arithmetic progression, and in solution use lower_bound

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Problem C can be easily done, first get the square root of k (bcz every row starts with square number), then start counting from top most box of next column.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys i had submitted solution for E problem with the same logic. It ran fine in my local IDE but codeforces gave wrong answer on test 1. Is this some bug in the codeforces or is there some part of the code which is wrong. Please do let me know.

126357466

Thank you.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it gave WA on my machine too, it is very messy so I couldn't find the mistake, maybe you could add some comments.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Speed of editorial was quick in the round! Thank!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My soln got stuck for f1 as I was unable to place the right characters to go for can someone give explanation of f1

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't see anyone mentioning it here, but many people have solved A using this method: Precompute an array with liked integers ranging from 1 to 1666, and then just output the k-1th element of the array. Are there any drawbacks to this method? It does take more space compared to the other solution, but the time complexity is much lower, O(1). (Correct me if I'm wrong).

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, this method works fine but we can calculate till 1000th number instead of storing from 1 to 1666 Hope thats clears it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved F1 and F2! At 2 minutes after contests finished. :(

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    ehh, that sucks, but you know that you are good enough to even Fs in Div3, now you can try increasing speed:)

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for nice comment :)

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You did it very fast from A to D. Any tips on how to increase speed?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        I try giving virtual contests, would recommend that, or you can do mashup of problems within time limit. Basically, solving problems in a timed environment helps ig.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem E, this submission gives different output on CF judge and local machine for some inputs, for e.g. for the i/p string v

Output of the above submission on OJ is -1, but when I run locally, the o/p is v v.

Can anyone please help in figuring out why this is happening.

Thank you.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I submitted your solution with GNU G++17 compiler and it gave Runtime error on test 2. I have faced problem like yours on codeforces too and submitting on GNU G++17 compiler always helped me.

»
2 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

This is my code for F2.

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

It's a pity that I didn't attend.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This was a great round!

»
2 months ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

I have another solution for Problem F2.

First, take the longest prefix of $$$n$$$, such that there are at most $$$k$$$ distinct digits. Let's call that prefix $$$p$$$.

If $$$p = n$$$, the answer is $$$n$$$.

Otherwise, let's call $$$i$$$ as the first index after $$$p$$$ (for example: if $$$n = 199754$$$, $$$k = 3$$$, then $$$p$$$ will be $$$1997$$$ and $$$i$$$ will be $$$4$$$ (indexes start at $$$0$$$)).

Now find the minimum $$$x$$$ such that $$$p$$$ contains $$$x$$$ and $$$x$$$ is greater than $$$i-th$$$ digit of $$$n$$$ ($$$x$$$ can't be equal to $$$i-th$$$ digit of $$$n$$$, because in that case you can choose longer prefix than $$$p$$$).

Now there are $$$2$$$ cases:

  • If $$$x$$$ exists, change the $$$i-th$$$ digit of $$$n$$$ into $$$x$$$. Then change the all remaining digits of $$$n$$$ (from $$$i+1$$$ to the last) into the smallest number in $$$p$$$.
  • Otherwise, you can see that all digits of $$$p$$$ are less than $$$9$$$ (because in that case the $$$i-th$$$ digit of $$$n$$$ can't be bigger than all digits of $$$p$$$). Now you have to change one of the digits of $$$p$$$ into a bigger one. It's easy to see that you have to change the digit which have the biggest index. Lets call that index $$$j$$$. At fist $$$j$$$ will be $$$i-1$$$. Now if you want to change $$$j-th$$$ digit (let's call it $$$a$$$), insert all digits before $$$j$$$ (from $$$0$$$ to $$$j-1$$$) into a $$$multiset$$$. Let's call that $$$multiset$$$ $$$s$$$. Now there are $$$3$$$ cases:
  1. If $$$s$$$ doesn't contain $$$a$$$, change $$$a$$$ into $$$a+1$$$ and insert $$$a+1$$$ into $$$s$$$. Now if $$$s$$$ contain less than $$$k$$$ distinct digits, change all remaining digits into $$$0$$$, otherwise, change them into the smallest digit in $$$s$$$.
  2. If $$$s$$$ contains $$$a$$$, check if there is a digit in $$$s$$$ greater than $$$a$$$, find that minimum digit (let's call it $$$b$$$), change $$$a$$$ into $$$b$$$, then insert $$$b$$$ into $$$s$$$. Now if $$$s$$$ contain less than $$$k$$$ distinct digits, change all remaining digits into $$$0$$$, otherwise, change them into the smallest digit in $$$s$$$.
  3. Otherwise $$$j$$$ will become $$$j-1$$$ and the digit before $$$a$$$ will be deleted from $$$s$$$ (after this $$$s$$$ may contain the digit before $$$a$$$).

Time complexity: $$$O(len$$$ $$$\mathrm{log}$$$ $$$len)$$$, where $$$len$$$ is the number of digits of $$$n$$$. This means that this solution will also work for $$$n \leq 10^{10^5}$$$ or even for bigger $$$n$$$.

My code

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

May I ask you 1 thing ? Does this contest rates for people who are having rating under 1600? - If yes, why I have been rated yet ? - I need an answer.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If there's no blog updates or notifications saying it's unrated,it will be rated for you. Just wait :)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great Contest, I became pupil for the first time.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why my $$$O(t2^{10}mk)$$$ solution got $$$Accepted$$$ for problem F2...

upd : got hacked lol

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ah you get hacked,orz!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think we have the same approach but I break when the value will only rise, that will only take $$$O(2^k \times m \times 2)$$$ memory but $$$O(mk)$$$ query

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C, I got my answer wrong on just one number: 999950883 . Can someone please tell why did this happen. Is this number special in some terms? My submission link: https://codeforces.com/contest/1560/submission/126314408

»
2 months ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

Disliked this contest, 7 constructive/greedy approaches, really? Nothing educational/interesting. Your div.3 #734 was far more better: it had cool dp and graph problems.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very good Editorial,and very good problem!

especially for problem F2,a short solution and a long solution are very good for readers.

And it is pretty suitable for beginner coders!

:)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is there any other way to guess that 2^18 thing(size of set of powers of 2) for problem D? Thanks

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how does problem rating system works I dont think C would be 800 atleast 900, I guess since a lot of people have solved it , it is given 800.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C is similar to the CSES Number Spiral, here is the O(1) solution comparatively easy from the editorial.

        int n;
	cin >> n;
	int y = sqrt(n);
	if(y*y == n){
		cout << y << ' ' << 1 << '\n';
		return;
	}
	int z = y+1;
	if(n > z*z - z){
		cout << z << ' ' << z*z - n + 1 << '\n';
		return;
	}
	cout << n - y*y << ' ' << y+1 << '\n';
  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it -8 Vote: I do not like it

    sqrt() doesn't work in $$$O(1)$$$. It works in $$$O(\mathrm{log}$$$ $$$n)$$$.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      why down vote isn't asymptotic complexity of this library function $$$sqrt()$$$ is $$$\mathcal O(logn)$$$

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E has the sorting and binary search tags, can someone explain where it can be used in the solution?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain to me...why in problem D..we are only considering up to power of 2 equal to 18?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes please anyone?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it is $$$2\cdot10^{18}$$$

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes...sorry for the mistake..do you know why this upper limit is taken!

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        In worst we may have to remove either all digit of n which can be atmost 10 operation as $$$limit$$$ of n is $$$10^9$$$ or we may have to append 9 digit in right of n which increases value of n equal $$$10^{18}$$$ is equivalent to $$$2^{60}$$$ at most. Checking for all 60 power of 2 and and finding min operation to convert it to perfect power of $$$2$$$.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In Editorial for D problem I am unable to understand why upper limit is 10^18

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Observe that n's upper bound means there's a limit to your answer which is the number you'd get from deleting all digits and adding a single-digit power of two. The question then is how large of a power-of-2 could you construct with any max-digit-length n + that many add-a-digit-to-the-right operations?

    The last case in the sample was helpful in that regard: if you bounded your powers of two according to n itself, you'd get an incorrect result for it.

    Extra: consider why 10^9 and 10^18 are commonly seen limits...

    Disclosure: I didn't think of this during the contest either, womp womp.

    edit: uhhhh, this was in the editorial... in which case, sorry for being repetitive...

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I really liked this contest, genuinely enjoyed doing problems C,D,E,F.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what kind of error is this?"wrong answer order too long"...everything seems alright...getting all the outputs that are visible, matching...can someone help? string trans problem https://codeforces.com/contest/1560/submission/126609563

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Which is 189 number in 5 test case in 1560F1 - Nearest Beautiful Number (easy version) problem?MrPaul_TUser please give that case because there are a huge number of submissions failed on that case and it is interesting to me to know why

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem c i didn't understand the logic/intution behind statement "the number belongs to the i-th row and the (i−(m−i))-th column. if(m>i)" can someone explain it please

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey guys, this was my 2nd competition abd I could solve only A, B and C, one more than my first competition. But I notice that for most of the question I form the logic almost equal to the editorial but screw up in small details. Any tips and suggestions for me??

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is my approach for problem C. Although this showed WA during the contest but it got accepted now. 126677915

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please help me with understanding why this code gives TLE though it's mostly similar to the solution given in editorial. https://codeforces.com/contest/1560/submission/126656613

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please someone help me.... why my answer is the wrong test3 for F1. 126757323 above is my submission. also tell me, how to improve my code.

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For problem F,May I get the test case for 204th number? I could not know where my submission got the answer wrong. Thanks in advance

https://codeforces.com/contest/1560/submission/129336848

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How I solved C problem..... (1,2,5,10,........The first thing as mentioned in the editorial the numbers are increasing in Arithmetic Progression .) see the increment follows(+1,+3,+5,......)... If you notice the max number for a particular layer is minimum in that layer + 2*col -2 (col=column number 1-based indexing..) For eg consider the layer that contains 2 .....(2,3,4) here max is 4 which is equal to 2+2*2-2 .... Now we will run a while loop till we find mx,mn such that mx>=k and mn<=k ...... when will hit this condition we can simply increment mn upto(column num -1) and check if we get mn==k ........if we still dont get mn==k it means we have to find k towards left sol we will decrement col num ........Finally just print row num and col num Here my submission (https://codeforces.com/contest/1560/submission/129896567)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please provide more beginer friendly tutorial for problem D. I understand the whole, but didn't understand how we come to consider power of two that are less than 10^18. I understand why it is needed but don't know how to approach so that figure out power should be less than 10^18(20digits) long.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

my cpp code...

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin>>n;

        int a=1, d=1, cnt=0;
        while (a<=n) {
            a+=d;
            cnt+=1;
            d+=2;
        }
        int p = a-d+2;
        int mc = p+cnt-1;
        if ( n <= mc) {
            cout<<cnt-(mc -n )<<" "<<cnt<<endl;
        } else {
            cout<<cnt<<" "<<cnt-(n-mc)<<endl;
        }
    }   

    return 0;

}
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E by binary search? (It is one of the problem tags).