Привет, Codeforces!
<almost-copy-pasted-part>
Привет! В 10.04.2021 17:35 (Московское время) начнётся Codeforces Round #713 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 7 задач. Задачи подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше, могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы будем расстроены, если у многих попадают решения после окончания контеста.
Вам будет предложено 7 задач и 2 часа на их решение.
Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше. Независимо от того, являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Задачи на этот раунд были придуманы MikeMirzayanov, Supermagzzz, Stepavly и sodafago.
Спасибо Gassa, darkkcyan, bfs.07, Tzak, songsinger, Mukundan314, iankury, drunya, sodafago, ChOmPs, Programmer, Khairy, IITianUG, Rox за помощь в тестировании раунда!
Спасибо MikeMirzayanov за платформы и координацию нашей работы. Удачи!
</almost-copy-pasted-part>
UPD : sorry
And why exactly you gave this guy so many negative reviews?
This is the third time I've seen the same meme in announcement blogs
Yeah I have seen it before too
is it only me who see only this announcement in russian and rest are in english?
UPD : Now it is fine for everyone :)
No announcement is in russian
from today all indian coders have a big problem wheather to give codeforces round or to watch IPL
Ofc codeforces's contests!!
Any sane person would prefer the former one.
i know that is just a joke
no
Clashing with Codejam Round 1A :(
I think Everyone Love to see it :)
Yep, my mistake, Sorry!
I wish i would solve atleast 3 to 4 problems in this contest
me too !!
Good luck to all
should be rating and not rank (rank may increase/decrease).
same for rating, it should be !(entropy)
After a long time,I've got my focus back & feeling the same excitement I was used to feel.Hoping the contest will end smoothly.Good luck to me, Codeforces and all. :-) (Thinking,what will happen if Codeforces have an emoji that express excitement levels? :3)
It's sad that I can't participate in this Div. 3 because of my courses...
Maybe I'll participate in the Div. 2 tomorrow, but I'm not quite sure yet. Maybe I will be absent in CF contest for a long time...
btw, wish me good luck for my senior high school entrance examination QAQ
Best of Luck!!!
.
Thanks very much :)
aboba
first time doing contest.... it's hard for me....(cry....:<)
This was the lowest division and in my opinion, the problems were easier than other Div3 contests. I'm not saying this to discourage you but to give you advice. Maybe codeforces is a little too hard to start with. You can learn the basics from this website (https://www.pbinfo.ro/). It's a website from my country which takes you from zero to hero (or at least doing the first 2-3 problems in Div2 in less than 1 year, haha) You only have to translate the page to English when you enter the site. Good luck with your coding journey! I hope I gave some positive thoughts!
dont listen to alexadru7, just solve 800s instead, and if those are still too hard, do leetcode (but they shouldn't be that hard)
Thanks for the great round!
Too much implementation :(
Please someone give idea for Problem E. Thanks in advance!!
First take the at least number if l to r difference is 3 then take the number 1 2 3 if its greater than s then answer must be -1. other wise try to replace every number with large unused number as if sum of those number not exceed s. if sum==s you find the result.
implementation
you_ create new array have size = r-l+1. make array from 1 to r-l+1. add 1 to arr[pos]._ _You start with pos = size — 1. if arr[pos] == pos then pos--
Here $$$sum(x)$$$ denote sum of $$$1, 2, 3, ..., x$$$. Let $$$len=(r-l+1)$$$. A solution exists if and only if $$$s>=sum(len)$$$ && $$$s<=sum(n)-sum(n-len)$$$. Now to simulate the process, take numbers from $$$1$$$ to $$$len$$$ in an array (arr). And take numbers from $$$len+1$$$ to $$$n$$$ in a set (st). Let's denote $$$left$$$ as the sum remaining i.e. $$$left = s - sum(len)$$$. Now, you can start from last element of array do this while $$$left>0$$$.
Once you have got arr with sum s, you can add remaining elements at other positions. see my submission
I can't tell if I've gotten better, or if this round was just easier :/
Can someone help me in solving problem E?? I tried by using no from 1 to x-2(where x = r-l+1) whose sum will be equal to sum = (1+2+3+...+x-2), and found two no whose sum was equal to s — sum. I don't know the proof of this method. Someone kindly help.
Here's an example for n = 10, l = 3, r = 7, and s = 21.
We want to find the numbers that will be in the sum. First we try:
1 2 3 4 5 / 2 3 4 5 6 / ... 6 7 8 9 10
Then find the two sums that s is in between.
Over here, it is 2 3 4 5 6 and 3 4 5 6 7.
Now, since 3 4 5 6 7 is too large, we need to decrement some of the numbers one by one.
Since 25 — 21 = 4, we decrement 4 of the numbers, and to ensure no collisions occur we decrement 3, 4, 5, 6.
So the numbers included in the sum are 2 3 4 5 7.
Now, just put these numbers so that they occupy positions 3 ... 7.
LOL, ignore.
I'm curious what the intended $$$O(n ^ 3)$$$ solution to E was, there is actually a pretty nice solution to that can be made to run in $$$O(n)$$$.
For the subarray $$$[l, r]$$$, if a solution exists, then there always exists a solution of the form:
$$$1, 2, \ldots, i, j, k, k + 1, \ldots n$$$, where $$$i \lt j \lt k$$$.
(We can always shift terms equivalently left / right to reach this for some $$$i$$$ and $$$k$$$ from any valid solution)
Since size is fixed, $$$k$$$ also depends only on $$$i$$$. So we can just iterate over $$$i$$$, calculate the sums of $$$1 \ldots i$$$ and $$$k \ldots n$$$ and then check if the $$$i \lt s - sum \lt k$$$.
I implemented it in $$$O(n ^ 2)$$$ during contest by trivially iterating to calculate sums in $$$O(n)$$$ time for each iteration, but it can be done in $$$O(1)$$$ time per iteration using prefix sums or summation identities.
I did not understand from the statement k also depends on i.Can you please elaborate as to what you have taken as i and c and k
Sorry I meant $$$s$$$, not $$$c$$$, got confused between the characters representing the needed values in different questions.
So we want to select $$$r - l + 1$$$ values, right?
So if I know that I'm taking $$$i$$$ values at the start $$$(1, 2, \ldots, i)$$$, and I'm going to select a single number later as $$$j$$$, then I want to select $$$(r - l + 1) - (i + 1)$$$ values for the part $$$(k, k + 1, \ldots, n)$$$. So we can write $$$k$$$ completely in terms of $$$i$$$ as $$$n - ((r - l + 1) - (i + 1))$$$
E was apparently available on stackoverflow https://stackoverflow.com/questions/46296588/distinct-n-numbers-so-that-sum-equals-to-n
I didn't read sum of $$$n$$$ over all testcase is $$$500$$$ and took a lot of time to solve in $$$O(nlogn)$$$. About your intended solution $$$O(n^3)$$$ I think we can solved it like $$$0-1$$$ Knapsack. Since sum $$$s<=n(n+1)/2$$$
I think Blog should be update Cz it div3 : do not have a point of 1900 or higher in the rating.
it should be: do not have a point of 1600 or higher in the rating.
UPD: It's my mistake :)
no
Thats for trusted vs untrusted standings, not the rated part. Basically what it means is that if someone has peak rating $$$\geq 1900$$$, even if their current rating is $$$\lt 1600$$$, they won't appear in the official standings. Basically its meant to stop people from smurfing to specialist to appear at the top of the official standings of a Div3.
Was the intended solution for problem F is DP ?
I also think so. but it's not dp. you_ create new array have size = r-l+1. make array from 1 to r-l+1. add 1 to arr[pos]. _You start with pos = size — 1. if arr[pos] == pos then pos--.
problem F dude. I think you are talking abt problem E.
oh. so sorry
you can prove that in the optimal solution,you will spend minimal days reaching a position then stop and only earn tugriks on that position until you pass c,so iterate over which position you stop at
hey, can you please share your solution? I thought almost the same but guess I missed some corner case.
my sol is the same as editorial
Funny thing, i thought that but couldnt get it to work
I don't think so. It can be solved by using Greedy.
Assume Polycarp last at position i, then for position before i, upgrade to next position as soon as possible will be the best way.
My approach was array day[i] carries the number of days to reach position i and the rem[i] the number of money i start with at position i
then i get the minimum of days[i] + ceil(( c — rem[i]) /arr[i])
i really don't know if it consider dp or not
can problem E solved by knapsack?
I think so, but the problem is that you should consider amount of taken items, it is fixed
I get AC with greedy
Maybe, but if so its tougher than other solutions in my opinion. I thought about this at first, but the best state I could come up with was $$$dp[\text{current number(1 to n)}][\text{count of taken}][\text{sum of taken}] = 1 \text{ if it is possible}$$$, which is $$$O(n ^ 4)$$$. I can't see any trivial way to reduce the state.
what do you mean by count of taken?
He meant amount of numbers used, cuz it should be always fixed
If it's a boolean knapsack it can be optimized using bitsets I guess, so solution might become N^4 / 64
Oh yeah, $$$dp[\text{current}][\text{count}][\text{sum}]$$$ will update $$$dp[\text{current}][\text{count + 1}][\text{sum + current}]$$$, so it can be performed in blocks of 64 elements using an $$$OR$$$ on the bitset. If you consider the extra constant factor of $$$\frac{1}{2}$$$ from sum, this will take $$$\frac{N^4}{128}$$$ or around $$$5 \times 10^8$$$ operations, which is sketchy but possible for 2 seconds I guess. However its obviously not the intended, and based on the editorial I think it was just set to $$$n = 500$$$ to allow less optimized solutions to pass.
Yeah :p
A great Contest！ Although I spent lots of time on problem D&G so that I couldn't finish this. :(
I refuse to believe that this is your first account. Also wtf is this ??
Who else ignored the fact that the coordinates for B were for rectangles instead of squares
Every square is a rectangle!
Every rectangle is not a square!
So if your solutions is for squares instead of rectangles , it should still work ryt?
No. It only works for all squares, not all rectangles are squares
not all the cases allow him to make square
Despair is when you fail to fit a problem in time-limit, only to realize later that the reason in long long int.
TLE: https://codeforces.me/contest/1512/submission/112546490 AC: https://codeforces.me/contest/1512/submission/112563646
Only if the time-limit was 3 seconds :(
Despair is when you fail to fit a solution in time-limit, only to realize post-contest that the bottleneck is '64-bit int'.
TLE: https://codeforces.me/contest/1512/submission/112546490
AC: https://codeforces.me/contest/1512/submission/112563646
Only if the time-limit were 3 seconds :(
Yeah TL was super tight, my first submission with 64 bit integers ran in 1980ms, after replacing it with 32 bit ints it ran in around 1s.
The ranklist is cyclically shifting started from Geothermal and it will end to him LOL.
Mission successful !! :)
Why is everyone's A failing on the top of the standings?
Invalid inputs are passing as hacks. I think the validator doesn't have a check for 1 different element.
I submitted
and got successful hack.
Oh crap , Supermagzzz ... Can you look into this
1
3
1 1 1
Is good, but it can be better! :v
1
4
1 1 2 2
EDIT: VALIDATOR DOESN'T CHECK THE 1 DIFFERENT ELEMENT PROPERTY
Whats the hack case on A?
Also how is this idea incorrect:
The different element is either the smallest or the largest element of the array, so we can just check one of them.
HackForces
Div3-A, there's probably an error in the input checker.
But I have successfully hacked my own submissions(#112521962) in the following case.
1
3
1 2 3
Yup, hacked someone with this case as well. Seems like validator doesn't actually check that property. Should be fixed fairly soon.
wtf. Why everyone is getting hacked?
I think setters should again write a correct validator in problem A, invalid test cases are showing hacked in A.
[deleted]
Uh, are you guys going to fix the invalid test case for A. It's allowing many people to be hacked and lose easy rating.
we are not going to lose rating lmao. I don't know if you are delusioned or you are joking it's most probably the latter.
It seems that a wrong validator was written for Problem A.
People are using invalid hacks on problem A by using
as input, can anyone please check it
Please tell me why my B is wrong!
112540024
[Edit] Thanks lazy_and_slow Thanks a lot for taking the trouble. Appreciated!
you have made a mistake in your first_y and second_y points in the code. I corrected it (commented on the line with mistake). 112571015
This is most probably an unecessary comment but please do make sure to not allow incorrect (most probably TLEd out solutions for A to get accepted) upon re-judging
Could you help me with problem C please? I uploaded a solution but it failed. In one of the tests it should print 100001101100001 or something like this, but prints -1 instead.
your solution fails on this test
after the first iteration, your string will be
0?00???0, which is incorrect, since these new zeros must be next to the already existing zeros. to fix this, you can first process the pairs about which it is already obvious which character should be set (pairs 1?, ?1, 0?, ?0), and then the remaining ones (which consist only of ?) 112623883Thanks!
The input validator of Problem G is also wrong
I use this testcase and successful hack
This is ridiculous, not only problem A, but problem G is also broken... why does it allow inputs bigger than 10^7?
Can anyone also check G validator? I got hacked with RE and it seems kinda strange for me...
I got hacked in G for a solution which I believe can't be hacked , hey CF correct your test case validators
Hackerforces :(
Today people like me (Newbie) tried to hack GEOTHERMAL(I.G.M) solutons :):)
Everyone Problem A XD
Could anyone tell me why my submission for D 112517759 was incorrect (hacked)? I'd appreciate it, thanks! UPD: Thanks to LastDance_NotLastOfMe for clarifying! Really appreciate it.
overflow b_i <= 10^9 & n <= 10 ^ 5 worst case : Sum <= 10^14
Lol got to about rank 298 before A and G hacks were fixed. GG.
why hacks just clean up and not make them wrong?
Can the validator for G please be checked? Thanks
Sorry to say but the level of Div3 is getting down day by day. We all saw what happened today. Moreover, problem G is just copied. Original G problem . If you just copied, give some credit to the owner at least. We really enjoyed Div3's that were organized by vovuh. I don't have any problem with the recent authors and I appreciate their hard work, but please maintain the level of Div3, as many of us enjoy giving Div3 more than much other contest.
I have been debugging my G since it got hacked.
Keep posting good memes like this :)
bro, I hope you don't mind :)
I didn't. That was really a good one. Keep posting good memes (it's hard to find them).
Meanwhile Problem A after today's Div3
Edit — Those who don't know, most of the solutions were hacked by invalid Test Cases. It's fixed now. Thanks Mike ;)
So much hack unhack , that much high numbers of submissions on problems , Bug in the Problem A & Codeforces | #WeWantUnrated
Why? Because you couldn't perform well enough?
Hello! Because of mistakes in some validators I reverted all hacks and rejudged solutions. Sorry for the issue. Fortunately, this did not affect the round itself in any way. Not a single participant was hurt!
Will these real successful hacks which is ignored now be run again?
After the rejudge of problem G, my solution got TLE on test 5. On submitting the same code in practice, it got AC, and test 5 ran in 1325 ms. Is there any reason for this inconsistency, because it may have affected other participants too.
Same happens to me.
Same for me my solution passed in 1650 ms in the contest but after rejudge it TLE on the 1st test. On submitting the same code it got accepted now.
TLE : 112502445, Accepted : 112582502
The same happened with my code. It's giving tle on 3rd test case. when I submitted it again it got ac.
My effort of two hours is gone. T_T
Sorry for it. It would be not easy to rejudge hacks properly. But you can uphack all solutions which weren't hacked yet )
Is this contest unrated? I haven't received any rating yet
Opening hacking is not over yet.
my solution got hacked , now will it effect my ratings?
how to know it got hacked ?
you can check your submissions
Though F is easier than G, for the first 1 1/2 hours during the contest there are more accepted submissions for G than F. Why is that?
The relative length of problem Statement of F vs G probably. Plus I think G wasn't that hard compared to F. The time limit was rather tooooo tight for G.
G is fairly standard if you know the property about sum of divisors (or can obtain it from the property about number of divisors), whereas F actually takes a few minutes to think about the specifics.
Also 5-6 top participants solved G early in the round, meaning it had more solves than C or D. So several other participants (including me) just switched to trying G after solving B thinking it was significantly easier based on the solve count, which led to a positive feedback loop.
My solution for problem g is giving tle .however when i submitted it again it is getting accepted. How could it be possible?
Many of problem G accepted solutions got TLE in pretest after rejudge. G needs to rejudge again with proper balance. Thanks.
During the contest, my solution for D was Accepted. Now it is a TLE. I am tired of changing my Java solutions to use fast I/O. Are these I/O problems or algorithm problems?
Yes, in this case, seeing 1860 ms (with 2 sec limit), I probably should have changed it, especially because I had time to do it. For instance, my G passed only after I changed the way I printed the output. Nothing else. And then I saw D's time and thought "Screw that, I am not changing it".
Well, it sounds like it is a part of the competition. And yes, I go through this every other contest. For instance, it is a common knowledge that you want to use Long[] instead of Integer[] in Java when they need to be sorted. Why?
I think that having an efficient I/O should never be a goal for these contests. If it is, please remove "slow" languages, so we (the users of said languages) can either skip the contest or try to compete on equal grounds by coding in languages we are not familiar with.
Each participant has the right to choose the language that he likes. Together with all its pros and cons. Yes, Java runs a little slower on average, but it has better static analysis in the IDE. It is quite typical for IT tasks that the tool is chosen for the task. And yes, I'm sure it's not a bad thing that sometimes you encounter purely programming difficulties. Understanding that not all ways to read or write data are the same is helpful. In particular, it is important to understand the basics of buffering. Specifically, in your case, knowing the standard library of the language in which you write is also useful. You are using Arrays.sort, but not reading the documentation. Read it finally.
Thanks for the response. All valid points, sorry for venting out.
New here, how long does it take for the ratings to be updated ?
for div3 and educational rounds around 12-14 hours
But, I think it should be updated before the new contest Div 2 today.
question g needs to be rejudged. Many of the solutions which are getting tle getting accepted on resubmitting. Even on 1300 ms.
Yes , the code I submitted yesterday got AC . Today it showed TLE on testcase 5. A Few moments later TLE on testcase 3. Submitted the same code just now in Practice — AC. Admins, please look into this.
My submission for Problem D passed all the pretests yesterday even though I had used int instead of long long.
Can finally say that the pretests should have been stronger ;)
int
long long
It was obvious in the question that you had to use long long, if n==2e5 and you have permutation of that length, then the sum would more than 2e10 which can't be scored in int, which is basically what you had in the B array
That's not the point. The pretest should obviously have some counter cases for int-solutions.
I agree that it was an avoidable mistake on my part; but the thing is that if I had got an overflow error while the contest was still running, I would have been able to fix it in a moment and wouldn't have got the WA verdict that I got around 12 hours later.
Had the pretests been a little stronger, I wouldn't have missed out on a point because of something as silly as the mistake that I made...
If we could not solve a problem and got 4 wrong submissions than penalty of 40 minutes extra will be added?
NO, You will get penalty only after you get AC
В пятой задача можно было еще трехмерное дп заюзать, а в четвертой доказать, что только 2 наибольших числа подходят в качестве суммы элементов массива a.
I am a newbie . When will the rating be updated ?. This is my first contest. Anyone pls reply
it should be updated very soon. you can see your rating changes by cf predictor extension
Thank you for the round! The tasks were very interesting.
I refreshed the official standings table (after the open hacking phase finished), and the rankings are still changing. What is the reason behind this?
Hello MikeMirzayanov I just received this message on my mail. Attention!
Your solution 112492155 for the problem 1512B significantly coincides with solutions swagsy/112482200, Sayskar500/112492155. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
Sorry to say but I have no contact with the above mentioned user and I can clearly state that we have had the same logic (after visiting the guy's profile and seeing his/her code for question B) but there was no conversation or copy of code in betweeen us. I had received a similar message 5 months ago but that time I was not aware what the warning was about (also the user was different) otherwise I would have reported that time itself. Kindly mark my submissions as correct.
If I had any intensions to copy I would have copied solutions for all queestions. It's not neccessary that if two people have the same intuition/logic for a question they have copied it. Please kindly look into this that it doesn't happen. And I again mention I don't know that guy personally._
Sorry MikeMirzayanov But I don't have any super complex template/snippet in my codes. I prefer writting simple and clean code; which is why there is always a chance that my code may match similar to anyone else's code.
I didn't wanted to ping you 2 times but please kindly look into other factors while checking for plagiarism. Like if the 2 people had the same code for others questions or not.
Suppose my code for A and C are not at all similar to that of the user mentioned above. So how did I solve them if I had to ask for solution for B?
hey guys, java code for problem D is giving tle in test case 17 although it's linear time complexity, can anybody explain why??
Arrays.sort() internally uses quick sort as a sorting alogrithm thus in worst cases if pivots are not choosen optimally complexity will be O(n^2), so try to use Collections.sort() instead, which uses merge sort.
thanks bro!!
Top round!!!
Hello MikeMirzayanov , I just received this message
Your solution 112505064 for the problem 1512D significantly coincides with solutions ritesh1340/112500594, floki/112505064. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
I was surprised to get this message, since I did not use ideone.com or any common source. I just used my local text editor (VS Code) and my own code and templates. I don't have any contact with the user ritesh1340. I'm certain this is a complete coincidence and we just happened to think of the same straightforward approach.
Please kindly fix this issue and thank you
+1
After receiving the message, I actually went to see, if my code was similar to floki's code Or not. I agree to the fact that the codes are really very very similar.
But, what else would I code? That is such a straight forward approach, and a straight forward implementation. Plus, as far as using ideone Or something similar is concerned,I didn't use it.
I would request MikeMirzayanov and Stepavly to please look into this
Thanks
Is there anyone who got in Problem F's second test WA because 8891st number differs and then could manage to find the issue and get AC ?
yes you can see my code actually u might be missing the case where you dont have to earn at a particular day and the balance you have is sufficient to move to next position
thanks a lot, I didnt think about that
[Deleted]
For problem G: My submission using long long: https://codeforces.me/contest/1512/submission/112652041
My submission using int: https://codeforces.me/contest/1512/submission/112651472
Using int is taking noticeably less time than using long long.
Can anyone explain, Why long long is slower than int?
I don't know why I got TLE for nlog(n) submission in D.
Please consider to rejudge my solution of problem G
Last 713 div3
Same solution one is ac and one is tle
TLE Solution : https://codeforces.me/contest/1512/submission/112528244
Accepted Solution : https://codeforces.me/contest/1512/submission/112621917
When contest is running my problem got ac verdict all the 9 test case
And i have a screen shot also
And when contest and rejudge the
All solution g that time my solution got tle
In 7th test case, . But contest time
Show all the 9 test case ac
And same solution i submit now
It's show ac verdict
Please rejudge my solution MikeMirzayanov
Almost the same thing happened to me also.
TLE Solution — https://codeforces.me/contest/1512/submission/112541255 (Which was ac in the running contest)
After contest AC solution — https://codeforces.me/contest/1512/submission/112611320
Both codes are exactly the same.
This Div.3 is too easy...Hope a harder contest!