Hello, Codeforces!

I'm glad to invite you to amazing (we've tried to make it such) Codeforces Round #739 (Div. 3) which will start on Aug/18/2021 17:35 (Moscow time). This round is my (MrPaul_TUser) second round a significant contribution to which was also made by MikeMirzayanov, BledDest, DK318, unreal.eugene, and geranazavr555.

The round contains 7-8 problems. The difficulties of the problems are expected to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round, it will be a 12-hour phase of open hacks. We tried to make really strong tests — just like you will be surprised if many solutions fail after the contest is over.

You will be given **7-8 problems** and **2 hours 15 minutes** to solve them.

Note that **the penalty** for the wrong submission in this round (and the following Div. 3 rounds) is **10 minutes**.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as trusted participants of the third division, you must:

- take part in at least two rated rounds (and solve at least one problem in each of them),
- do not have a point of 1900 or higher in the rating.

**Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.**

Thanks to powergee101, artsin666, WitchOfTruth, ivanzuki, A_Killer, mahade31, I_Remember_Olya_ashmelev, nooinenoojno, Gassa, _c_k_r_, spotless, iankury, UpS0lver, ncduy0303, and Vladosiya for testing the round and improving tasks.

Good luck and have fun!

**UPD** Editorial

Lighthearted memeReally the problems are so constructive

Can't wait for the round!

This round is clashing with ICPC Asia West Gwalior-Pune regionals!

Yeah if any postponement can be done then it would be great!

There is a gift from Codeforces &

MikeVirtual ContestFor those who cant appear in live contest..Hope you enjoy the problem after the contest :)

I hope this turns out to be my last rated Div 3 round!

`

I also thought the same thing but then i was stopped at 1598 xddd

I also thought the same thing after Codeforces Round #634 (Div. 3)

Great work from there and then now you can even skip div2s when there are occasional div1+div2

May Be.

But, it is very unlikely that you leave a colour for the first time and never come back.

As a FT-

TESTER, you know what to do.I RECOMMENDREAD ALL THE PROBLEM SET.

I REPEATREAD ALL OF 'em.

I BELIEVETHE PROBLEMS ARE VERY NEAT AND YOU WILL ENJOY.

Hopefully I don't have to become an UpS0lver after the contest.

Hopefully this round will be great.

I REPEATTHE PROBLEMS ARE GREAT.

I enjoyed the problemset and its awesome. Thanks a lot to all behind this div3.

OOOH! 8 problems and 2 hours and 15 mins to solve them. I am very excited about this round. So thank you CodeForces that you didn't make me expert in the last round with a difference of 7 points from expert so I can participate in this contest officially.

as for me...

Div3 round but only blue, purple and red testers ^_^

It is on pluses , cool !

I know it's difficult for the problem-setters, but can you please postpone the contest by a day? We have our Asia West Gwalior-Pune regionals on 18th. I know, CF works differently but considering there are no contests within the next 5 days, I request you guys to please postpone. Please, we don't want to miss a div 3 round :)

Good luck to everyone!

Good luck to everyone!

May the forces of code be with us.excited!!

He tried his best to make the tester list palindromic xD

Finally, as a tester

give you contribution.

Good Luck to Mahade Hasan vai.

I'm Pretty excited for my first unrated round ! :)

8 problems so guessing first 5 will be cakewalk for majority of participants

We hope so :)

As a tester, I sincerely wish you all enjoy this round and get high ratings!

Good luck to everyone!

(Tester)_c_k_r_ orz

In div3 do all questions have same score? Like A and F have same value upon solving?

Here the distribution of places is not based on points, but on the number of solved tasks and penalties for all tasks

Yes, this contest uses advanced ICPC rules. As far as I know, the only change is an 12-hour open hacking phase.

Hope I stay cyan after this contest :) .

Hope I stay blue after this contest

impossible.

Excited to participate in my First round :)

Evening m'lady.

Hi Pablo, how's Beluga doing?

good

Trust me beluga :}

Give me your Codeforces password...

You will become a grandmaster in the next contest.

Happy Birthday :)

Why did you put your phone inside the microwave lmao

I have come back to div3.

CF Analytics Extension

https://chrome.google.com/webstore/detail/cf-analytics/hhljbjodjdbjbggddjaidojnlmaobcpo?fbclid=IwAR2CdKUrtNlHEwNB4Sxsv6VV0DqmkUXxfTTw1eCsclM3aYv-o_Q7l9eK0e4

Finally a Div3 round .. i was waiting for it ...thanks all the authors and testers , today gonna be my first rated contest ..excited as fuck ..woooohoo .. love from hell

good luck

i hope there will be no IN QUEUE this time , when u r in queue u waste time bcz u cant concentrate on the next question fully

I hope I will get -100

lol

just send RTE

Hoping to change color this time :).

Give me some sunshine, give me some rain, give me another chance to become pupil once again ;-;

I hope there will be no "In queue" today :)

If this contest doesn't work out well for me , I will wake up early for next week to practice daily.

Where is vovuh ?

sleeping around

hopefully I will become a pupil today so wish me luck!

Anyone else facing "Unexpected errors"?

Nice problems!!! Keep up the good work.

What does penalty mean?

I solved D using Python and got TLE. Then submitted the exact same code in C++ and got AC. Is this right? I am new to this, but I thought it should not be like this

I am salty because it cost me 40 minutes penalty + another 20 to figure it out

Python is slower mate, that's why people use c++ at all

that's okay, python is the worst programming language for sport programming then you need fast and low-memory-usage programs

Amazing Div3 round. Well balanced questions. thanking all the problem setters of the round ^_^

Digitforces :)

what a shit am i?

i could not even solve B , there was already 10000< summissions

i am really excited for this contest , really big disappointment from me

SpoilerMotivation goes in negative direction

just git good mate

I just wanted to thank you for setting problem E. One of the most beautiful problems I've seen from CF contests in a while. A problem solved after some cool ideas. Thanks, setters!

problem F1 memeI relate to this 100%

TL PANIK

oh my god, I didn't expect to be able to solve F1 without knowing how to do D or E at all

That's why

I REPEATREAD ALL OF 'em.

Problem E was really nice and interesting :D

my F2

solve it 19 seconds before the contest ends....

the time limit is too strict....

Actually the only solution that came to my mind was the greedy one and that works pretty fast, just think backward and try to replace each digit and construct a valid number.

i did it in 5mins before. 700ms with optimisations :|

E was MUCH easier than F1. Damn caseworks in F1. Everytime I got WA, I discover a new casework.

I am too young too simple.I thought F1 is easier than E...

I overlooked E and tried F1 cuz it had "Easy version" in it

F1 was trivial. There are only about 50000 possible numbers to construct. So you build them all and then solve queries trivally.

What in the world is pretest 2 for F1 D: ;-;

super ultra speedforce lmao

can't agree because I found problems challenging enough

I just want to say everyone solve problems so fast ^^

It's very natural for contestants of this generation.Especially, after the introduction of AtCoder

Deleted

How to solve problem D ?

Iterate over all powers of 2...

You can check my submission to understand what I mean: https://codeforces.com/contest/1560/submission/126346052

Can you tell me your idea? I have trouble understanding your code !!!

you can iterate over powers of 2 with upper bound of 2^63 so 64 items to check: just check how many digits of k already fits into current power of 2, how many digits you should remove and how many digits you should add to get current power of 2. In the end choose min

i don't understand how to do it to optimize the time, i think so too, but it doesn't pass the time limit

maybe code would help https://codeforces.com/contest/1560/submission/126327050

Two pointers and greedy

Can you tell me how to do it in more detail?

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

here is my solution, it's easy to understand (At least I think so. 0.0)

idea: First preprocess all the powers of 2, a total of 60. Then compare n with these one by one and take the minimum number of operations.

when u stuck on easy problem in div-3. life suc**d. :(

it's okay, not all problems from div3 are easy even for div2 participants, so be happy, your life is beautiful

Yes Life is Beautiful <3

Ur 17 WA on F before AC is really inspirable sir..

:D

I coded a backtracking solution for F1 but sadly it was getting TLE. I think that the time limit was too tight.It was (10C2*10^4*2^9) operations which is rougly 2*10^8 operations and could pass in 2-3 secs.

I think that the time limit was too tightOr maybe, just maybe, there could have been a much faster solution.

I said that in the context of a backtracking solution. Obviously there could be other ways.Btw how did you solve it?

oh, okay!

I solved it in the following way:

Iterate from the last digit to the first digit. Say you are at the $$$i_{th}$$$ digit(from the end). If you can keep the portion to its left the same, change this one digit, and keep the portion to its right as small as possible within the given your constraints, this is your answer. If you can't, move on to the digit on its immediate left.

My code, sorry it's quite messy: 126351416

Thanks for explaining your thought process will implement it.

you dont actually need to check all possible choices for the two digits btw. In case if the number is not already beautiful, the answer's first digit would be the same as the first digit of the original number, then you can choose for the other number. that way your solution can be sped up by a factor of 4.5

Yeah I thought about that but I got low on time will implement it.

Mine Backtracking passed the Pretests , you can have a look if you want .

A perfect Codeforces contest that showed me where I stand and what are my weaknesses. I realized I have to learn a lot more to try solving D,E,F etc. I need to learn more and practise more.

My best contest yet, first time solving A to E (Okay I know it's a Div. 3 but still).

I would think chess players of your level would do significantly better than this

hahaha

Are you the real Anish Giri? Add me on lichess (same name)

Lol ofc not, I do play chess though, I just added you

I rarely solve problems with 1000 solutions. But this time F1 was easy for me and I was very wonder to solve it. And I didn't get why there are so less solutions.

Because lesser Blue and Purple Participate in Div 3 rounds compared to Div 2 , Many a times When people are unable to solve a problem ( this time Problem E ) and the contest is unrated people don't move to next problem .

`atol`

function (c++) wasted my 20 mins contest time..`-_-`

`Problem - F1`

— 126353303Idea isn't good,but code is hard to code.

Can anyone help me with this? I was using my Codeblock IDE to code, and I passed the first test case in problem F2, but when I submit my code in Codeforces, the output was different! https://codeforces.com/contest/1560/submission/126358147 Here's the image: https://postimg.cc/tZ133pW7

I mean F2 problem

Nice contest and cool problems, but i think that it has so many string ploblems, like D, E and F1/F2 (F1 and F2 are string problems too, rigth?)

F1 could be solved without string as well. I think F2 was easier than E.

yep, it was.

Bruteforces

If my first submission was accepted but I submitted again then my second submission would be considered and first one would get skipped ,right?

Yes I think so

Can someone just explain to me how the answer to the test case in F : 1 1 2 answer is 1 ? isn't it supposed to be 10 ? because there's two different numbers in it.

we have to use atmost 2 digits but can be done in 1 too.

Ye, just realized that and it costed me 6 WA :[

Contest Admin MrPaul_TUser please take strict action against this guy utsav_vasoya_85

Posting video solution during the contest which is violating Codeforces T&C PolicyThe link to the Video solution

It gets me how much views these videos get so fast. That just shows how many filthy cheaters there are. Makes me angry.

i am so sorry i will never do this again and if u want i will take down video also this is first and last time. this is my word. if this will happen again take a strict action on me.

There is no sense of taking the video down now -_-

You just took away some hard working guys actual standing from themAmazing pretests (especially pretest 1 (Especially for D and E)). I caught many edge cases where the code would have failed when in local testing itself. Thank you.

+

Can anyone find a test case for my F1 solution 126364100 it failed in pretest 2 |_|

Check this:

The output should be

`555`

instead of`556`

in your solution.Shouldn't it be 556 coz k is 2?

Check the statements. The number should contain

no more than kdifferent digits.Wasted

Problem F1, F2 is solvable with digit-dp + binary-search if you're not good with greedy observations, like me.

Problem F: Nearest Beautiful NumberThis problem originally was only one problem.

Try to think backward, start from the end try to increase the current digit:

Then you have three options: either the number ending at current position has distinct digits equal to K or less than K or greater.

If it's equal to K, then we need to add the smallest digit that already exist in the current substring as we can't add more other digits. (if we added it will be greater than K)

if it's less than K then we can just add zeros.

if it's greater than K then we need to remove that digit, just continue.

sol: https://codeforces.com/contest/1560/submission/126370632

Can't come up with an example for the less than K case, do you know any?

102 2

102 to 109 will not work as it contains 3 digits.

now we need to increase second digit 0-> 1 so 11_ and in this case it's already less than 2 so we add zeros. 110

Task C was impudently copied from the ROI:https://vos.olimpiada.ru/upload/files/Arhive_tasks/2020-21/school/iikt/tasks-iikt-9-11-sch-msk-20-21.pdfDeleted.

Did you just accuse me of something? Trust me, simple problem ideas are often not new. That is life. And the coincidences are accidental. The problem was invented by me absolutely independently. And I don't think it's even a problem, but rather a programming exercise.

No, I wasn't trying to blame anyone. I just stated the fact, since many participants could just copy the code :(

you know what

`impudently`

means, right?They aren’t even the same problem LOL, the grids are completely different. Just look at first row: 1-2-5-10 vs 1-2-9-10. Moral of the story is,

Don’t accuse someone without looking carefully.Yeah, u are right...

U need to change two rows of code:

https://vos.olimpiada.ru/upload/files/Arhive_tasks/2020-21/school/iikt/ans-iikt-9-11-sch-msk-20-21.pdf

Submission: https://codeforces.com/contest/1560/submission/126375425

First comment don, t know what to write here

I had solved D, but I did not account for the max length that n can have (apparantly upto 10^18). But foolish me, thought that this would not cross 10^11(worst case). It will cause my rating to drop (which is already low). I will be more careful in the future. It was an excellent problem.

I am not sure what I am doing wrong here. If you find the mistake in my code please do tell me. 126357637

test

1

13 1

wrong answer — expected: '22', found: '33'

Yeah got it thanks .

Are there are any other ways to solve E?

my logicI checked if my current string* after adding the last removed character x contains the previous string (without x) ( where len(curr) = len of prev string + cnt[x] in s)

eg . in the 1st testcase , prev = aaca (on removal of 'b) and curr = t[idx-len+1 : idx] , then we get curr = abaca,

I saw that in C many people are iterating to get in what range will the number lie and do calculations according to that. You can do this in O(1) by using the fact that sum of first N odd numbers is

N².My solution O(1) for problem C: https://codeforces.com/contest/1560/submission/126316175 Edit: it is not O(1) as pointed by some of the people in comments, I never bothered to look up complexity of pow function before.

Hmm , we can find the coordinates with the help of square root of that number as we can see all perfect squares lie in the first column (k*k lies in (k,1))

Actually It is easier than your code, After getting N^2 which is less than k We just N^2 — (N — 1)^2 == > 2*N — 1 And find (min(abs(2*N — 1 -k), abs(N^2 — k)), N(row, col depends on which is closer to k(i.e. whether N^2 or 2*N — 1))

your solution runs in $$$O(log \space k)$$$

Mine runs in O(1) 126374450

this runs in $$$\sqrt n$$$

Yes yes i forgot i am sorry, If only i could Look for N/2 — i and N/2 + i sides to find optimal square number

Thanks for pointing it out, I'll edit my statement, I never bothered to look up complexity of pow function before, my bad.

`pow(n,2)`

in your case works fine, $$$O(1)$$$.`math.sqrt(K)`

runs in $$$O(log K)$$$Can you tell the source of this info, from what I found on net, the complexity of math.sqrt() operation in python was given to be O(M(d)) where d is the number of digits

yes, I think u're right

This is not o(1)

Thanks for pointing it out, I'll edit my statement, I never bothered to look up complexity of pow function before, my bad.

It might be O(1) hmm.

Probably depends on how you define input size.

thanks for Balanced round meoww

So happy to give this round, From last 3 rounds I had seen failures but after doing around 300 questions, I was able to solve 3 problems, Sadly for C the time got over. :( :( :(

video of hacking myself out of 7th

Image Link

Some people are really bad, using random id to Hard code a wrong case which is not pretest, and then hacking them with original id :'(

If I am wrong explain me reason of that "if"

Wtf is that?

I'd like to report a suspicious hacking attempt:

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

the source of the hacked with the hacker's are very similar, and the hacked submission has a special case (n=555), probably inserted there so it would be easy to hack (if you would know which submission to hack). No reasonable contestant would ever add such a case in their program.

the same happened here (by the same hacker on the same 'victim'): https://codeforces.com/contest/1560/submission/126362247, he added his own name in the hacked submission :)).

If this isn't conclusive proof of ''cheating'', then.. what would be a conclusive proof?

Edit: just looked at the comment that came before mine-- Is this "standard practice" in acm-icpc rounds :))?

Thank you for a formal and proper comment on the same

I wish they do something about it. :(

The same user also hacked every single solution by __Kamal123 in a similar way, and they have almost the exact same code.

https://codeforces.com/contest/1560/participant/__Kamal123

LOLLLL!He is too rude to forgive. Imagine stealing a bank and leaving your ID.Can any one explain why this solution https://codeforces.com/contest/1560/submission/126384961 Got TLE ?

I would suggest try using vector in place of Set , Set has a good constant factor along with logarithmic complexity for almost all operations

Bogdan_fake clearly designed their solutions to be hacked. Surprisingly, a user called Bogdan_feysa hacked each solution...

IDK man the cheating just gets too much at a point.

Second user I have found: abhishek_kira hacking Rahul_uzumaku. https://codeforces.com/contest/1560/submission/126382347 see k==122112 https://codeforces.com/contest/1560/submission/126381396 see convoluted if statement at the start

Third instance I have found. Again same user as second: abhishek_kira hacking alpha__Noone. https://codeforces.com/contest/1560/submission/126364309 see K==99 && n==989891

Fourth instance. Again same user: abhishek_kira hacking gagan_preetcp. https://codeforces.com/contest/1560/submission/126361622 see n==989 && K==99

rishisgsits_22 also hacked all the solutions for gs0801it191068

they put a missing testcase to hack them later

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

hi,yes,i tried using this after i saw at least 5 guys doing the same thing,but guess what,as far as I understand it now,it only counts if you hacked someone who is higher in the score table than you,and if ou hacked someone lower than you,it doesnt affect your rating,thats why I used the acc which i created to prove my friend wrong,because he was saying that those solutions will get me extra points,right after i saw that those users who hadn't been participating in at least 2 rating rounds,wont be included in the final table,i used the acc because i had only one rating contest there,therefore,i wont be in the final scoretable,even with all that,i i only started making the solutions only after the end of the contest,so they wont affect anyone,i made 5 hacks on my acc,to prove my friend wrong,the 6 hack was on the guy,who i don't know,i just saw him hack the same user twice,and i wanted to make fun of him,hacking his solution faster than him(if you don't believe me,you can check it youself),but thanks for reacting,I'm really glad that there are users,who have the same opinion about hackers,that they should be punished,hope you understand that i made those hacks for fun,knowing that it won't affect my final standing,thanks for reacting and i wish you high rating

and yes,if someone with admin rights is reading this,could you please delete or ban the Bogdan_fake account,because i understand that it pissed off other people,that i decided to orove my point through hacks,and i would like to ban account Bogdan_fake ,so it wont be pissing off anyone else,thanks

126400412=> inO(1)Solution for Problem1560C - Infinity Tablesqrt is log(n) function.

ohhh got it thanks

if your rating is less than 1600, then the round will be rated for you. But there's no change in my rating.

Currently, the hacking phase is going on. The final standings would be declared after the hacking phase is finished, and after some hours, the ratings will also be updated.

rating distributions ?

Thanks to this round! Enjoy this round very much! :)

that was cool contst, but unfortunately i didn't wrote good(

Hello, when will the new ratings appear on the profile?

Contest NAME Should be CodeForces

MATHRound(Div 3)If you don't like codeforces and it's contests get out of it simple :)

I can see your performance in other non-math contests, so shut the f*ck up! You don't deserve rating, you know nothing bloody prick.

Well, there was some good string problems

I don't think so.Only Problem C is a math problem,and it is not difficult to work out. And some problems in this round are interesting,just like Problem F.

Why still I didn't get my rating for this contest?

why it is still showing as unrated for me?

My rating is 1194 .Still its showing unrated for me. But in bold word the contest rules said -

"Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you." .

Its very disappointing as for the first time i might became pupil if i got rated this round. :(

In dv3/edu round, there have 12hours hacking period. so have to wait for rating change around 15hours from contest end bro.

So wait a little bit more, already system testing end for this round.

your new rating will be around 1240 :)

Why unrated?

When will the ratings be updated?

Congrats for new color! :) Your new rating will be around 1330

how are you calculating this?

and can you tell mine also?

congrats man new color!! around 1210

are you estimating this or some kind of calculation?

Use CF-Predictor to get estimated rating changes.

don't burst my bubble :)!!!

I just installed CF predictor, but it didn't work. I don't know why.

It worked

I like this round.Some problems are intersting,especially the problem F :)

is this unrated coz ratings has not changed yet

I keep hearing we will have to wait a bit. I probably going to lose rating in this round so not keen on seeing the change really. :(

Let me see how many down votes you can give on this comment!!

Hmmm, so utilizing human's tendency of doing exactly what he/she was told to do... :)

Did this round go unrated ???

somebody please tell me...

No, just wait

Not, it's rated just now.

I have to say that div2 is easier for me than this.

Finally I became pupil after a year of greyness

I too became pupil.

Because it was 8 problems so the first 4 problems were a little bit easy. I enjoyed this contest :)

Great Round! Thanks!

Here to report 2 cheaters from this roundPay a visit, solutions from round #739: https://codeforces.com/contest/1560/submission/126357111 https://codeforces.com/contest/1560/submission/126342205

MikeMirzayanov

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