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, God_Of_Code, mahade31, ashmelev, nooinenoojno, Gassa, _c_k_r_, Ahmed_Salama, iankury, Killever, ncduy0303, and Vladosiya for testing the round and improving tasks.
Good luck and have fun!
UPD Editorial
Really 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 &
Virtual Contest
For 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.
READ ALL THE PROBLEM SET.
READ ALL OF 'em.
THE PROBLEMS ARE VERY NEAT AND YOU WILL ENJOY.
Hopefully this round will be great.
THE 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...
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!
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
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
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
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
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
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 :)
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!
I 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
READ 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 ^^
How to solve problem D ?
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.net/contest/1560/submission/126327050
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.
Or 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
Mine Backtracking passed the Pretests , you can have a look if you want .
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
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
— 126353303Can 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.net/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
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_85
Posting video solution during the contest which is violating Codeforces T&C Policy
The link to the Video solution
good round
There is no sense of taking the video down now -_-
You just took away some hard working guys actual standing from them
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.
+
Can anyone find a test case for my F1 solution 126364100 it failed in pretest 2 |_|
Check this:
The output should be
555
instead of556
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.
This 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.net/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.pdf
Deleted.
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.
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 .
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.net/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.
your solution runs in $$$O(log \space k)$$$
Mine runs in O(1) 126374450
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
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 :'(
I'd like to report a suspicious hacking attempt:
https://codeforces.net/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.net/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.net/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.net/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
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://codeforces.net/contest/1560/submission/126382347 see k==122112 https://codeforces.net/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.net/contest/1560/submission/126364309 see K==99 && n==989891
Fourth instance. Again same user: abhishek_kira hacking ash_cp. https://codeforces.net/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.net/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
Thanks to this round! Enjoy this round very much! :)
...
Contest NAME Should be CodeForces MATH Round(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.
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.
Why unrated?
When will the ratings be updated?
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.
Great Round! Thanks!