Codeforces Round #739 (Div. 3)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Привет, Codeforces!

Рад пригласить Вас на увлекательный (а мы постарались его сделать таким) Codeforces Round 739 (Div. 3) — раунд для третьего дивизиона, который состоится в 18.08.2021 17:35 (Московское время). Это мой (MrPaul_TUser) второй раунд, существенный вклад в создание которого также внесли MikeMirzayanov, BledDest, DK318, unreal.eugene и geranazavr555.

Этот раунд содержит 7-8 задач. Задачи подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше, могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-часовая фаза открытых взломов. Мы постарались сделать сильные тесты — так же как и Вы будем весьма удивлены, если у многих попадают решения после окончания контеста.

Вам будет предложено 7-8 задач и 2 часа 15 минут на их решение.

Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
не иметь в рейтинге точку 1900 или выше. Независимо от того, являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Огромная благодарность powergee101, artsin666, WitchOfTruth, ivanzuki, God_Of_Code, mahade31, ashmelev, nooinenoojno, Gassa, _c_k_r_, Ahmed_Salama, iankury, Killever, ncduy0303 и Vladosiya за помощь в тестировании раунда и улучшении задач.

Всем удачи и хорошего настроения!

UPD Разбор задач

Комментарии (188)

Показать архивные | Написать комментарий?

naman1601

3 года назад, # |

+81

Lighthearted meme

→ Ответить

maddler

3 года назад, # ^ |

+19

Really the problems are so constructive

Tushar11

in this round, some problem definitely have parts.

Dhoni_fan

-15

TBH these div3s are not of Vovuh's level.

I only love Vovuh's Div3s.

lis05

https://mirror.codeforces.com/blog/entry/93808

ojus_single

Can't wait for the round!

greenindia

-54

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

lucifergd192

-59

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

honeyop

← Rev. 2 →

+23

There is a gift from Codeforces &

Mike

aditya309

+32

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

peek4b00

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

timreizin

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

PHENOMENALAB

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

Killever

+71

As a FT- TESTER , you know what to do.

I RECOMMEND

I REPEAT

I BELIEVE

FairoozR

Hopefully this round will be great.

+21

breddreamer

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

Blobo2_Blobo2

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.

Wayne_Yan

as for me...

TimeToAct1on

It is on pluses , cool !

Bunohash

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

k1ngash

Good luck to everyone!

Alwoosh

ZaiaF_Rahman

He tried his best to make the tester list palindromic xD

mr_zodiac

this will be my first contest i wanted to know is the penalty only for 10 mins or some points will also be deducted and if i get a TLE will i also get a penalty. Thank you

if your submission will fail, you will get penalty

and what about the penalty is it only for 10 mins or some points will also be deducted

for each task, with every non AC submussion you will get penalty of 10, and the last AC submission will decrease as many points as u have used to submit it example, imagine that you have got task AC at 1:59 with two unsuccessful submissons: your penalty for this task will be 10*2 + 119 = 139. the total penalty is the sum for each task

mahade31

Finally, as a tester

Ver_Nick

give you contribution.

_milon_3.4

Good Luck to Mahade Hasan vai.

ShivanshJ

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

Ooommmkrs

+10

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

powergee101

+24

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

DaMing2001

the0dd1out

+11

(Tester)_c_k_r_ orz

1_Hypex_

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

OG_Matveychick1

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

tch1cherin

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

That_was_legendary

-8

Hope I stay cyan after this contest :) .

LightSky

-12

Hope I stay blue after this contest

impossible.

paras_417

Excited to participate in my First round :)

warr

Evening m'lady.

Trippie

Hi Pablo, how's Beluga doing?

dukhi_insaan

good

Diana773

I have come back to div3.

shakilsustswe

CF Analytics Extension

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

Hogwarts.dropout

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

kushagra7

I hope I will get -100

just send RTE

BitWiseOperator

Hoping to change color this time :).

yeetholmes619

+13

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

soham976roy

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

marsey20

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

itachi1720

-13

Where is vovuh ?

sleeping around

ekatva_3

Anyone else facing "Unexpected errors"?

Theo830

+22

Nice problems!!! Keep up the good work.

ushmitadutta

What does penalty mean?

Michal

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

defnotmee

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

Dev_Manus

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

gabaswillwinIOI2022

+53

Digitforces :)

Leonardo_Paes

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!

gnudgnaoh

+16

problem F1 meme

Dan4Life

I relate to this 100%

TL PANIK

swayingdream

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_Hate_DIV3s

+18

Problem E was really nice and interesting :D

mickeyandkaka1

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 :|

osource

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

Acc_Robin

+14

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

Agnimandur

+17

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

lazywitt

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

shioiori

super ultra speedforce lmao

turzo_sawroop

can't agree because I found problems challenging enough

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

nuyenhuy

How to solve problem D ?

MrOtter

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://mirror.codeforces.com/contest/1560/submission/126327050

Rudro25

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

AmarShukla

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 tight

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

I said that in the context of a backtracking solution.

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.

RalseiJevil

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

dhruv7888

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

Santoryu

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

TsatskiPetski

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 .

astro_lion

atol function (c++) wasted my 20 mins contest time.. -_- Problem - F1 — 126353303

superman1236969

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://mirror.codeforces.com/contest/1560/submission/126358147 Here's the image: https://postimg.cc/tZ133pW7

I mean F2 problem

LoboLobo

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.

yasserkhan45

Bruteforces

DarkTigerFAF

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.

vatsal2198

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_85

Posting video solution during the contest which is violating Codeforces T&C Policy

The link to the Video solution

_Utsav_85

-20

good round

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

You just took away some hard working guys actual standing from them

lordmannyjinx

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

The_Professor

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

rkfcccccc

Check this:

1
555 2

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 k different digits.

Problem F: Nearest Beautiful Number

chlalstjr

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

d0t_d0t

-51

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

black_trees

← Rev. 4 →

Deleted.

MikeMirzayanov

+59

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 :(

No, I wasn't trying to blame anyone.

you know what impudently means, right?

bregue

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.

mnkqc

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

13 1

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

Yeah got it thanks .

simran.singh2198

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://mirror.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.

← Rev. 3 →

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

Darknez

Mine runs in O(1) 126374450

n = input.nextInt();
st = 1;
ct =1;
while(st < n){
    ct++;
    st = ct*ct;
}

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

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

MijPeter

yes, I think u're right

This is not o(1)

It might be O(1) hmm.

Probably depends on how you define input size.

sary

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. :( :( :(

____RoHit____

QUESTION D. ... DOES'NT MAKES ANY SENSE...

LIKE.. DON'T MAKE A MEANING LESS QUESTION.(-_-)

question d is very nice

galen_colin

video of hacking myself out of 7th

I did D with keeping track of 2^61 as well.(got accepted) could anybody tell till what power of 2 was required to be thought of.

jainvaidic

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 :'(

valeriu

I'd like to report a suspicious hacking attempt:

https://mirror.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://mirror.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. :(

Toinfinity

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

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

Sadek_Mo

LOLLLL! He is too rude to forgive. Imagine stealing a bank and leaving your ID.

Zaoldyeck

Can any one explain why this solution https://mirror.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

aadit.ambadkar

MakiseRintarou clearly designed their solutions to be hacked. Surprisingly, a user called FBI 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://mirror.codeforces.com/contest/1560/submission/126382347 see k==122112 https://mirror.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://mirror.codeforces.com/contest/1560/submission/126364309 see K==99 && n==989891

Fourth instance. Again same user: abhishek_kira hacking ash_cp. https://mirror.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://mirror.codeforces.com/contest/1560/submission/126405273

FBI

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

Eason_AC

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

sabyr

...

Blackmaillor

Contest NAME Should be CodeForces MATH Round(Div 3)

fck_cheater

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.

Wgmlgz

Well, there was some good string problems

DitaMirika

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.

toNmoYy

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.