Hello Codeforces!
Сейчас проходит зимняя смена ЛКШ (Летней Компьютерной Школы), и мы в составе параллели A+A0 и её преподавателей подготовили полноценный Codeforces Round. Вы можете ознакомиться с предыдущими раундами, подготовленными учениками ЛКШ: Codeforces Round #612, Codeforces Round #530.
Codeforces Round #694 начнётся во 05.01.2021 17:35 (Московское время). В обоих редакциях раунда Вам будет предложено по $$$6$$$ задач на $$$2$$$ часа. Раунд будет рейтинговым для обоих дивизионов.
Задачи раунда были придуманы и подготовлены AliceG, pakhomovee, MadProgrammer, ArtNext, fastmath, IgorI, Kapt, KhB, Hello_zoka, Karabutsa, ligaydima, Mangooste, pelmenner, allvik66 под руководством meshanya, cdkrot, kokokostya, craborac, scanhex.
Мы рады поблагодарить:
300iq за координацию раунда.
MikeMirzayanov за платформы Polygon и Codeforces.
LHiC, budalnik, KAN, Monogon, IaMaNanBord, ld_minh4354, Gauravvv, Vergara за тестирование задач и полезные комментарии.
Мы рекомендуем Вам прочитать условия всех задач. Разбалловка будет объявлена ближе к началу контеста.
Удачи!
Разбалловка будет $$$500 - 750 - 1000 - 1500 - 2000 - 2500$$$ в обоих дивизионах.
Системное тестирование завершено. Спасибо Вам за участие! Мы надеемся, что Вам понравились задачи!
Поздравляем победителей:
Все они решили задачу E (а neal сдал её первым). Задача F оказалась весьма сложной, и никто не смог сдать её за контест.
Div.1 + Div.2 in the title is confusing, cuz it means combined round
:(
del
hello
Ого, очередной раунд от экспертов
Класс, очередной раунд от синих. Спасибо, Майк! А когда будет нормальные авторы раунда?
Ох уж эти синие! Даже не могут согласовать слова в предложении между собой
I like blue! lol
MadProgrammer is the impostor .lol
Among us jokes are too last year bro..
..Making us confused !! Nope, I can check all and make the scenario fool
more formally : Brute force on the writers :D to check if he's blue or not
AliceG Топ!
Really like the blue color theme for this winter round!
coders from the southern hemisphere
:)
AliceG Топ!
Hmmmm, there's something off here
AliceG Топ!
Thank you for another blue round!
AliceG Топ!
AliceG Топ!
At first sight I thought there is a bug ,later realised it's "magic" lol
I am missing monogon.
AliceG Топ!
BLUE
BLUE
AliceG Топ!
Should we change our handle blue in order to participate this contest?
Actually a great Idea !
I cannot guarantee that your color will not remain blue forever
Nevermind, you will be blue after this round!
Blue dress quot I love blue !
Masters of the blue , of course meow will participate .
As a tester, 1-gon commented nothing!!!
new year resolution
BLUEFORCES :D
pelmenner Топ!
Раунды от учеников ЛКШ имеют номера 530, 612, 694 и образуют арифметическую прогрессию. Интересно так и задумано было или просто совпадение?
Я думаю, что так получилось, потому что раунды ЛКШ первые в каждом году, а в каждом году одинаковое число контестов
В каждом году первый раунд — "Hello $NewYear", только в этом что-то пошло не так. Я думаю, просто совпало, хотя разница раз в год сильно помогла этому.
Meanwhile in the standings..
18 "blue" authors and 1 real blue author, press F
1 IMPOSTER AMONG US
noc
Some of us didn't author tasks, but helped with problem & the round preparation
It would be fun if testers were blue too.
As a tester it's probably first time I feel nice about being Blue. Thanks to auth-orz.
Battle of Blue authorcf 693 1st question please help me , on what test case my code fails because I think that my code is right Its humble request thanks in advance
include <bits/stdc++.h>
using namespace std;
long long count(int n){ long long c=0; while(n%2==0){ n=n/2; c++; } return c; }
int main() {
int t; cin >> t; while (t-- > 0) { int w, h; long long n; cin >> w >> h >> n; string s = ""; if (n == 1) { s = "YES"; //continue; } else if (w % 2 == 1 && h % 2 == 1) { s = "NO"; //continue; } else if ((w % 2 == 0 && h % 2 == 1)) { long long x1 = 2*(count(w)); if (x1 >= n) { s = "YES"; } else { s = "NO"; } //continue; } else if ((w % 2 == 1 && h % 2 == 0)) { long long x2 = 2*(count(h)); if (x2 >= n) { s = "YES"; } else { s = "NO"; } //continue; } else { long long a1=2*(count(w)); long long a2=2*(count(h)); if (a1*a2 >= n) { s = "YES"; } else { s = "NO"; } //continue; } cout << s << endl; } return 0;}
wrong place to ask!
colourful standings
hope to be blue color ^^
too much blue
А на сайте ЛКШ ничего не было написано про зимнюю школу, почему?
Лодку не шатайте, пожалуйста.
Is this BLUEFORCES ?
Really like this 'Authors in Blue' theme!!
AliceG Топ!
Власть синим!
much Expertise went into the problems' preparation
I literally freaked out on opening the contest page and seeing this blue brigade in there XD.
The face when I saw all the authors are blue.....
I'm glad all the cyans turned blue this year :D
Are you blue so that you can get girlfriend?
What a coordination among problem setters, All blue looking nyc
how do I cancel my registration from this contest? Does that really matters??
If you do not participate in the contest, it doesn't matter.
Last night I participated in a competition prepared by newbie, and tonight I will participate in a competition where the people who prepare the questions are all export. It is an interesting experience. ^__^
It's not funny in the second time
I hope this round will make me the color I am now,but I'm more likely to turn blue...
Hope you guys do your best.
Authors are playing "among us".
And MadProgrammer is the impostor.
I wish to become blue after this contest!
pog
Once in a Blue moon contest
i wnt psitive contribution please
Then make contribution not begging
why all the writers of this round have changed their id colour to blue? too much symmetry and why blue?
It's just a continuing joke https://mirror.codeforces.com/blog/entry/72809
Топ! Ой... не туда
The comment is hidden because of too negative feedback, click here to view it
good luck on the round guys (:
Roses are red, Violets are blue.
Roses are red.
Violets are blue.
You know there will be a mass cheating.
and MikeMirzayanov knows that,too.
Well, that looks like new year's
BLUE squadGlad to see a blue brigade as problems co-ordinator. Hope to learn something new after this round. :P :))
Last contest I did really terrible so I cheated from my friend to not lose too much rating (I would never gain positive rating change from cheating )
Now I feel really terrible I never cheated before that was just very stupid and I'll never do that again even if I'm going to lose 200 I prefer to stay clean like how I always have been
Glad to see u accepted your mistakes.
I have not cheated in Codeforces but I guess you feel guilty and undeserving of the rating. Also codeforces is not a school exam, there is no obligation to participate, so cheating seems purposeless. Do well this round!
MikeMirzayanov, ban him please
you dont need to make public proclamations like this, just do not cheat.
Please update the scoring distribution??? Less than 1hr is left!!!
Auto comment: topic has been updated by IgorI (previous revision, new revision, compare).
A bit Queue in the submission
Such a long queue :(
It appears that I didn't register (I forgot to) to contest and can't submit, but the UI apparently forgets to tell me that is the case...
P.S. It's ok now
Strange contest!
is there any problem in server because submission taking time
Judging is taking around 5 mins.
Long queue
Long queue
Has to be new record for difficulty gap between C and D in Div2.
the queue is 30 pages long. It's time for an unrated contest. :))
the queue is 30 pages long so it's time for an unrated contest :)
Почему нельзя просто ограничить количество участников, еще вчера сайт подлагивал и была очередь, очевидно было что сервера не справляются, ну куда пихать 22000 человек в один контест?
I think the long queue is because of the weak sample test.
Queue is too long. The round should be unrated.
lol people are asking to unrate the round just because they perform bad.
Queue way too long. Should be unrated
Its taking too much time for judge....
scrolling through the comments while 3rd problem in queue
Problem C was so easy!!! I should have solve that earlier in this contest! :(
This always happens, I debate which one to gamble on and choose the harder one
It would have been really nice if the condition B > 10*C wasn't true. :)
difference between levels of C and D is very much i guess. anyway a good set of problems.thanks for the contest.
Is compilation error supposed to count as a wrong submission????
this is my submission log: https://imgur.com/oLZjnCZ
This is just my submission compared to someone else's on the leaderboard: https://imgur.com/BJZcjKu (if you look at the third person in the picture, they solved at same time as me, but I got 50 less points).
As you can tell, my compilation error cost me -50. Is this supposed to happen?
You got -50 because of double "pretest passed", not because of compilation error
Is that what is supposed to happen? They're both right, so why is that giving -50
Because you basically replaced the previous submission which could contain a bug not caught in pretests. So it is the price for replacement.
I personally don't think that should be -50 but ok. If it passed pretests but you caught something yourself, that's just a problem of pretests being weak, and therefore not your problem that it passed pretests. Nevertheless, it is whatever I did bad anyways. Thanks for clearing up my confusion
After pretest, Codeforces will hold a system test, which will finally decides whether your submission is right or not. The resubmission is the function to avoid FST(Failed System Test), which will cause -50 penalty.
Does this -50 happen for all cf contests? I just want to know for future reference
Yes, as far as I know this is nothing new and is written somewhere in the rules
A submission makes the previous AC submission counting like a failed one. This is for all constests, but not in all contests this results in -50 points. For example in educational rounds you get 5 or 10 points penalty.
You got -50 because of the resubmission
** Placeholder for the picture "me after solving ABC" **
Div2D (Div1B) was amazing!!! The queue was irritating though
what is the solution/hint, dont we just have to find answer for w=0, 1? what is wrong in that
Yes, the answer for all w>=1 will be the same. So you have to look at just 2 cases.
WHat is wrong in this, I stored, for each number, the product of prime factors with odd power taken once in a map. For example, for $$$4, 12, 3, 6$$$ we store them as $$$1, 3, 3, 6$$$ in map. Now key of $$$1$$$ gives already perfect squared, and value of $$$1$$$ in map will give single element count which become perfect square in first second. Now odd values in map will remain odd. Even values will get added to perfect squares component
You maybe missed ans1=max(ans0,ans1) after calculating the answer for 1. This was the mistake i made and my idea is same as yours
actually I mistook the statement of question :-(
For singular elements as
6is in case of[4,12,3,6]I multiplied it with itself to make it a perfect square after first second (facepalm)How to solve it?
Pairs whose parity of powers of prime are same are adjacent
Okay, thanks.
I found it easy and mathy... I solved it by taking square-free part of numbers
Could you please tell me why I am getting TLE? Actually I am never sure about how to use unordered_map without losing performance so if you could give me a few tips about that, that would be helpful.
Submission: 103458851
Variables-
equi[x]: the ultimate value of x once all square elements are removed from it.
equiCount[x]: a map to count occurrence of x
initial: for w = 0, counts the maximum answer for initial setting.
after: for w >= 1, counts the maximum answer once different elements are merged
After looking at problem D (Div 2).In Div2D , 2nd test case after 1st second array becomes [36,36,8000,8000,8000,1] .
Now why is the answer 3 ?
{8000,8000,8000} are adjacent to each other :P
Are 8000 and 1 not adjacent ? lcm/gcd = 8000/1 = 8000 A Perfect Square
Nope, 8000 is not a perfect square
fuck. literally spent half an hour thinking why the hell is the answer not 4
I lost a bit of time there as well — had it been a more obvious non-square-root, time could've been saved.
The problem writers didn't (intentionally) give a lot of hints in this round, for any of the problems — most examples were quite basic and it was left for us to figure out the gotchas.
[8000,8000,8000] — three adjacent elements [1,36,36] — also three
there are 2 sets- [36, 36, 1] ans [8000, 8000, 8000] maximum size of any set is 3
8000 = 2^6 * 5^3
36 = 2^2 * 3^2
1 = 1
So 8000 is adjacent only to 8000.
How to solve D? I noticed, that the answer will be got either on first or second operation of counting the answer, but after that I got stuck.
I was thinking like mapping each element to a number obtained by dividing the largest possible factor as square. Then elements mapped to same element are adjacent, now if the size of group is odd then this group could not be adjacent to any other group in next iterations otherwise such group in next iteration will be merged to other such even number group and group of elements mapped to 1. But not sure as I could not implement it in the time.
$$$a$$$ is adjancet to $$$b$$$ only and only when its power prime divisors have same parity (3 = 2^0 * 3^1, 12 = 2^2 * 3^1 are adjancet).
So all you need is factorize every number and count group by parity of prime powers. Then beauty is largest size of group.
So, was it necessary to keep only different prime divisors? And what about the merging of other adjancet groups?
UPD. Understood it. Thanks a lot.
Merging will be only for group with even size and once as you posted. Then their product is perfect square. Otherwise group will never be changed.
Let's say current group is (3, 12). Their product will be 36 — perfect square. And if group is (3, 12, 27) then their product is 972 = 3^5 * 2^2 (powers have same parity as 3 = 3^1 * 2^0, 12 = 3^1 * 2^2, 27 = 3^3 * 2^0, so it will be in the same group)
Represent each number as a product of it's prime factors (but with each power modulo 2).
For example: $$$540 = (2^2)*(3^3)*5$$$, so it will be represented as $$$(2^0) * (3^1) * (5^1) = 15.$$$ Hence each perfect square would be represented by 1.
All numbers having the same representation will be adjacent at the $$$w = 0$$$ second
And at $$$w = 1$$$ second only the representation having even counts will actually become perfect squares and thus merge into the representations of 1, and other representations will remain the same. Count the maximum among them
*0th or 1st Notice that lcm(x,y)/gcd(x,y) = x * y / gcd(x,y)^2. That means that numbers are adjacent if their product is a square number. If they are square numbers, we don't really care about prime factors that appear even a number of times. So basically, divide numbers into groups, where every number in the group has the same "odd" prime factors. If the group is odd-sized, after the operation its size doesn't change. Otherwise, after the first operation, you can merge two even-numbered groups.
Did anybody face 'Idleness Limit Exceeded' in Div. 2 D for not flushing cout, or was it just me?
Same when doing practise- -
That's pretty weird to me, I got Accepted by changing
cintoscanf.[Accepted] Use
scanf: code[Idleness limit exceeded on test 3] Use
cinwithios::sync_with_stdio(false): codeDoes anyone know why?I am using
intto readlong longcause the issue..Yeah, it worked when I changed endl to "\n". Strange.
Div1 C deserved way more points than Div1 D :(
How to approach C problem? I didn't understand the samples.
Same, I spent a lot of time, thinking what the hell with samples.
Idea what we can use another distribution than in samples, like (from the second example)
I solved by two prefix sums (gift prices and sorted costs to pay to friends). And we try to find how many elements with paid friends we can replace with gifted (gifts from start (from cheapest)). Trying to find the edge of the minimum total price. It's kinda difficult to explain.
103452905
Possibly it is not the most obvious solution.
The difficulty difference between div 2 C and D was way too much :(
Nope IN fact I solved D first then A/B/C
And I got D but not C :)
Weak test cases of C
103437395 (should be WA , but AC)
103459710 (This is correct)
UPD : My mistake sorry :( , but still i m not able to figure out why both are correct
its correct, i mean first link answer is not wrong.
No you are wrong :)
1
11 2
1 1 1 1 2 2 2 2 2 3 3 3
2 4
The first solution gives 28, while the correct answer is 27 which given by the second solution
oh yeah
if (j < m && j < a[i]-1)should be there i guessthis is the verdict before system tests
In Div2 D i was solving with keeping in mind that answer for w = 2 is same as w = 3, 4, 5, ...
Is it true?
:((( just one more minute.
In problem D , I thought answer will be same in each query and adjacent property will be transitive .Got WA on test 2 , maybe i missed something .
I stored frequency of a[i]/(j*j) if a[i] is divisible by j*j .Maximum frequency will be answer .
could someone tell whats wrong in approach or solution
nvm, got it
The answer is the same for w = 1 to 1e18.
Yep
Div2 D was tough but it is really awesome problem I guess.
Agree
1) I think Div2D can be solved using Prime Factorization. (Correct me if I am wrong). time complexity will be around O(N*sqrt(Amax)). 2) I think you will get maximum possible answer in second 1. so we have to calculate answer for second 0 and 1.
I don't know what I missed but, failed pretest 2.
You miscalculated answer for second 1, you include even component size ones as well as ones which are perfect squares already, and also take maximum with odd frequency ones also.
I think I messed up calculation for element with value 1.
I don't think that complexity passes, I got TLE. Might just be me being an idiot though.
No. I agree with you. I was just brainstorming.
I passed sample of E in 10 seconds after the match, f**k the long queue!!!
The problems were nice but the queue was awfully long:(
Oh in problem F I didn't consider the case when two rectangles form a cross, ready to FST, so sad :(
But, how could this pass pretests..?
the requirements for the solution for Div1D/Div2F don't have any sense!
Cheaters everywhere!
Waiting for the obligatory mass cheating blog.
we dont give a f*ck, why are u posting this? spoils the mood tbh.
We know about this chat and all cheaters will be banned
Lol they blocked me after I told them 2-3 eye-opening lines XD
There was long queue throughout this contest we had to wait for 2 minutes to get to know whether our code passed pretests or not . My last submission although passed pretests but there is negligible chance of it passing the final test because it took 1965ms where maximum time allowed was 2000ms. I think I could have modified it easily if I had got 5 more minutes which got lost due to this queue . The Coordinators should have Increased the time by 15 min to compensate for the long queue. Anyways keeping aside the result This was a great contest. A,B,C were good . D was quite Tricky
Hi! Does this contest have hacks?
Interesting problems!Thanks to everyone who contributed!But testing was weak. :(
Hi! Is it possible to hack codes?
I highly suspect the data of DIV 2 C is wrong, that is, in pretest three, the ci's are not ranked from the smallest to largest. Anyone share the same idea?
They are in ascending order, please read the question carefully
Yeah they should be, but I doubt in pretest 3 they are not
Hmm...I got all the pretests passed, did your code failed for 3?
Yeah, and I compared it with the passed code, and our code are different if and only if the costs are not sorted
Can you show both codes?
I will give you 20 euros if what you say is exactly true.
This is the passed code
And this is my code
I guess I can't get this 20 euro but I would also be grateful if you could point out my error :)
In the last for loop you are using b[i] which is wrong because i < n
Some out of bounds lies here...
If you are saying things like "test data is wrong" without even seeing the test, you better have a very good reason. It is far more likely that you did something wrong. Especially since a ton of people have solved it.
The kid is wrong btw. I added
and no RE. BTW, the array b is the array c in the problem. https://mirror.codeforces.com/contest/1471/submission/103468499
Преподаватели не могут жить в домах, соединённых переходом. — поправьте меня, если я неправ, но мне кажется, что по-русски так не говорят. Корректно сказать "жить одновременно".
Понятно, что эта фраза означает, но она действительно сбивает с толку. Мой друг задал уточняющий вопрос, и ему ответили "без комментариев". Почему? Разве цель людей, отвечающих на вопросы — портить контест участникам?
Не думаю, что участник в Div1 задает вопрос от того, что ему нечего делать.
In Div2C, Totally missed that the cost array was sorted. Made a segment tree ;_; . (Link 103478099)
A- pretests passed(3)..... WA on test 4 :))))) and my day is spoiled.
??? why pretest A was too weak so many contestants was hacked
someone probably leaked the wrong solution
whoever did that, u have my respect!!!
Not really. Many failed due to precision error of floating point ceil func in C++. Seems quite natural to me.
Not getting hacked is not a universal human right or something.
Due to integer over flow my code failed for A
I realized after contest finished
I have to change int max_bty,min_bty to long long int max_bty,min_bty Silly mistake
But i wonder how integer overflow occurs even constrains says sum of all elements won't exceed 10⁵
I could solve only B in the contest. Got wrong answers when I submitted A and C. Just tried A and C with replacing
intbylong longand both got accepted.Thanks for an interesting problem set. Wish there was a little extra time due to problems with the queue.
what happen Problem A's TC 4
I learned ceil for integers by a hard way today.
What is the issue with ceil?
Why is my solution for D still showing pretest passed instead of in queue?
Because it passed the system tests :)
Emmm... I didn't get points for that problem.
How can we have all that queue without even increasing the time of the contest?!!!!!!
Thought the blue color was the theme of this contest, turns out it s absolutely red!
RIP c++ contestants on problemA div2 xDxD
why what happened?
take a look on status! lot of cpp submissions failed system tests on problem A.. mine included xD..
I guess it has something to do with the function ceil.
I think I have never used
ceil. Don't useceil, in fact try to not use floats unless absolutely necessary. You can do most things with integers, for example(p + q - 1) / qcalculates $$$\left \lceil \frac{p}{q} \right \rceil$$$.coool thankies
To find the
a/brounded up to the nearest integer, can't we useif(a%b==0) ans=a/b; else ans=(a/b)+1;?I assume you can use many things to do that.
Pffff.... I always thought that this is one of first things you learn in c++ contests:
1) Beware of overflow;
2) Beware of UB (overflow is one of case of UB but sometimes it is not and it is too common problem);
3) Beware of using floating-point functions where it's not necessary.
Why are you blaming c++?
BUT WHYYY?????????????????????????
System Failed Error.
when everything works perfectly!
Also, this C++ code uses Ceil and also accepted
https://mirror.codeforces.com/contest/1471/submission/103394434
You failed because you output 1e+10 (see your submission)
In passed ceil result was cast to integer type. But I think maybe this is still hackable due to floating point operations. This is rule — never use them :)
Thanks for strong pretests in B.
I used
intonwthen it passed pretests.I did the same and it failed pretests :o
I think he is talking about div1B.
I was also talking about div1B lol
I've just realized that div1C is a perfect task to do while(1) when you run out of queries.
Fastforces
My simplest solution to Div.1C :
Randomly choose an index and check if its value is not k. When we find such index, break.
If value is more than k, keep going left else keep going right till we find k.
Is it hackable ?
Why you guys did weak pretests to Div.1 D, not funny
Also thank you for very stong pretests on problem C, now I will lose all my rating, worst prepared contest ever
When you are about to get +230, but you don't believe your solution on D so you did 100 random iterations of the greedy (just 1 iteration passes) and then it exceeds the time limit in system tests
In div1C when I was stressing the solution of one guy from my room, he had like $$$\frac{1}{10}$$$ chance to ask too many queries and it passed o.O
Why Problem A of Div 2 throws SYSTEM FAILED ERROR in my and many many other submissions?
MY CODE: https://mirror.codeforces.com/contest/1471/submission/103394142
It's throwing WA in TEST 4. BUT WHY??????
cout<<(ll)ceil((sum * 1.0) / x)<<" "<<sum2<<endl; it gives you OK
Typecast your answer int INT, ceil function returns double, which has a floating point precision of 10 digits, so any number greater than that is represented in exponential form.
Hi, my submission 103400375 didn't enter the main test queue due to some reason. Please check it and rectify MikeMirzayanov. Thanks to the user osLivedHere for pointing this out!
Got accepted now. Thanks!
Good job!
Thanks for LOTS OF STRONG pretests.
The Problem. C，we can only read 2 integers，and there are only 6 pretests?
This is a part of my code. I just made a mistake(980 is too big) but it can pass the pretests.
So what are these pretests for?
Not that strong pretests are good for hacking, but just 6 weak pretests went too far
Queue would have been very long if there were more pretest. Could have made round unrated. It was prefect amount of pretests for maximum participation. But the pretests in itself could have been stronger. Like adding test cases could have solved this problem.
No way, 6 weak pretests is just too bad
why systest on E so slow :(
Wrote 41 minutes ago and it's still running...
Finally finished
Best of the best)
Got fst for 2 problems... I think today's pretests are kind of weak.
Since I got WA on problem A, do anyone know a fast way to write ceil(ll a/ll b) on large integers?
a / b — round down
a % b — remainder
!!(a % b) — cast a % b to bool (0 if a % b == 0, 1 otherwise)
So full expression is $$$\lfloor a / b \rfloor + (1 \ if\ a\ mod\ b \neq 0, 0\ otherwise) = \lceil a / b \rceil$$$
Use
(a + b - 1) / binstead ofceilfunctionceil(a/b)=floor((a+b-1)/b)
(long long)ceil((double)a / b)
Bleed Blue!
I feel like I am higher in the rankings than I should be, even though I had 3 failed submissions on problem D. Is there a reason for this?
I feel sad for what happened to rainboy
He is not alone)
Darn I got 2 TLEs on Div 2C before I used the input optimization (ios_base...). Even my O(N) solution failed because of that. They really just had to make it N=3*10^5.
My O(nlogn) solution works without optimizations)
Idk what I did wrong then. Here's my submission that was O(NlogN): https://mirror.codeforces.com/contest/1471/submission/103439026
103495429
Do not use
endl.I spent a few minutes debugging div2e and solved it after the game. But I couldn't finish it in the game, even though my idea was right. What a sad story. .
1471A - Strange Partition 103405431 103466071 I used a simple (int) to convert a fraction to integer. How I even got an negetive value ? Is it fault of server ? cause removing (int) gives correct ans and int is virtually just converting or typecasting fraction to integer.
wrong answer 13th numbers differ — expected: '3333333334', found: '-961633962'
This should not be there . Please correct me if I am wrong. [user:300iq][user:IgorI]
I think you have overflow
here: mi = (int)(mi/x)+1;
I don't thing that is the case since ma is also int .... and values are almost equal plus many people used int when declaring the variable .I suspect system's fault.
To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!
Damn! Never knew using
floatinstead ofdoublecould be this costly. In problem A, my code (103399047) failed test case 4 (wrong answer 9th numbers differ — expected: '11', found: '10'). I thoughtlong longdivisions could be handled byfloat. Does the same happen with anyone else ?In general, it's better to avoid using float or double when it's not necessary. It's way safer to just make your own simple ceildiv function.
float is type which store at most 9 decimal digit precisely. So not all 64bit numbers could be hold.
And yes, in status you can see that you are way not alone
always do (a+b-1)/b for the ceil of a/b
I found problem F very unclear. Is like the first condition contradicts the third:
it means that if an edge doesn't have both vertices with a teacher, the edge is closed?
but the third condition says:
Was the intention that open edges are the ones with at least one teacher in one of its vertices?
open edges are the ones with exactly one teacher in one of its vertices. I agree though, it was unclear for me as well. Had to read 4-5 times.
yeah the statement could have been worded better.took me a lot of time to understand what they meant.
I asked for clarification of the third condition, then I get:
So I can only get what it means when I successfully guess what it means.
it was a bad contest.
It was good learning
In Div1B , I am getting WA on TC 44 , but its working on online and local compiler correctly. Can someone please help me with what is the error. Thanks!
w can overflow int
my int is defined as long long , so that isn't the reason I think
Too bad idea change container white iterating over it with range-based loop.
Thank you so much , but can you tell me why this happens ?
You there have unordered map.
What happens when inserts new element (index access can do this)? There is checking if there is need of rehashing (map size is gonna be greater than $$$m.max\_load\_factor() * m.bucket\_count()$$$ ). If rehashing is needed then all buckets are cleared hence all iterators are invalidated now.
So in your cycle body $$$x$$$ is reference to value lies under iterator which is currently not valid anymore. And before next iteration there is try to increment invalid iterator which implies UB.
Why it is only WA#44? Because UB is almost never predicted;) But maybe at most small tests there was perfect square in test data and there is no invalidation and with others rehashing is no needed.
Thank you so much , got it . Will be careful from next time ;)
https://mirror.codeforces.com/contest/1471/submission/103474555
Missed div1C by two characters...
I missed div2D by one second :(
Thank you cf to yet again remind me to no never use float even in my dreams
Aw I really thought I would reach pupil this round, welp better luck next contest
How do I find the answers in problem D without integer overflow?
Here's my post-contest submission: 103473448.
Could someone please tell me why I am getting TLE for Div2D (Div1B)?
Submission: 103458851
Variables-
equi[x]: the ultimate value of x once all square elements are removed from it.
equiCount[x]: a map to count occurrence of x
initial: for w = 0, counts the maximum answer for initial setting.
after: for w >= 1, counts the maximum answer once different elements are merged
Actually I am never sure about how to use unordered_map without losing performance so if you could give me a few tips about that, that would be helpful.
Fast input output makes it not TLE, but there's a runtime error anyways 103489924.
Does someone have an explanation as of why my submission Replacing unordered_map with vector is getting TLE, but this one using unordered_map with the exact same code is not..!
I have just changed the hashing container..
If memory was a concern..i should have got RTE. But TLE is kinda strange.
The limit of testcase $$$t$$$ is $$$10^5$$$ and you are initializing a vector of length $$$10^6$$$ with $$$0$$$ in each test case and its time complexity is $$$O(N)$$$
Oh correct! That really helped. Thanks a lot!
Can anyone figure why this code is getting mle on test 21 ( Div2 :Problem F)
The contest(problems) was really good, but I didn't like sample tests(they are too stupid).
strange contest
Above is the content of di1C/div2E test 70 checker log, and there are something really confuse me. Shouldn't k be an even number and p is less than or equal to n?
I suppose that variables are mixed up in checker logs for this problem. See other logs, everywhere they are like this:
ok Position $n is guessed successfully (n = $k, k = $p) with $some queries(An input line of the judgement protocol contains 3 numbers and these might be n, k, p in that order)