Привет! В 18.11.2022 17:35 (Московское время) начнётся Codeforces Round 834 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.
Вам будет предложено 6-8 задач и 2 часа 15 минут на их решение.
Штраф за неверную попытку в этом раунде будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацией нашей работы. Задачи были придуманы и написаны командой Университета ИТМО: MikeMirzayanov, myav, Gol_D, Aris, Gornak40, senjougaharin и Vladosiya.
Также большое спасибо: mumumucoder, Enkognit, orloffm, TeaTime, ilyamzy, Olympia, moonveil, 74TrAkToR, molney, elseecay, bigDuck, Nickir, Be_dos, OAleksa за тестирование раунда и весьма полезные замечания. Список тестеров будет пополняться.
Всем удачи!
UPD: Разбор
Div 3 after a long time...
YEAHHH div 3 is the best opportunity to become a specialist.. ;D
Yeah
You will become unrated.
Thats why y solve only 1 problem on this easiest contest
why is it so? I too solved one. But didn't get any rating?
y get ratinf after 12 hours of hacks of solutions
Let's see.
As a tester give me contribution
As a not tester, I gave you contribution
As a not tester, I gave you contribution too :)
As a participant, I gave you contribution too.
:))
As a contestant, I gave you contribution too.
:/
Negative contribution given boy....
OMG DIV 3! HOPING FOR GLACEON COLOR!!! never, Leafeon. is the best :sunglasses:
Good luck!
try flareon color
Omg blue round
Div.3! Hope to Specialist!
Best of Luck!
Why?
because he is a miser
I am not.
You will become unrated.
Aleksamaster is the best tester , Oro najjaki
Aleksamaster is the best tester , Oro najjaki
Among us
End term Exams and contest on same day :(... I guess I'll miss my becoming pupil chance ..
Best of luck to everyone writing the contest!
GL
I swear, this time I am going to change color!
Delta will +500.
Delta of delta will -99999999
Let's see.
all the best!!!
OMG Blue Round
OMG Blue Round
Time to change my rating.
Hope not by negative delta.
Sure You will get +ve delta.
We will see. It will be like "swap(anuj_1234.rating, MohamedEmara.rating);"
Best of Luck!
It will -99999999 for you.
Спасибо bigDuck за тестирование.
Ку плэчере <3
I relate!
I will try my best to become expert.Only need 20 scores,best wishes.
Div 3 is the best opportunity to reach expert
Sure you will be expert.
Bro,why you say that?I just want to be stronger.Hope you can be expert too.
You will become unrated.
gay
really be an expert.thank you all.
OMG div 3 , hoping for big +ve delta
Never miss the rounds that written by ITMO University team
True. They always have interesting problems.
where I will get the contest link
Go to the contest section Codeforces page. Find round 834 and register before the contest
Good luck for everyone . Do your best to be the best !!
I didn't compete with you a month ago, so i am in a hopeless situation, what should i do?
It would be nice to finally fix language selector issue and remove excessive use of flags.
Sources with supporting arguments:
Codeforces Language Picker -- chrome extension to see how fixed codeforces language picker would look like.
Please support the initiative and stop reinforcing poor UX practices.
Good luck everyone :)
Goof luck everyone!!!
Hope to become an Expert.
nice performance
Congratulations!
Thanks!
What if it is my 5th rated round? Will I become trusted participant if I will solve a problem in it?
great
I hope to become a specialist soon
This round seems to be a more interesting one:)
How to solve G?
I used a greedy idea:
...for every a[i] place the max unused number from the range (1 ... a[i] — 1) before it, if no number is available in the range, then it's impossible.
However, I haven't proved this idea in the contest, so I'm not sure about the systests. If someone else who have proved it can mention it here, then it would be helpful.
Why max unused? We want the minimal permutation, so should not we place minimum in the range?
Notice that I am iterating from index N to 1, so using the maximum ones at higher indices is more optimal than using the minimum ones.
It seems logical...
Everytime you pick the maximum possible choice and you ignore smaller values which have higher chances of being used in another pair than the max value ($$$1$$$ is smaller than $$$n-1$$$ values, $$$2$$$ is smaller than $$$n-2$$$ values, and so forth...)
So even if it can be used somewhere else also, no problem because there is another smaller value you can put there (and if there isn't, it's impossible to construct the permutation).
Getting the max guarantees the smallest permutation also.
I used a Maximum Segment Tree.
int[] answer
of lengthn
which will store our final permutation. On every odd position(0 based indexing) fill the elements ofint[] b
. Because we want minimum number to be in front position, so it makes sense to keep the maximum element on the second position.answer
array. Now we iterate integers from n to 1 and check if its not present in answer, find the right_most element in answers array which is less than this current number. So we can safely place this number on left hand side of the found number. Now delete this number. This type of operations can be done by segment trees.My solution is not clean as wrote in hurry in contest and its a newbie's code. My AC 181520850
If you are a braindead grey (like me) and never thought to solve the problem backward, you can also binary search on a lazy add/min segtree.
https://mirror.codeforces.com/contest/1759/submission/181510473
Solution for G:
From $$$i=n/2 \space to \space1$$$,for each $$$b[i]$$$,find $$$max(x)(x<b[i],x≠b[j])$$$ .
Proof:
Note $$$X=max(x)(x<b[i],x≠b[j])$$$.
Consider $$$"... Y\space b[j] ... X\space b[i] ..."$$$ and $$$"... X \space b[j] ... Y\space b[i] ..."$$$.Because $$$X$$$ is the largest number less than $$$b[i]$$$,we get $$$X>Y$$$,the former has a smaller lexicographical order.
Yeah It is so easy compare to other problems:(
What was the correct approach to solve problem C?
You can consider cases like: a == b then answer is 0 distance between a and b is >= x then answer is 1 distance between a and l or a and r is more then x and then distance from that end is more then x ( to the b ) then the answer is 2 and the last case is to make the deistance to one of the endpoints equal to at least x, and this just adds 1 to the previous case, so the answer is 3 in the last case, if you can't do that than the answer is -1
Check if ans==0
If possible use 1 step, else
if possible go to left or right end, then to b, else
if possible go to left end then right end, or to right end then left end, then to b.
else not possible.
I felt problem D to be tougher than E & G :|
Me the same. I wasted too much time in D and then found out E was much easier to figure out. But it was too late... :(
Can someone tell me what's wrong in my submission of D
I am not sure what is your code doing. But i found a test case:
Thanks!
Can any one tell, what would be the difficulty level for the problem D?
My estimation would be $$$1300$$$.
can someone explain problem c and d
My solution for D:
k zeros at the end of a number means that this number can be represented as
10^k*a
, where a is some number.10 = 2 * 5
, therefore, in the answer we need to maximize the number of pairs{2, 5}
1) Decompose n into prime factors and count the number of 2 (let it be q2) and 5 (let it be q5). If
q5 > q2
, then we need to addq5 - q2
twos in the price increase coefficient. Ifq2 > q5
, then q2 — q5 fives. Ifq2 == q5
, it means that we cannot "collect" tens from two numbers and add a zero to the end of the answer.2) After that, I started picking up a number from [1; m]. We need as many 10 as possible in the answer multipliers, so I multiply the number (2 or 5) that I lacked to create pairs with multipliers of the number n,
abs(q5 - q2)
times by itself.tmp = (q5 > q2 ? 2 : 5)^abs(q5 - q2)
3) Then, I need to maximize the quantity of 10 at answer and, if there is solutions with the same number of zeros, need to get maximum. So we can increase
tmp
variable. To increase the number of tens, you need a number that can be represented as10^k * a
. This is easy to do if you take a digit of the highest digit and add to it(the length of the number - 1)
zeros. For example, whenm = 21345
, you need to take20000
. So we have to do something like this:4) When working with the
tmp
variable, it is necessary not to forget that it cannot be more thanm
, so it is necessary to set conditions thattmp <= m
everywhere you are increasingtmp
.The answer is
n * tmp
orn * m
if there isn't solutions with zeros at the end.My code return negative value in problem D but i am doing only multiplication in my code. can someone please help me with that
here is my submission 181501309
When you are multiplying it's crossing the limit for integers. Try with long integers
What you are facing is integer overflow, try using 64-bit integers.
That is something you will often have to care about.
how to solve F?
Observation 1. The maximum answer is $$$p-1$$$, One case where this happens is where the number is a single digit.
Observation 2. A full carry across one or several digits happens only once at most.
Now think of it like this. How many steps do we need when our number is 0? That's $$$p-1$$$. Now, how many steps do we need when we have a few more digits existing in the number, smaller than the last digit? Might be smaller than that, but we may still have to run a full cycle. For this reason, we manage two variables, $$$\mathbf{pp}$$$ and $$$\mathbf{pk}$$$. $$$\mathbf{pp}$$$ is the smallest number connected as a continuous group with $$$p$$$, $$$\mathbf{pk}$$$ is the same but it is for the last digit. These two variables serve as boundaries. To be precise, $$$\mathbf{pp}$$$ serves as the boundary before the carry, $$$\mathbf{pk}$$$ serves as a boundary after the carry. So, you should be very well able to case-work with $$$\mathbf{pk}$$$ on whether we need a carry or not. Now the rest is just implementing the carry, and fiddling with these two variables (and the last digit).
Solution for F:
Note $$$k=a[n]$$$,consider $$$k->k+1->...$$$
Case1:
$$$k->k+1->...->p-t$$$
In this case, there is no carry bit.$$$0,1,..,k-1$$$ must appear in $$$a[]$$$.
$$$p-t$$$ is the largest number that does not appear in $$$a[]$$$.
Case2:
$$$k->k+1->...->p-1->0->...->k-t$$$
In this case, you should recalculate $$$a[]$$$(consider carry bit),note it as $$$b[]$$$.
$$$k-t$$$ is the largest number that does not appear in $$$a[]$$$ and $$$b[]$$$.
Accidentally hacked jiangly submission with Ticket 16429 from CF Stress :)
coooooool!
jiangly's algorithm: the greatest element of an array is always the last element.
How to solve D ?? Made me drop the contest..
Just find out how many 2 and 5 you get from m and (1<=x<=n) if(x==1) answer will be m*n; otherwise m*x;
Sorry can you elaborate ??
You'll get $$$n$$$ 0's in the suffix of the answer if the factorization of $$$n * k$$$ ($$$1<=k<=m$$$) contains atleast n fives and n twos. Greedily check if you can get $$$x$$$ zeroes in the suffix of the answer for every x uptill about 18 should suffice (since n * m is atmost 1e18).
For example, if you want $$$x=5$$$ and $$$n$$$ contains $$$4$$$ 5s and $$$3$$$ 2s in it's factorization. Then you require such a k that has atleast $$$x-4$$$ 5s and $$$x-2$$$ 2s
Could someone please explain why my code for E fails on test case 3? https://mirror.codeforces.com/contest/1759/submission/181515762
I have used the following approach, there may be at most 3 orders of choosing potions whenever we encounter an astronaut with health greater than the humanoid's health, and they will be GBG BGG GGB
The final answer should be the maximum of the number of astronauts we can defeat using one of the three orders. Please point out the logical inconsistency in my approach or provide an example where my code fails.
(the recursive way to solve this did strike my mind, but I decided to do it this way as it seemed simpler)
As the humanoid can gain more health as it consumes an astronaut, you should iterate until you cannot consume an astronaut anymore instead of binary search the position at the beginning. After that you will drink a potion then try again that strategy. There are 3 ways to drink potion (2,2,3), (3,2,2) and (2,3,2) so just try all of them.
brb gonna go slap myself a couple hundred times.
As I mentioned in the comment, I have tried all three ways BGG GBG GGB.
NeverCompromise I think you can look at the submission of mine https://mirror.codeforces.com/contest/1759/submission/181620640 . Its similar to your approach. I just have done the implementation in the other way which is shorter
Yeah that's a neat way to implement i, I had made a really dumb mistake at the start of my code. Fixed that and got it ac yesterday. Thanks for trying to help anyways.
Can somebody tell me what's wrong with my B code? (Pretest 4 WA)
I figured it out, I thought the original permutation's size can't be over 50, but the problem statement never actually said that, only the found elements can't be more than 50
1759A - Да-да?
Personally to me, it felt more like a div4 round. The maximum difficulty rating for the problems of this contest should be around 1700 or 1800 I guess.
Agree 100%, nitin sir orz
Someone please tell me how the humanoid can absorb the astronaut with power 15 in the case 7 of Problem E. It says that the humanoid can absorb an astronaut with power strictly less humanoid power. It confuses me a lot.
Use blue first.
Oh!!! I think the solution is greedy, which is not valid. I think too simply. Thank you very much !
Take a look at submissions of the rk8 NightSky_Yozora.
Obviously, there are 4 coding styles in his submissions:
Problem A, B, C is solved by the first person;
Problem D by second;
Problem E by third;
Problem F, G by fourth.
it's a violation of the rules, isn't it?
Sir, what about Sneh_Patel_0701 he has cheated in previous rounds too. But didn't get caught. Now he is going to become expert. Is there any punishment for them?
Can someone point out what I may be doing wrong? What edge case I may be missing?
https://mirror.codeforces.com/contest/1759/submission/181520511
you missed else after your last elif
1759D - Make It Round
Greedy approach : We will try to append as many 0's at the end within given constraint How to find it ?
Let's take input examples : 6 11
Now we will build our answer by checking if I append zeros can I get some k such that it falls under constraint, once we can't append 0's we will break loop
How to do it? How to find possible values of k? Well it's easy, we can use some mathematics
Here's my code
Thanks :), You can ask doubt
can u explain little more how exactly u getting logic to finding k?
k = x/gcd(x, n) x goes from 10, 100, 1000, ...
I tried doing this but it was always giving wrong answer in C++ (probably some overflow issues or something like that) but it worked fine in Python
Hi, @djay24 What's your intuition behind (m / k) .?? like, you used k = (11/5)*k, why are you doing so, can you explain.?
Thanks in advance.
1 <= k <= m Initially k is minimum possible value it can take within given constraints So k can take values from k, 2*k, 3*k, 4*k, ... z*k, I have to find such z such that z*k is maximum possible but less than equal to m, so I am multiplying by (m/k) factor... That's why initially k = 5 but after we can see k = 10 is best answer so k = 5*(11/5)
Is there a problem with hacks in problem F? Any hack in this problem still in the waiting process.
Also Some of them give unexpected verdict. MikeMirzayanov
Upd: Hacks still in waiting state after 6 hours problem F hacks
E and G are far far easier than D (did'nt read F yet)
E and G are far far easier than D (did'nt read F yet)
Has anyone solved E with a memorized dp? the recursive approach is very simple but i cant seem to get my head around implementing a dp solution.
What is your state? I had an iterative dp where $$$dp[i][j][k]$$$ denoted the max cost achievable till index $$$i$$$ if you take $$$j$$$ green potions and $$$k$$$ blue potions in total. While transitioning, I tried to take $$$l$$$ green potions and $$$m$$$ green potions in the $$$ith$$$ step. If the cost achievable without taking these $$$l$$$ potions and $$$m$$$ blue potions was greater than $$$a[i]$$$ then I greedily add $$$a[i]/2$$$ to my answer and then multiply by 2 and 3 on the basis of how many $$$l$$$ potions and how many $$$m$$$ potions I took.
Submission
Thanks, makes a lot of sense! i had the same 3 states but had trouble differentiating the cases where the potions were taken before or during the round.
177670435``
````````Please, Who can help me to find out the queetion of problem D. I guess my code's part of maximal price of several possible variants is wrong.because the Checker Log told that expected: '874999993000000000', found: '749999994000000000'.
hello!can i get some help please
guy you... have a mistake in function qpow. Remove
else
, because you should increasea
in every iteration.My feedback to the round authors (just for problems A-D (problems I managed to solve in the contest)):
A: Easy implementation problem, the problem statement could've been written more simply because I needed to look at the examples to understand the problem without spending like 5 minutes. It shouldn't be like that since this is Div.3 A problem.
B: OK problem, nothing else to say.
C: Good problem, even though I don't prefer problems with $$$l,r$$$, and many if statements like this one. I like the problem.
D: Best problem (rating $$$\leq{1400}$$$) along with 1748B - Diverse Substrings in the past few weeks in my opinion. It's always interesting to solve number theory problems.
The feeling when Div. 3 round was more problematic for you than Div. 2 round XD
i have a problem.In problem e ,java,i use the same algorithm to solve this problem,but three different sorting methords(priorityqueue, Collections.sort,Arrays.sort),the first two is accepted,but the third one has TLE.Can anyone figure it out?
Arrays.sort uses a dual-pivot quicksort algorithm. Unfortunately, its worst case time complexity is $$$O(n^2)$$$.
got it
Solutions were already there on YouTube I check the timings. People just copied from there. So unfair
Dont worry,Mike will ban them
Goof luck everyone
can anyone please explain me the approach for problem C? I can't figure it out!
you only have the following options:
1. if
a
is already atb
-> answer is 02. if difference between
a
andb
is >=x
-> answer is 13. from
a
go tol
(if possible), then tob
(if possible) -> answer is 24. from
a
go tor
(if possible), then tob
(if possible) -> answer is 25. from
a
go tol
(if possible), then go tor
(if possible), then tob
(if possible) -> answer is 36. from
a
go tor
(if possible), then go tol
(if possible), then tob
(if possible) -> answer is 37. if none of the above is possible, then answer is -1, otherwise it is the minimum of all the cases
for steps 3-6, we chose either
l
orr
and not any other temperature because its always efficient to use an operation go to the farthest possible index.I like this competition very much. The F and G questions are very simple, which is simpler than the level questions in div2. They do not involve advanced algorithms and data structures, and their meanings are very clear.
i wasn't able to solve F without implicit segment tree with lazy propagation and binary search on it(got MLE 2 times xd)
I remember it was a line segment tree binary, someone did it, maybe you wrote it wrong.
yeah, memory consumption was huge because i didn't use shared ptr or vector, just raw pointers..
Can someone please clarify if it was rated? I participated in the contest and solved A but I was not rated. What are the rules for being rated?
The contest doesn't even show in my contest tab. What is the reason for that? Can someone please clear up the confusion?
The full system test hasn't been completed yet, how can it be rated?
NightSky_Yozora was obviously cheating, plz do something.
Is this contest was rated for participant whose rating < 1000 ??
< 1600
There are still about 40 hacks stuck at "In queue" or "Unexpected verdict" state, despite the fact that the final testing has already been conducted. This is not the first time such a situation arises.
I think that such occasions should be automatically reported to contest managers and, in general, should block the final testing unless fixed.
Why my rating is still not updated until now?
Oh, it's already updated but I didn't noticed it because it shows "unrated". Why?
ALL MY RATINGS SHOWS "UNRATED"!
because you are unrated
Impossible, I solved 2 problems in R833, and I solved 4 in this one. My solutions are not hacked.
everything is possible
Maybe you're right. Evidence
Is this system error?
And why a point is in the year of 1970? Evidence2
i think because you participated in 1 contest that time
Codeforces was founded in 2011(maybe) and I was born in 2010.
maybe you were born in 1970 and you just forgot about it
How possible? And there was nothing called Codeforces then! You can ask MikeMirzayanov for it.
I asked him and he said codeforses was founded in 1920
Now it`s time for the Ultimate Question of life, universe and everything: Is it rated?
At least not now.
All Questions were mathematical as always. No concept used of DSA. Disappointing contest
Mathforces
Apart from D, I don't see how the others are mathematical (don't know about F, since I didn't solve)
Well, D may be a simple math problem, but all other questions are focus on basic algorithm ability. Though I'm a newbie, I think this round is of good quality.
Bruh only D was math
Nice problems! I love the round
I hope that I can be specialist xd
Has this contest turned unrated??? Why the ratings are not updated yet
Wait. But y will get + 47 raiting for this contest
Please update the rating
No
Hello, 2 hours ago I got a message that tells my solution for problem C matches with some other participants. Also, this round will be unrated for me and it shows I am out of competition. My solutions are skipped also.
I checked their submissions and found some similarities in logic and I think this is normal as thousands of people are participating here. But their code writing style and solution for this problem are totally different.
Also, this happened to me for the first time. I don't know what to do! Help me if anyone can! Thanks in advance.
Sorry to hear that. You may send emails to the codeforces official account and provide exact evidence to show you didn't share code with other participants. You may get the round into a rated one finally if you are resonable.
Hope that will help you.
Thanks. Can you give me the email address?``
One contest doesn't mean everything.... Try in next contest.
I have been skiped , i have not cheated , what i should do to prove that
You have been skipped several times. Just admit it and don't cheat again.
noooooo he didn't cheat of course he just keeps getting accidentally skipped /s
When is editorial going to be posted?
I liked this round, would enjoy to read the editorial too.
https://mirror.codeforces.com/contest/1759/submission/182444103 I am Getting Runtime Error in Problem F but not able to find it , It would be great if anyone can help .