Блог пользователя MrPaul_TUser

Автор MrPaul_TUser, история, 5 лет назад, перевод, По-русски

Идеи задач: MikeMirzayanov

1560A - Нелюбовь к тройкам

Разбор
Решение

1560B - Кто напротив?

Разбор
Решение

1560C - Бесконечная таблица

Разбор
Решение

1560D - Сделай степень двойки

Разбор
Решение

1560E - Поликарп и преобразование строки

Разбор
Решение

1560F1 - Ближайшее красивое число (упрощённая версия)

Разбор
Решение

1560F2 - Ближайшее красивое число (усложнённая версия)

Разбор
Короткое решение
Длинное решение
Разбор задач Codeforces Round 739 (Div. 3)
  • Проголосовать: нравится
  • +73
  • Проголосовать: не нравится

»
5 лет назад, скрыть # |
← Rev. 5  
Проголосовать: нравится -8 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +42 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -30 Проголосовать: не нравится

Prob C was very interesting ngl.

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +22 Проголосовать: не нравится

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.

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +22 Проголосовать: не нравится

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

It was a nice problem :)

»
5 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +8 Проголосовать: не нравится
A clean solution for C
»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +11 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +5 Проголосовать: не нравится

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

Btw problems are pretty good!!

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    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).

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +18 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -17 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
← Rev. 7  
Проголосовать: нравится +3 Проголосовать: не нравится

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 \lt 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$$$.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

" 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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

Why this is getting TLE

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -27 Проголосовать: не нравится

MathForces

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +3 Проголосовать: не нравится

This is my code for F2.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +10 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Great Contest, I became pupil for the first time.

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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

upd : got hacked lol

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.me/contest/1560/submission/126314408

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +9 Проголосовать: не нравится

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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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!

:)

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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';
»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.me/contest/1560/submission/126609563

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.me/contest/1560/submission/126656613

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    5 лет назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится 0 Проголосовать: не нравится

    Because max length of input string n is 9 bc n < 10^9 except 10^9 itself. You can always delete all 9 digits and add a 1, making the total 10 moves. Or for 10^9, just delete all the zeroes, which is also 9 moves. That means there's no reason to go past powers of two greater than 18 digits, because starting from 19 digits, you can just make the number 1 instead. So, you only have to check powers of two < 10^18.

»
5 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

I brute-forced my way through problem E and it worked. The algo I used was after finding order in which elements were to be deleted, I took a string s0 which contained all k unique elements to be deleted, then I made a string s1 delting first elment to be deleted.

eg:s=polycarppoycarppoyarppyarppyrpprppp

s0=polycar s1=poycar

After this I used to rabin-karp to find all occurences of s1 in input string s then I kept updating my s0

v=[first index of occurence of s1 in s]

for all j in v

s0=[0.....j-1]

then I applied the algo given in qs to see if it worked. The solution worked. But shouldnt it be n^2 in worst worst case? Maybe the test cases were weak

https://codeforces.me/contest/1560/submission/145174200