Привет, Codeforces!
В 07.07.2023 17:35 (Московское время) начнётся Codeforces Round 883 (Div. 3).
В этом раунде вам будет предложено 8 задач, посвященных приключениям неугомонного математика, программиста и просто забавного персонажа по имени Рудольф, и 2 часа 15 минут на их решение. Задачи подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше, могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты и тоже будем расстроены, если у многих решения будут падать на взломах после окончания раунда.
Штраф за неверную попытку в этом раунде будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона необходимо:
принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Составители задач этого раунда: vladmart, Sasha0738 и natalina.
Также большое спасибо:
Vladosiya за координацию нашей работы.
MikeMirzayanov за системы Polygon и Codeforces.
Sugar_fan за красное тестирование раунда.
74TrAkToR, zwezdinv,Sokol080808,senjougaharin, FEDIKUS, Lucina, vrintle за жёлтое тестирование раунда.
pavlekn, diskoteka, Phantom_Performer, bigDuck, Evirir за фиолетовое тестирование раунда.
KoT_OsKaR, HappyChau0v0, bugdone, Termii, t0rtik, Rudro25, O_E, jhorvat, sohelH за синее тестирование раунда.
ctraxxd, 666EGOR777, Guevara74, stefanbalaz2, jojonicho, hussein_auf за бирюзовое тестирование раунда.
Всем удачи!
UPD: Разбор опубликован.
Here before the "Hope to reach expert this round" comments.
Hope to reach expert this round! (Tho there's no way an unrated jumps all the way to expert)
Such weak test cases for problem C
Bro can you please expalin where test case fails!
like when there penalty and scores are equal
Weak TestCase Contest
Can you speak Chinese
Yes of course. Whenever I get a Chinese lobby in cs, I always greet them with 嗨，台湾是最伟大的国. I always end up getting kicked for some inexplicable reason though... maybe I need to work on my accent.
Looking at the post, i think that i should clarify that i identify as a bi-color tester
As a tester, help Rudolf solve those problems!
You missed an opportunity to name him Rudeus (Greyrat) and have back-to-back anime rounds :'(
In the problem B, why this case is valid?
XXX
XXX
XXX
in the problem statement it is mentioned that
how can this test be result of the Game where one player is making all moves?
Also, All the sample tests are maded in that way that one player is making move after another.
If it is valid test then I think it was better not to introduce this problem as 3 player Tic-Tac-Toe game.
Exaclty! My solution was hacked with the input:- . X . . X . . X . How can this be a valid input in the case of a completed game, if only one person is making the moves?
You can get hacked with a case that follows standard tic tac toe rules such as
OOO XX. ...
well, if we consider 3 player Tic-Tac-Toe Game, here 3rd player is not moving at all and 1st player is moving 3 times. How this test can be valid test?
can anyone clarify that?
In their defense example 5 is also a "Violation of the classic rules". so, they mean classic rules in a weird way where people can skip turns. But I definitely agree with your point of the game not following "classic rules" as promised is something they should have looked at or provided some clarification in the problem statement.
"It has classic rules, except for the third player who plays with pluses" does this mean only the 3rd player has different rules such as skipping turns or having more turns ?
If this interpretation is correct, then the samples make sense. But it contradicts XXX ... ... as a valid test case
yea even my solution also got hacked, how can i know for which test case my solution is failing
Yeah. A player should not win more than once (have more than one winning sequence of cells). Very weak test cases, lots of solutions were hacked.
As a Blue Tester, Hope you will enjoy the falling of snowflakes.
E2 hard, have no idea
Idea1: for n<=1e16 do brute force mean check for every k from 2 to 1e6. Then for 1e6+1 to 1e18 do Binary search. Cause here no of element fixed 1+k+k^2 as k^3 >1e18..
Idea2: You can fixed length . length can be maximum 60-65. then for each length do binary search just..
if you fix length to >50 you will TLE in Java. Brute force for 2 to 1e6 and then binary search with fixed length of ~6 is correct though.
I liked the problem, but something odd happened in the evaluation. I passed E1 and E2 during the contest, but in the post-validation got TLE in E1. It's such an odd thing to pass E2 and fail E1, and it is due to the fact that TLE strictness vary during and after the contest. Of course, if I had noticed this TLE, it would have been easy to submit the same program that had succeeded for E2...
Weak testcase contest. Very Disappointed. If you get TLE or WA during contest atleast one can get a chance to think of a better or correct solution. The hack that caused TLE for most accepted submissions (for E1) shows how weak the testcases were in this contest.
As a tester, this problemset has some amazing problems!
Hope to reach close to "Cyan" after the round.
Hope to be balanced difficult round.
In the second query of the second test case of D, why the answer is $$$3$$$? It think it is $$$2$$$: $$$(3, 5)$$$ and $$$(2, 7)$$$.
are you a time traveler?
No, wrong blog. It's about Round #882.
Sorry bro , but this is div 3. You are at wrong place.
Hope to be a balanced difficult round.
Now div3 is my only hope after my div2 performance went for a toss :(
Can relate
lol, ur hopes got shattered
Yup. Due to my stupidity only. I kept solving F without trying C and D for 1.5 hours and before I knew, contest was over. Later I upsolved C and D in 10 minutes each. Got a good lesson though
In c everyone just copies tries code form online, please check plagiarism.
bro wrong blog this is upcoming div3 :skull: and copying code from online is allowed if it was there before contest
First unrated div3
Congrats
Thanks
As a tester, please join this round :)
Although I was unrated for this game, I still wanted to participate
Enjoy each competitions and get rating
Enjoy each competitions and get rating
First time to participate in DIV.3 .(just dropped the blue name yesterday) everyone come on ！
First time to participate in unrated Div3
I hope to solve A,B,C in this contest (:
Red Purple Blue Testing... Are the problems salty?
Personal question:
I've just started with 400 rating am I eligible for this round?
yes
Hope to reach expert this round
what is the minimum number of problem you need to solve to reach expert from you cur rating in this round?Just curious to know.
just add me to friends and will look to +100(and more) delta. Answer on your questions — i dont know
8
its depend on the contest some contest it's okay if you solve 5 and some contest you have to solve 8 and there is extension called carrot it can help you know what is expert performance link : (chrome://extensions/?id=gakohpplicjdhhfllilcjpfildodfnnn)
Am I the only one who hates DIV 3 ? :)
Me too...
.
Don't know what I am going to do with that information
mine worst contest till yet... waiting for the rating update to see how much delta negative it will!!!
You can use this extension to predict delta even during contest, it is pretty accurate
Actually it was my first contest...can you please tell me when will the ratings be updated?
You can probably expect ratings to be updated within the next 24 hours.
So Rudolf and Rudolph are like brothers?
how E2？
me after previous contest:
-hello, Specialist !
me after today contest:
-goodbye, Specialist !
i'm tooo slow)
Thank you for the amazing contest! I really liked it!
TIL I am not that good at geometry
was E2 a double binary search problem , first on k and second on the possible power of k ??
I used quadratic formula to solve for potential cubes and then precomputed possible powers until 10.
pretty neat , but was it intuition or somewhat a proof that we can achieve our output uptill 10 ?
Not exactly, sorry for the confusion. You can also have powers larger than 10, I think. I just brute-forced to get all possible candidates that have powers less than 10. This makes the look-up for other potential values of k faster
can you help in my E2 submission 212790410
Product res can exceed limits of unsigned long long
How can I solve that problem?
I did something like this in 212650593
Didn't Solve it.. But i think we don't need to do a binary search over k's powers we can check all of them "aka. brute force " as maximum possible power to have is p = 63 for k = 2 and p decreases with any increasement in k .
was thinking the same that complexity could be max around O(log sqrt(N)* 63) in worst case if n is 10^18 and k is 2, kept on messing and crashing my compiler :'(
So the goal of the problem is to find some k and l such that k^0 + k^1 .. k^l = n and l>=2. Notice that l can be at most around 63 ( when k is 2 ), and therefore, you can iterate on l and binary search on k, yielding a log(n) solution with a moderately large constant factor.
2^64 ~ 3^41 ~ 10^19 ~ 250^8 ~ 7000^5 ...
I brute forced the solutions for the first 1e5 values. For values above 1e5, I did 2 things.
First: Fix the length of the formula between length 3 to 5.
Second: After assuming a certain length is correct, lets say 4, you know the formula should look like this: k^0 + k^1 + k^2 + k^3 = n
Since n is known, you can binary search for a k.
Can anyone help me why this submission of mine for the problem F is giving wrong answer? I think my logic is correct, maybe somewhere I am doing mistake with i/0.
https://codeforces.net/contest/1846/submission/212691145
you have wa1 you can fix it
Kinda MathForces round but Enjoyed solving A ~ E1 :D
can someone tell me how tf am i getting a WA test 5 on D where do I mess up Submission
nvm i was using setprecision wrong. i will get negative delta for sure
My code was rounding off answer of problem D to next number can anybody help
set precision to the answer.
for c++, add this before printing answer "cout << setprecision(8) << fixed;"
I have tried then also same problem it was fine for other but test case 4 it rounded to 200000
Then maybe your logic is not correct. You can refer to my solution
You subtracted area of small triangle from big. I solved by using area of rhombus. Let me try your method.
Mine too rounded to 200000 but it gave correct answer. My Solution -> 212673768
My answer also got accepted i should have submitted it during the contest 212710542 Thanks everyone for help
Hey can anybody share link resources for solving problems related to decimal points (faced difficulty today)!!
same
You misunderstood problem D. It wants you to be precise to the 6th decimal place. If you google "C++ float precision" or "C++ double precision" then you find out that both datatypes are accurate enough. Float is precise to the 7th decimal while double is precise to the 15th decimal.
If you ever find yourself in the need of bigger datatypes, you may want to check out this: https://cp-algorithms.com/algebra/big-integer.html
.
E: n is valid if there exist k>=2, r>=2 such that 1+k+k^2+...+k^r==n. Since k^r<n we have r<log(n), so we can check for all values of r and find k by binary search, we can solve a single case in O(log(n)^3).
F: We remove no object for 1st and 2nd queries, and the mimic must change it's type during first 2 queries, so there will be exactly one t that the number of occurence of type t increased. Then we can remove all objects with type other than t in the 3rd query, then the types of all objects will be same, and mimic will not be removed. Then the mimic will change its type in the 4-th or 5-th query and we can find it easily.
G: We can build a graph with 2^n nodes (representing every possible subset of symptoms) and 2^n*m edges using bitmask, and solve the problem by dijkstra shortest path.
optimization of E that I overlooked during the contest but turned out to be valid: The only possible candidate for $$$k$$$ is $$$\lfloor (n)^{(1/r)} \rfloor$$$. This is due to the fact that $$$x^r < (x^{(r+1)}-1)/(x-1) < (x+1)^r$$$. Look at the binomial expansions to find out why.
unfortunately it is difficult to directly use this because of double value precision problems: my wrong code
You can always adjust afterwards just like how you find the value of $$$\lfloor \sqrt x\rfloor$$$, just double check using values of $$$k^r$$$.
it can exceed MAX long long
Dude, trust me, I know that already. And also I know that if $$$k^r$$$ is safely contained in
long longthen $$$(k^{(r+1)}-1)/(k-1)$$$ is safely contained inunsigned long longas it is smaller than $$$2k^r$$$.not what is was saying. $$$(k+1) ^r $$$ can exceed max long long even though $$$k^r$$$ does not
well then you can check if it exceeds the limit very easily? just use naive multiplication and check overflow using division in the process
no shit
kingpin199 why do you use int instead of long long in your code?
I also invented chromate00's optimization and implemented it https://codeforces.net/contest/1846/submission/212834179
im defining int as long long int in the beginning of my code. im suprised why urs passes and mine dosent, any idea>
Test: #13 test consists of large numbers
I think the problem with types or overflow
You can try to change double to long double
Or generate a test with large numbers for debugging
That's what I tried during the contest, even though I was just as sure that this approach is going to get hacked (unsurprisingly, it did), my submission: 212667440. Naively switching to long double doesn't help as well, is there some other way to make this solution work?
well the safest approach in contest would be sacrificing a log factor and using naive multiplication + int128 (GCC) (of course you would need to adjust the value of the k-th root)
In problem G, is it true that every medicine can be used multiple times? If not, how do you prevent multiple uses?
That's why we're using dijkstra, do you ever comeback to the same node in dijkstra bfs ?? Use that analogy here, take days as edge weights
there is no ban in using one medicine multiple times, so you can use it multiple times, but I think it doesn't make sense
"how do you prevent multiple uses?" — in our graph we use edges as medicine(at least I used it as medicine) when u are doing dijkstra it is obvious that you will not use one edge multiple times, so we use one medicine at least once.
my submission 212707666
Am I correct that there are multiple edges in a graph associated with the same medicine? If that is the case and multiple use of the same medicine is forbidden then all such edges must be removed from a graph once we use one of those edges. It is not specified explicitly but examples suggest that every medicine on the path must be unique.
I think in terms of logic choosing twice same medicine is not efficient, I can't prove how exactly dijkstra will choose unique medicines, but by definition dijkstra choose always shortest path, so it should choose unique medicines
why downvotes ? am I wrong in something?
I implement F the same idea as yours but getting WA. Any idea why?
212701178
You should output the index of the mimic directly after find it, instead of removing other objects and output 1.
wait why is E $$$O(log^3(n))$$$ not $$$O(log^2(n))$$$?
there are logn degrees of the polynomial, then you binary search leading to a second log, and your check function is also log
wtf was d?
good questions but the problem statements can be improved. All of them are so long AND confusing.
It's like a reading exam at this point.
G is literally dijkstra. There's nothing algorithmic about the last problem in this contest. The hard part was READING and parsing the bits. Wtf
I really liked G, excellent problem. E2 is also very nice.
what did you like about these problems? G is very obvious and E2 is just stupid math.
Nothing is obvious / standard in a div3/div4 round. People here are learning these topics. How could you say bit-mask + dijkstra problem is an obvious one for div 3? It was indeed a great problem
Thanks for preparing this amazing contest! I am delighted that I got 1st rank (excluding unofficial) before the hacking phase.
The last problem G is a masterpiece. It is picky to think about Dijkstra. But very good problem to show that modeling to graph can be good way to solve the problem.
The contest was good, but can testers do something about all these. telegrams, whatapp groups, and youtube channels uploaded the solutions before the end of the contest. I have seen some submissions that were directly copied from youtube uploads, and still no action was taken on them :(
What do you think Codeforces can do? It happens every contest in Leetcode as well.
This is more like an Indian problem that spreads everywhere in my opinion. There's nothing Codeforces or Leetcode can do if most of the Indian users lack integrity and consideration for other people.
TLDR: Indians lack skills and talents so they cheat (low rating overall). Blame India for producing top cheaters instead of top geniuses in algorithm
lgta H apki Indians se kuchha jayda hi dusmni h
I’m indian too but gotta agree with you here :/
Know many cheaters personally as well……. But still you shouldn’t equate it to a lack of skill among indians (ik i’m still a newbie but there are many genuine candidate masters and red coders from india as well)
it's too racist.
never mind,we solve this tasks for increasing our skill,not just for the points
Layman trick for E2 trick I found right after contest ended ! —
for
iup to 10^6: store the possible sums in a set forigreater than 10^6 (it cannot be more than 10^9): it can only branch out one time before the result it goes over 10^18so the geometric series can only be of the form
1 + i + i^2now it remains to be calculatedifor which1 + i + i^2 == n. and we have to do it quickly. so after modifying the above equation it becomes(n-1) = i*(i+1)which can be found quickly by taking square root ofn-1, saykand checking ifk*(k+1)is equal ton-1what is wrong with this solution for C ? I found points and penalty for every contestant then iterated over them while incrementing cnt if anyone has better . Others seemed to have done the same
https://codeforces.net/contest/1846/submission/212638737
I'm not experienced in Java, sorry, but I'm wondering if it's because hashmaps can't store multiple copies of the same object. Some participants can have the same scores and penalty.
I think i used hm as variable name of arraylist which is a vector . It's okay , thanks for helping
Ah I've read it wrongly, sorry my bad.
You are adding the same penalty multiple times.
time+=(ar[j]+time);should betime+=sumI tried to hack my C but I received an Unexpected Verdict. It seems that there is a solution on Polygon that use int but it was marked as AC.
nice contest (especially problem G), unfortunately spent an hour searching formula for D
question C runined the contest for me , i got the vector of pairs of {poins,penalty} then i thought i would need to sort it accordingly to find the position of first person , but god i don't know but i am not able to sort it accordinly with comparator functions , it became a mess , spent half time of contest on C , then in last 10 minutes it striked me that i do not need to sort , just count how many elements greater than first , damn could have got <2k rank but next time ig
Screencast of the round, I tried to explain my ideas, if someone needs that
https://www.youtube.com/watch?v=dvNKBeTtlY4
A very good and educative contest. Problems were really very nice and educative specially problem G was really cool, problem E2 and F was also very nice.
today's just not my day. started the contest 5 mins late and just failing on E2 miserably, just being very low in ranking :(
Managed to figure out right solution for D in the last minute, but forgot to cout << fixed; cout.precision(6); and got wrong submission. so sad :(
For those trying a binary search solution for E2, you need to set the upper bound appropriately so you do not overflow. (WA on test 7 or WA on test 11, etc)
Accepted code
WA code
Also, anyone know why this python code TLEs?
change val to return (k**(it+1))//(k-1)
Unfortunately, the improved code still TLE's. Probably a case of python being slow?
Yeah, maybe. I had to use some weird brute force to pass instead of doing binary search.
Had the same problem in Java, where searching for >52 range would TLE me. You don't have to search in such a big range if you precalculate some solutions.
2^64 ~ 3^41 ~ 10^19 ~ 250^8 ~ 7000^5
I participated in this contest and I get TL in the interactive problem (F). I cannot understand why. Is the time limit too strict? Could someone please check my solution and explain?
This is my solution: https://codeforces.net/contest/1846/submission/212693618
Can someone please explain why 212706726 passes and 212706596 does not for E2.They're exactly the same code.
r=1ll<30 ?
Thanks
how to solve E1. I thought if a number can expressed as 1+a+a*a+a^3...upto n where a is an integer and n is an integer. and got stuck after.. Is this correct way to think or is it wrong.Thanks
its correct. you know that k >= 2 from problem constrains and also that every graph of the described type must have at least 1 + k + k^2 nodes. You know everything, just precompute those values going up to 1 + k + k^2 + ... + k^m so that the total sum <= 1e6 and store them. If the given n is among those values ans = YES else NO.
i really liked the geometry behind problem d
i did bruteforce on e2 https://codeforces.net/contest/1846/submission/212709034 try to hack it if you can
is there a hack for this solution of problem G?
UPD: Hacked
i did brute force on e2 try to hack it if you can:- https://codeforces.net/contest/1846/submission/212709034
i did bruteforce in e2 try to hack my sol if you can :-https://codeforces.net/contest/1846/submission/212718777
Can anyone tell me why my solution for E2 gives TLE in c++17. Got ac using c++20.
c++17 submission
c++20 submission
Since you're using long long instead of int in your code . It's getting faster execution with C++20(64bit) . Always use this compiler when you're working with long long . Hope it helps .
E2 was a nice question on binary search . Nice blend of Maths and Binary Search .
I guess, I have an easier/optimal solution for E2:
Link to my Submission : 212747366
It runs in O(k*log(k)) where k is 60.
Can someone hack this 212683099 submission for G, it runs 100 iterations, and it seems to be enough, I don't know any test case that can hack it.
leave me alone
It’s correct. Given a valid ordering of medicines, you can reduce it to the set of medicines that last relieve each of the 10 symptoms.
Credit to conqueror_of_tourist, conqueror_of_womais
I thought about it as a graph, u will not need a path that is longer than 10 nodes, although a submission with 7 iterations also worked lol, can it be explained?
Hacked
What is the importance of first 2 lines in the below python code for A question. Why am I getting T.L.E when trying to submit without the first 2 lines:
212712911
They are used to take fast input output.
What is the Hack case in problem B?? So many Hacks!!!
Not only for B. There are so many hacks, afraid...
А почему в задаче Е1 при n равном 2 ответ No. Пусть есть одна вершина, добавим две новые вершины, соединим с предыдущей. Для каждой новой добавим опять по две новые и т. д. И получается снежинка. Поясните в чем моя ошибка. Спасибо.
1 + 2 + 4 = 7...
What is wrong with my Problem C code ;) https://codeforces.net/contest/1846/submission/212661976
Change the <= in the comp function to <
In C today the (overflow test) in the contest wasn't provided and a lot of people will get WA because of it. How this basic test not handled to aware us :(
OMG...
Can anyone hack my C now？Just overflow test
UPD：it has already been hacked. Thanks
Yeah, not including a "long long" test was quite an evil thing to do.
Hope to reach newbie this round.
Terribly weak tests for problem B
Why it was a great Div3 round :
Problem A & B : Naah, they don't teach a lot
Problem C : Teaches use of custom comparators
Problem D : Teaches to handle precision in floating point numbers and some geometry
Problem E : You've to be prepared for future "Math-forces" rounds to grow as a competitive programmer.
Problem F : Simple idea but teaches how to interact with the judge
Problem G : Shows the power of dijkstra and also bitmasks with it
Overall, great round covering so many topics that are pretty relevant to div 3. Congratulations to the authors.
if u use python Problem D only teaches basic geometry
finally expert... yayy
finally expert.... yayayy
Good JOB my friend! Try to keep this rate and reach candidate then ;)
I have made a video editorial from A to E2 do check that out... https://www.youtube.com/watch?v=0paMs9FV_nk
Thank you!!
Thanks for the video editorial buddy ^ ^
Is there some problem with the validator of problem B, as many of the hacked solutions missed the case where more than one winner is possible, whereas it is clearly mentioned in the problem that multiple players cannot win the game.
X.X X.X X..
I really like this round. Nice problems
Hackforces anyone!?
Almost got hacked for C, my first submission was just using ints to keep track of the penalty which passed pretests. But then I remembered getting hacked for problems with calculations in the 100000^2 range and resubmitted with long longs shortly after.
what is the significance of trusted participants?
Does it affect rating by any way?
trusted participants for div3 are the one whose rating is below 1600
yes, while rating is considered only the trusted participants from standings are considered
Wrong. Did you even read the blog?
To qualify as a trusted participant of the third division and be shown in the official leaderboard, you must:
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.
Being a trusted participant does not affect your rating. Your rating gets updated if you have $$$< 1600$$$ rating regardless of if you're trusted or not.
Being a trusted participant only affects if you're shown on the "official" leaderboard.
Thank you for explaining this
I faced an issue with problem C:
This was what worked as a custom compare function:
Whereas this one didn't work though they do the absolute same thing:
I later discovered this after the contest was over, I was just trying to sort the values based off in increasing points in descending and same point value then ascending order for penalty here. But this one statement as if
p1.second.second < p2.second.seconddidn't let me pass the time constraint even though essentially they have the same time complexity as using this as an if statementp1.second.second <= p2.second.second, essentially the complexity of my program isO(n*m*log(m))and it should've passed through regardless but idk why it didn't...... you can check my submissions the older one didn't use long long int but I would've figured out regardless if I got WA but the TLE made me rethink my choice in logic and that defeated my morale hugely in the contest.... I wasn't able to do the other problems as I couldn't find an actual mistake here.... The test cases timings were too tight otherwise I really don't know what my mistake was in this scenario....Here was my in-contest submission: 212701525
Here was what worked after it: 212708923
You can see there is almost no difference between the both except for the
<and<=logic wise except for changing the penalty into long long int.... Please guys upvote and get it to the attention of the testers it if this was faced by others, because of this I couldn't perform as good as I potentially could've... as my logic was completely accurate but still failed regardless...Or you could have just used negative amount of solved problems and positive penalties for all the participants, so the standard sort would have worked just as well.
Two problems here:
penoverflows then it becomes negative which will give a verdict of WA. SubmissionFrom the Russian version of this round's announcement:
After this is over, the creators of the round are going to be real sad (basically swimming in their own tears), poor bastards.
Too many hacks...loving that hacks section..
Мне очень понравился раунд. Задачи достаточно интересные. От C, D, E получил удовольствие, решая их. Авторам большое спасибо!
Could somebody help me figure out why my output format is wrong for part F? Submission: 212739492
If someone could look at my submission of F 212740665. Why does it give IDLENESS error on the 2. test? I really appreciate it
My guess is you get an infinite loop when vector b size is 0
eh another failure contest, terrible pretests for B, really long and confusing statements, B isnt really suitable problem for this platform, this cringey shit should be unrated
Sounds like someone did poorly
nah just the B part, its not even suitable for this platform, lmfao put the dumb b away, if u gon say u solved F i can say i solved E2 too? i left after E2 and would solve G now that i read it
Dont make excuses for your own performance. Obviously, other people were able to perform well. Also, I fail to find what is so confusing about problem B, it is just tic tac toe with 3 people? Find if any of the 3 symbols make a straight line..
nope not at all excuses, as i said it really wasnt a problem u would put on this platform, its not competitive programming at all, just some edge case shit which u could miss, thats what happened and thats it, and to be fair no, ACDE1E2 is a much better perf than ABCDE1
I successfully did 6 hacking attempts and 1 unsuccessful attempt on problem B. However, I do not know why but all my successful hacking attempts have been removed and it shows only the one unsuccessful hack. Can someone tell me why? This is the testcase I used to hack Problem B
1
OX.
.X.
OX.
Same happened to me, I did 50 successful hacking attempts on E1 and now they all just disappeared. Seems to me that authors have added a few testcases in the pretests after the end of the round. I can't explain this phenomenon in other way..
Ikr! It took me more than a hour doing so. Adding testcases is fine as this would ensure correctness of all submissions but bruh why to take credit from all those who wasted their precious time finding those corner cases which probably they failed to notice in the first place.
may be someone could have hacked that solution, just before you
Such a bad statements for the problems "It will be assumed that in case of a tie in points and penalty, Rudolf will take the best place" why did this appear as the last sentence in the problem, it should appear above where the author described "In case of a tie in points the one with lower penalty wins"
since there is no continuation to it I assumed there is no tie-in penalty
I know I should've read the problem till the end but it's div3C + why there is no pretest with this case?
only thought 1 + k is required
how did testers approve these statements (:
i guess you forgot to put pre testcases and let all for hacking phase:)
Such a bad statements.
problem C:
"It will be assumed that in case of a tie in points and penalty, Rudolf will take the best place."
This appeared in the last sentence of the problem, the author at least should've described this above with "in case of tie-in points the one with the lower penalty wins"
as there is no continuation for it, I assumed there is no tie-in penalty. Maybe some blame on me for not reading the whole problem but it's Div3C and the info should've appeared above
no pretest for it or the long long case ):
Problem E is hard to determine what you want exactly.
it took me some time just to understand the problem, I thought 1 + k then whatever
but 1 + k + k * k then whatever? it took me some time to understand ): It's not well explained
even F and A need some improvements I see there are a lot of testers, did they all approve on these statements!!
Yeah A's statement was terrible. How did 10k people understand it in the first 10min?
What was the problem with A's statement? Just wanna know.
It was just very unclear to me. Maybe I'm just stupid but I wasn't able to figure out which direction the ropes went in. Eventually I just guessed something that vaguely made sense and got AC.
Do you understand how ropes work in real life? If the candy is connected to a nail at height $$$h$$$ with a rope of length $$$l$$$, the height of the candy must be in the interval $$$[h - l, h + l]$$$. Every nail and rope gives one of these intervals in which the candy must lie. The position of the candy must satisfy all of these intervals and because the candy is affected by gravity, it must lie at the lowest allowed point.
Does this make sense to you?
It makes sense, and I did think of this as I was trying to solve A, but then I ignored it because I figured, "It's a div3a, it's gotta be something really simple". In hindsight, it actually was, and it was entirely my fault for failing to interpret the description. I take back my original statement.
By guessing
Am I the only one who did not use long long in C and got hacked? Like There should be test cases of long long in the pretests, or I don't know my code miraculously worked on them even though everything was int.
In problem C the given note for test case 4 is wrong as Rudolf will be able to solve all 3 questions. Am I right?
are you talking about this test case? If so then there are 2 questions, and the note for this is correct.
How to solve D? Actually I can not figure out how to calculate the area of the overlapping portion of a triangle. Yes, height can be calculated easily (difference between previous triangle height and current triangle height) But what's about the base? How to come up with a formula for that?
Use similar triangles.
The intersection of the triangles is an isosceles triangle and it is similar to the given triangles. Now since you know the heights of both triangles (small one and given one), you can compute the ratio and multiply it with the given base. We are done. (Even though I used something else to compute the base during the contest, I think this way is better.)
hackforces ngl
The pretest of this competion is too weak, not longlong, algorithm analysis errors can pass the pretest
I agree with you (since I got my C hacked, not much painful since it was unrated) but there is something I would like to add (my opinions), I think that the problem setters were new, They had less experience of doing this job. But they made good problems (not all, did not like A, B), but of course a problem setter need more than just creating a good problem. Creating test cases is also part of it (which I think is a hard job), But this was there first time (I think) so they will get experience from this and I hope they will create their next round in a better way. Thank you for the contest.
I say this is not malicious, because I use a trumpet, just hope that the questioner can create more rigorous data in the future, C does not have longlong data even if it is counted, B question and even the wrong algorithm can pass pretest, of course, it is undeniable that I think the quality of this topic is good, but pretest is difficult to say
Yes, so true. My code for C was hacked as I used int instead of long long. If the pretests had one of that case, my delta would have been positive. Never thought that there would be a contest with pretests not having overflow case.
I participated in div 3 yesterday but i have received no rating so far. Can anyone help? It shows the contest in unrated section for me but it was definitely rated.
There is a 12 hour open hacking phase that ends in an hour and a half, then it takes a few hours after that for the rating to update.
Could you please explain what this hacking thing on codeforces is? I couldnt find any answers on google. I am very new to all this.
Sure, look here: https://codeforces.net/blog/entry/6249
In short, the open hacking phase is the (12-hour) period after some contests where people try to break other's solutions for more points. If your solution is absolutely correct, you won't have to worry about being hacked. On the other hand, is there is a subtle bug in the program, someone might want to exploit it to break your program for extra points.
Oh my god! So other people can exploit my code too. So can i also hack other people's code when the contest gets over?
It depends on the contest but for this one, you have only 20 mins left to try.
Also note that if you unsuccessfully hack the code there might be a penalty, so only do it if you're sure the defender's code is truly exploitable.
There are no penalty for unsuccesfulls hacks neither extra points for succesfulls ones
Oh I see, thanks for letting me know.
Too weak testdata. How can 4000 codes be hacked in one round?
The hack mechanism became an excuse for the proposer to perfunctorily provide data, so this round became hackforces.
So why so many hacks were ignored?
Why my submission https://codeforces.net/contest/1846/submission/212766857 for E2 is giving TLE. Can anyone tell what could be the reason and how can I resolve it.Thanks
my solution: https://codeforces.net/contest/1846/submission/212781080
Try to use pypy, fast IO and main() function to speed up your code, also dont keep computing the powers, save the results
When the final testing will Start?
Can someone clarify why it is allowed to have less than 3 players for the B problem. The problem statement states "Either exactly one of the three players won or it ended in a draw", which implies 3 players every game.
i have a feeling that "draw" doesn't always mean draw. it might also means either the game ends prematurely or the sequence of playing is arbitrary which means there is a chance a player doesn't get the chance to play
They mention classic rules in the question, so sequence of playing cannot be arbitrary.
The testcases don't fit the statement. I pointed that out when testing, but it went mostly ignored (except for the fact that more example testcases have been added.)
A part of my feedback:
"No complete game can ever have more than 2 dots. Some testcases do, though.
Improvement options: Personally, I would remove all games from the test cases that have more than 2 empty cells. If you feel lazy, you could also change the problem description, so that it is clear some games have not been finished. Maybe add an example that shows a mostly empty board in that case."
Am I the only one that thought he had his best div3 contest just to get hacked on 3 problems xD?
Feel for you...you were 10 rating short of actually escaping the contest
The predictor after the contest said I would get +50 now -100 xD
Can you provide link to that predictor?
It's the codeforces carrot extension on chrome
Did anyone use bitmask dp for G? I understood the Dijkstra approach
Problem G hasn't got the precondiction of using bitmask dp, cause the order of using medicine does affect the result. And if you multiply the number of medicine for twice, then work the dp, you'll find you cannot control whether some medicine is used for exatly one time.
The following testcase is not possible in tic-tac-toe game and in problem(C) it says it has classic rules.
In the problem B, why this case is valid?
XXX XXX XXX
in the problem statement it is mentioned that
Rudolf has a 3×3 field — the result of the completed game.
how can this test be result of the Game where one player is making all moves?
Also, All the sample tests are maded in that way that one player is making move after another.
If it is valid test then I think it was better not to introduce this problem as 3 player Tic-Tac-Toe gam
Yes. The even mentioned one of the three players in the problem statement.
In the problem C, a lot of people get hacked by testcase 10 ( including me ), But Why ? My Problem C Code
overflow
but i
define int long longalready~Give input 20 "1"s and your code gives 11 as output. but the output should be 1.can someone help me with this submission, I don't know what I'm doing wrong here. 212786771
res = (res*x)%p sometimes can't detect overflow. I have a problem with overflow in E2 too and still don't know how I can fix it.
already did the overflow check before every multiplication though. ill put a check on sum as well
So amazing that my problem C is hacked because I wrote int,not long long.
I cannot possibly believe that the setters put no testcase against integer overflow in problem C. At this point we might just as well have no tests at all during the contests and let everything be decided by hack testcases. Whether this be a terrible oversight by the authors or a conscious decision to join in with the recent trend of pointlessly weak pretests, I want to say (having being robbed of at least 200 rating points by dumb FSTs) that this ruins the fun for everyone and, in my opinion, has made the quality of codeforces rounds plummet in the last few months.
i think if you want to get higher rating, you should be able to estimate that 2*1e5 * 1e6 > int
Which is why I said it was a dumb mistake, which should have cost me 10 minutes of penalty, not +144 instead of +215 rating points. It has never been the point of competitive programming not to let the contestants have feedback on their solution.
My submission of problem E1 got hacked because of tle when I had submitted in C++ 20, but when I made the same submission in C++ 14 it got accepted. Please look into this, as many people using C++ 14 would have their submissions accepted. Submission- 212621824
G is definitely a good problem
Layman trick for E2 I found right after contest ended ! —
For
i <= 10^6: brute force similar to E1.For
10^ < i < 10^9: it can only branch out one time before the result goes over10^18So the geometric series can only be of the form
1 + i + i^2 = n(remaining terms would make the sum exceed the constraint onn)Now it remains to find an
ifor which1 + i + i^2 == n. and we have to do it quickly. so after modifying the above equation it becomes(n-1) = i*(i+1)which can be evaluated quickly by taking square root ofn-1, saykand checking ifk*(k+1)is equal ton-1solution link — https://codeforces.net/contest/1846/submission/212697488
did same but got tle pls check this solution https://codeforces.net/contest/1846/submission/212799364
Check the dp part of my solution You are probably TLE-ing for cases where
nis below10^6In my solution I have precomputed all the valid results for these
my code failed for 1048575 . OJ says answer is yes. But it is greater than 10^6 . it's root is 1023. Multiplying it 1024 does not give n-1 .
the sqrt trick applies to
10^6 < i < 10^9and for these cases n would have to be close to
10^12 (1 + 10^6 + 10^12)n=1048575is added byi=2which my solution is checking by brute forceCan someone please make me understand this: in E2 the constraint on N was 1e18 even if I get O(1) approach for each value of N then also the solution would be O(N) and the time limit asks us to find a solution in multiple of 2*1e6 (because 1 second mean 1e6 operations) so how is the solution possible ?
how will be O(N) if you are doing it in O(1) it will just be O(TC)
В рейтинговой таблице отражается, якобы все по нулям, хотя во время самого контеста было решено 3 задачи. С чем это может быть связано?
Проходит тестирование на новых тестах
this is not fair, my C got accepted in contest time but in system testing it got failed. This is not my error.
Your code was not correct for all testcases
It's failed due to integer overflow, but in contest time it got accepted
System testing includes running your code on some new testcases, it is your duty to make sure that integer overflow don't happen given the constraints.It's frustrating but happens with most of us sometime.
It's too frustrating, like if we get this wrong in contest time itself, then may be we correct it. But let it go. Thanks
Yes it is. I understand
During the competition I submitted the first 4 problems and got green on them but today two of them are red. Can somebody please help me understand what's going on? I am really confused right now
System testing is going on. All submissions are being rejudged based on successful hacks testcases. But as I can see, your solution for problem C has failed the system test and D one is waiting to be judged.
wow, amazing FST round. Some problem's pretest are weakly.I hope you will pay attention to strengthening pretest in your next round.
weak pretest make this round worse
7.7:rank:4000 7.8:rank:2000
7.7:rank 4800 7.8:rank 9300
oh, no!
WeakTestContest
The main character clearly has an identity crisis — sometimes he's Rudolf, and then other times he's Rudolph. :)
Is there a way to challenge a problem? Question B clearly states that the game follows the classical rules but with 3 people instead of 2 yet some test cases have the same player winning multiple times. This never happens in regular tic tac toe. With this my code did not work:
If I had put return statements in each if statement this would have been right. This question was worded absolutely horribly.
But even in samples was an example of game, which can't be obtained by standard way.
Where are the rating changes
Weak testcases ruining my rating
Does anyone know what B test 25 line 52 is? My solution was accepted during contest but now its rejected and I can't see what's wrong
You made the same mistake as me my friend. It turns out that a player can have multiple "3 in a rows" in the table. You must have had two outputs for one test.
oh man thats really unlucky how were we supposed to know that was a valid input LOL i assumed all inputs were valid tictactoe boards
I wonder if they made the test data using their feet.
is round unrated?? why no updates. lazyforces
Every Div.3 Round updates rating after 1 or 2 days
1
+++
+++
...
?????? ?????? Это корректная тестовая дата? Каким образом такой результат может встретиться в игре? Я понимаю, что это в первую очередь проблема моего кода ( выводит два "+" ), но тем не менее
why my submission is giving TLE on updated testcase. submission:https://codeforces.net/contest/1846/submission/212665339, please help
Because of Python
This is so bad, if the setters would have given a testcase, i would have coded in C++, such an awful contest Edit: I modified taking input by sys.stdin.readline() to make it faster and got Accepted.
This is not the problemsetters' fault, you should be aware that Python is much slower than C++.
You did not use fast input. Either way, it will also get TLE with fast input, I tried it. In Python, Sometimes an optimisation from O(N log N) to O(N) can be the difference between TLE and AC
935ms / 1s isnt a good runtime for an accepted solution. It can get TLE sometimes when submitting
is this gonna be unrated because crybabies cannot read the statement and say pretests are weak?
So, I got WA30 because of integer overflow. The way to easily fix this is adding __int128 but for some reason it was not available to do so (when I submitted my code in test system it got CE). If someone knows which compiler to choose to avoid those issues, let me know
To fix the issues with overflow I simply used the following convenient functions:
__builtin_smulll_overflow,__builtin_saddll_overflowHere is how I used it to pass tests (after my initial solution failed miserably)
Hope it helps someone!
My E1 solution didn't give TLE on C++ 20 but it gave TLE on C++ 17 which I submited during the contest, what is the reason? Can anything be done now :(
Can code be rejudged for C++ 20 compiler?
Using
long longwith a 32 bit compiler will be slower than with a 64 bit compiler, if you had selected C++17 (64bit) it would probably have been accepted.should not even then it should be slower by 2 times only , c++ 20 code runs at 600 ms while c++ 17 gives TLE at 2000ms , which is more than 3 times difference
I don't know how much slower it "should" be, where did you get the 2x from? It depends how much of the operations your program does are on long long, and the operations themselves of course make a difference, whether it's loading/multiplying/etc.
Just wondering, when will the editorial be released?
Idk whats going on with this contest, after hacking phase already over and final standings were released, it automatically changed to wrong answer in E1, can they change the test cases or what not even after the final standings?
That means your solution E1 was hacked
After the hacking phase was over it still showed accepted, abrupty after some hours now it shows wrong answer on test 10 ,not even hacked
.
There E2 limitations and overflowing got me some headache =)))
Hope my next contest will be greater ._.
Why Wrong answer on test 31 in E2?
I am pretty sure that it happens due to floating point arithmetics. I would rather recommend you to come up with the approach that doesn't use it (but I do believe that there is a way to find a workaround).
Try to test numbers manually, finding acceptable k and max_power.
Finally I wrote a script to generate all acceptable N numbers. That file weights 17GB and all my tests run about 4 minutes:) But I receive AC today after debugging a rare uint64 overflow case in C++ solution while the same PyPy solution gets TL.
Good luck!
can someone please explain the solution and thought process behind problem G, I find it hard to imagine how we will construct the graph and please link some practice problems based on Dijkstra from CF.
There are at most 2^10 = 1024 different symptom combinations (states). You start with your initial symptoms, apply all possible medicines and see which different symptom states you can get to in one ‘move’. Put all these new states in a priority queue and pick the next state to explore as the state from the queue that a) you have not explored yet and b) that you can get to in the least number of days (hence the priority queue). For the next state, you once more apply all medicines, and so on. You do this until you reach the state without any symptoms or the queue is empty in which case there is no solution.
Weakforces
I think the test case XXX XXX XXX should be invalid. According to the problem statement, this test case is invalid, because it means that the same player is taking consecutive turns.... in my opinion it should not be considered as a valid input
Hi, I Have question regarding this contest. In b question it was stated that classical rules are applied. But the test case on which my code was hacked is .+x .+o .+x which can never exist with classical rules. Please clear my doubt.. If it cannot exist with classical rules why it is considered for test case?
I am very confused, I just feel like my G should not be a correct solution. Can anyone give me a testcase that my code gives a wrong answer??
Can anyone tell me why my code on problem C fails? Thank you.
vector<pair<pair<int, int>, int>> resultpinresult:p.first.firsttells the problems a participant solved,p.first.secondtells the total penalty, andp.secondtells the index of the participantMost Likely a case of integer overflow(my solution also failed system testing on test case 6). Change p.first.second to long long and it should work fine
bro I used
#define int long long, that's not the reason why my solution failedbro, you still have integer overflow lmao: 214018157
It is because you are accumulating the sum into 0, which is an integer. I changed 0 to 0ll to avoid overflow, and now your solution passes. 212883277
Can you speak Chinese
Don't post meaningless messages here. You can speak Chinese in "Talks" module.
it seems that you played too much genshin impact. here is my suggestion:
This contest taught me to take all the possible precautions and not necessarily trust the problem statement.
please update problem ratings.
Is this round unrated? The ratings I received from this round had been disappeared.