Hello, Codeforces!
On Jul/07/2023 17:35 (Moscow time) Codeforces Round 883 (Div. 3) will start.
You will be offered 8 problems, dedicated to the adventures of a restless mathematician, a programmer and just a funny character named Rudolf, and 2 hours 15 minutes to solve them. Problems have expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.
The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.
Note that the penalty for the wrong submission in this round is 10 minutes.
Remember that only the trusted participants of the third division will be included in the official standings table. This is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:
take part in at least five rated rounds (and solve at least one problem in each of them)
do not have a point of 1900 or higher in the rating.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.
Problems have been created and written by: vladmart, Sasha0738 and natalina.
We would like to thank:
Vladosiya for coordinating the round.
MikeMirzayanov for Polygon and Codeforces platforms.
Sugar_fan for red testing.
74TrAkToR, zwezdinv,Sokol080808,senjougaharin, FEDIKUS, Lucina, vrintle for yellow testing.
pavlekn, diskoteka, Phantom_Performer, bigDuck, Evirir for purple testing.
KoT_OsKaR, HappyChau0v0, bugdone, Termii, t0rtik, Rudro25, O_E, jhorvat, sohelH for blue testing.
ctraxxd, 666EGOR777, Guevara74, stefanbalaz2, jojonicho, hussein_auf for cyan testing.
Good luck!
UPD: Editorial is posted.
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.
Watch your words
support
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.
You are right.I pass this problem by the rules of how to win.Because whatever case X will win.But I think thia case couldn't valid: ooo xxx +++ I think this case must be talked by problem.
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?
In the example itself there is one without the classic rules, .++ X.O +.. so that's a hint to better overlook the statement and focus on finding a winner if any.
vladmart Sasha0738 natalina was this intended?
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
In B, fifth testcase on sample test gives us information it is not guaranteed that inputs are only provided real 'Tic-Tac-Toe' way.
tc5 for sample test: .++ X.O +..
O : 1, X : 1, + : 3
This is the reason why I thought the positions with '.' are to be filled recursively with all posibities which made some games in the sample not DRAW.This is a serious problem imo.
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.
Idea 1 has worked. Thanks for hint
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.
Waiting for this. Best of luck to all contestants
As a tester, this problemset has some amazing problems!
Hope to reach close to "Cyan" after the 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
xD
First unrated div3
Congrats
Thanks
As a tester, please join this round :)
is it hard or something?
Although I was unrated for this game, I still wanted to participate
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
Here before the "Hope to reach expert this round" comments.
Good luck！
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
I can't do it because I AM IN SCHOOL NOW!
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
All The best to all the competitor...
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
Thank you for the extension link. I had another extension for prediction, but it stopped working recently.
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.
It's div3 so there will be hacking phase also so almost 18hr you will expect
Thanks for the contest ...for the first time i was able to solve E in contest
have they all been accepted? nothing hacked or failed in system testing?
Yep..
So Rudolf and Rudolph are like brothers?
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
congratulation bro for being expert and thank you for the help
why i do how you and it doesnt working https://codeforces.com/contest/1846/submission/213026873
why i here get overflow if i check max degree what i can exp without overflow https://codeforces.com/contest/1846/submission/212999512
here i change fact pow function type https://codeforces.com/contest/1846/submission/213006542
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.
No, It was a singular B.S. problem. There are at max 60 possible powers of k.
I.M.O. you can't B.S. on possible powers of k as you can't be sure if Mid value fails whether you should use more power of k or less power of k. as base number is not constant
You can guess the number whose exponents we are adding should be moreOrLess though. as k is kept constant
i ,myself am not sure if this explanation is sufficient, you can look at this submission for more info : https://codeforces.com/contest/1846/submission/212833690
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.com/contest/1846/submission/212691145
you have wa1 you can fix it
Kinda MathForces round but Enjoyed solving A ~ E1 :D
worst feeling when you know how to solve the problem but could not implement correctly.
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
You can use cout << fixed << setprecision(10); and make sure you use long double.
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
same i just ended up using python
Who all thought that the problem A was inspired from Cut the Rope video game?
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
Thanks
.
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.com/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)
how to solve G with dp?
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 thought it more like taking a medicine gives me some symptoms, if in the shortest path I take some medicine and its symptoms as well, why would I want to take the same symptoms again, all in my head no proof, if someone has any proof can you please clarify?
i was wrong.
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
oh
Great!
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 :(
the amount of high-rank newbies is insane. There is no chance to get rating for honest newbies like me. I am very disappointed with that. Every time I think I do better there are tons of other people solving the same problems. In this way is really impossible to increase rating and this is very demotivating. Finally there is no chance all the cheaters will be caught, so that's the story.
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
what 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.com/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+=sumoh yeah Thankss
Can you explain test case 4 of problem C to me? I think Rudolph should get first position in this case, since both 1st and 2nd candidate have 17 minutes penalty
penalty is not the time taken to solve the problem . it is the time taken from the start to solve a problem . If time taken by Rudolf is 8,9. penalty for first problem will be 8 for second problem will be 8+9 So total penalty is 17+8=25.
Ohk yes
I 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
you can sort pairs in set like {-points, penalty}, but in this problem have to use multiset, i can't got it till end of the round.. agh.
p1.first contains-> Count of points (sort according to decreasing points)
p1.second.first contains -> Penality (sort according to increasing penaltiy)
p1.second.second contains -> Rank (As Our participant no. is 1) so, we can sort according to the increasing rank.
overkilled it
Screencast of the round, I tried to explain my ideas, if someone needs that
https://www.youtube.com/watch?v=dvNKBeTtlY4
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
when i realized task G need f(n)^2 complex to build the graph instead of f(n),there was no time for me to finish the DIJ XD
when u implement a good high school maths concept , (similarity for finding the smaller parallel side of trapezium), in cf contest, the feel is different!!
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.com/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
Can anyone help me why my code is causing RunTime error on Test case 5 ? https://codeforces.com/contest/1846/submission/212693233
here,removed one charcter from your comp function: 212712986
Thanks a lot, I never knew about this.
Due to the wrong declaration of comparators.
Binary predicate that, taking two values of the same type of those contained in the list, returns true if the first argument goes before the second argument in the strict weak ordering it defines, and false otherwise. This shall be a function pointer or a function object.
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.
Thank U
Probably the Worst DIV 3 I ever gave
i really liked the geometry behind problem d
is there a hack for this solution of problem G?
UPD: Hacked
i did bruteforce in e2 try to hack my sol if you can :-https://codeforces.com/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
I saw a code pass with just 10 iterations, can you explain your reasoning for this?
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.
thanx man! didnt know just those 2 lines would make this big difference
What is the Hack case in problem B?? So many Hacks!!!
people are missing '.''.''.' this case as it can output draw so,put a condn that when you are winning cgaracter should not be equal to '.'
+++
...
...
Not only for B. There are so many hacks, afraid...
For My Case it is +++ ... ...
What is wrong with my Problem C code ;) https://codeforces.com/contest/1846/submission/212661976
In your comparator sort function replace <= by <
Can you please tell why when comparing with <= gives runtime error (out of bounds). Thanks in advance.
Change the <= in the comp function to <
Still gives WA
One more point, Issue is when you are doing sum = 2 * sum + arr[k] So that means we are adding previous sum, But previous sum != total time spent it is total penalty which is different from total time spent.
Accepted Solution using one extra variable to keep track of total time spent
It worked, Thanks!
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.
good luck!
Спасибо
it's easy to notice that all the hacked B code are the same
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.
Agree. Only thing I would add is that I personally found It a bit easier if compared to other div3.
if u use python Problem D only teaches basic geometry
finally expert.... yayayy
Good JOB my friend! Try to keep this rate and reach candidate then ;)
Congrats For Expert
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.
When will the editorial be out ?
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.
I get there are other ways to solve it, but my problem was that there is little to no difference between my accepted and TLE solution... The whole point was the logic which was the same for both either ways even if I did think of that approach this and that would've been written similarly even your solution is O(n*m*log(m)) regardless...
Two problems here:
penoverflows then it becomes negative which will give a verdict of WA. SubmissionI know about the overflow like I said I would've figured it out regardless, also thanks for the blog seriously this should be mentioned in sites like gfg and others because I learnt custom comparators from there, just now read the documentation and realized. It wasn't logically wrong but nevertheless a mistake and it's how it works. Thanks a lot again! Basically learnt this the hard way... Kinda sad as I could've done 5 problems ABCDE1 but got stuck with C and finished just ABD.
From 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..
Can Anybody Tell Why My Code is giving wrong answer on test 3 https://codeforces.com/contest/1846/submission/212736306
A nice and interesting contest in general, but I wish that pretests were better, some solutions don't use long int or conditions and still pass the pretests (problem C)..
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
Lol this is like codeforces asking you to change your username as it belongs to someone else after you successfully registered for it. Ironical!
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!!
Honestly. I don't understand why no one is talking of this. Understanding F is way more difficult than solving it. It's like the statements were written in some non English language and just put in a translator.
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
this could be my dream only if I accepted problem C
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.
Yes, you are correct. I misread it and the note 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
Indeed weak test cases.
My submission/212771298 passed the pretests, and nobody hacked it too.. but when I re-submitted my code after hacking phase it gave WA on #10.
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.com/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.
Oh ok. Thanks a lot for taking the time to explain it to me.
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.
Teach you a more effortless way to create data.Just one ZERO.and then wait for the contestants to hack each other XD
I accidentally read problem C incorrectly. In my understanding, it was that question's points can be uneven i.e. not the same for all questions and points are non-negative. So I needed to maximize points first, and after that for all maximum points choose those questions whose combined penalty is less close to the total time. Can anyone help me with how to approach this problem?
Did I miss something that was posted? For question C I was looking through the responses during the open-hacking to check whether or not my own algorithm had any errors, but quite a few of the responses in C++ are the exact same down to typos, variable names, and formatting.
Was this question previously solved / present in another round?
In problem B, it appears that many people have misunderstood the problem. The problem statement states, "It is guaranteed that multiple players cannot win at the same time." However, some individuals mistakenly interpreted the character '.' as a player, leading to their incorrect solutions and potential vulnerability to hacking. If the test cases continue to be weak like this in every Codeforces round, I am hopeful that I will soon reach the Pupil level.
how to say "you are wrong,here is why" XD never wanna see this again
can someone help me with why my solution:https://codeforces.com/contest/1846/submission/212766857 is giving TLE for E2.I cant find out whats the problem
My solution for Prob. C got accepted in the contest.. and nobody hacked my solution too.. but after the hacking phase I re-submitted my code and it gave WA on test case #10.
Someone please check my Submission.
doesnt matter if you didnt get hacked directly. After the hacking phase there is a new set of tests (created merging the old one and the hacks) and sadly against this new test set your solution fails. If you look carefully problem C had initially only 5 TC, now there are more (as you can see you are failing on test 10)
So my code will fail system testing, right?
I think yes
Why my submission https://codeforces.com/contest/1846/submission/212766857 for E2 is giving TLE. Can anyone tell what could be the reason and how can I resolve it.Thanks
in python, there are no integer overflows, instead python tries to calculate those numbers resulting in tle. you should optimise your code. for example: instead of mid = (low + high) / 2, use mid = low + (high — low) / 2. You have used power operator many times too.
my solution: https://codeforces.com/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?
why im not rated? all users under 1600 are rated, why I get 0?
wait
Look forward to the Editorial!
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
Is the system testing over, or is it yet to happen?
Same thing I am trying to figure out
[EDIT]: I dont think it has happened yet, but if you run your codes they will run against the new tests, so you can see if they actually pass or not.
As a beginner I didn't enter
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.
Yeah that's true I asked since I saw some submission's with trivial bitmask dp with some extra iterations pass
Can you please link those submissions with bitmask DP. I tried to solve G like that as well but it gave WA.
212683099
The following testcase is not possible in tic-tac-toe game and in problem(C) it says it has classic rules.
Can someone tell me what is wrong with my code for C; 212651784
Edit: Well, i didn't think about long long. :(
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 longalreadyI wrote it a different way (
long longalready ), but it still Wa on testcase 10, C Code2~Give input 20 "1"s and your code gives 11 as output. but the output should be 1.thinks！, I know what I did wrong
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.
I mean checking the constraints is your job, do you write a brute force solution and blame the setters for it not passing?
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.com/contest/1846/submission/212697488
did same but got tle pls check this solution https://codeforces.com/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
Dang
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 forceI am newbie my rating was 348 before contest so it shold have been rated contest for me but it is not reflected in my rating . and when i view my contest it is mentioned in unrated why?can someone explain this to me
It will update soon
my rating has not been updated yet, i saw a person whose rating got updated. Anyone know why is that
I think you misunderstood something, nobody has received any sort of ratings for the round as of now. System testing is going on, you may receive updated ratings soon.
Can 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)
Thank you, I did not see that the test case was 1e4
this is the worst scenerio I have ever encountered in a cf round, such a weak testing from the setters. very much dissapointing.
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.
Thanks for the help! pcajourney
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.
Absolutely abhorrent pre-testcases ruined this round for myself and many others. CF needs to do better.
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
If you see example test case-5, then that input was also not valid. So, by that, you can get the idea that tic tac toe can also have invalid inputs. Now, if this is fair or not, I can't comment on that.
me too :(
Nah i thought ill get positive after so long, only to get 2/3 failed after system testing ,Baited me so hard
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
hahahahahahaha
why my submission is giving TLE on updated testcase. submission:https://codeforces.com/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
my two solutions got WA, 'cause of int instead long long(((
Test for this round before contest end is super super bad. So we got 1e9+7 fst
Explanation needed for problem B
In the problem statement it is clearly stated that the game is played with classic rules except for player 3.
In classic tic tac toe, the players take alternating turns, if the game is classic tic tac toe, then this testcase:-
...
OOO
...
shouldn't be valid
Yet many hacks have been performed using testcases like this one
I request the setters to resolve this issue.
Look at the fifth sample test case.
The issue still remains
I am just trying to point it out that the problem statement had a flaw.
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!
Someone please help in (https://codeforces.com/contest/1846/submission/212796957)
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 ._.
[deleted]
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.
Why is this test case valid? +++ +++ ...
Why has my 3rd problem been hacked? How do I know what went wrong
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?
My Solution does not work in Java 11, gives tle,
but works in Java 17,
why is this?
got negative delta :/
task 3
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
I have a question about the task C. Why on the test 5 5 14 7 2 9 10 3 5 3 2 9 7 6 1 10 5 7 2 6 9 10 4 10 5 7 8 9 answer is 2(not 3)
XXX
XXX
...
This test case wasn't included while contest and my code got accepted as well...a day later it says it fails on this one...
hmm
nvm
These problems are so cool :D
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:
When can we expect next Div. 4 round? I hope most of us are desperately waiting for the same!
yes, i've been wanting this for a long time too.
This contest taught me to take all the possible precautions and not necessarily trust the problem statement.
please update problem ratings.
212673391 I think i have used ideone in public mode by mistake and i was unaware that someone can see my solution there thats why my solution has been copied by somebody/ or it can be an absolute coincidence, i am use my vs code ide for solution then i submit my contest solution in a file format and i have clear evidence for that ..like i have also file in which i have written my code and save in my device. i use ideon for one two solution which get copied in this contest so pls remove my plagriasm and please give back my ratings. so that's clear that im not use any other code,and my solution has been colliding with other guys and there is no fault of me and sorry for this but I will take care of it from next time while using ideone.
Is this round unrated? The ratings I received from this round had been disappeared.
Not Able to solve any question very much disappointed after spending 1 hour and 45 min
Hi can someone help me debug my code for problem C. I am failing on test case 6 and I don't understand what the problem is. I know I'm asking for a lot but any help at all will be highly appreciated.
https://codefile.io/f/LwzrxjcTxT
not able to see your code... pls check!!!
include<bits/stdc++.h>
using namespace std;
void solve() { int n, m, h; cin>>n>>m>>h; vector<vector> time(n,vector(m));
for(int i = 0;i<n;i++) { for(int j = 0;j<m;j++) { cin>>time[i][j]; } sort(time[i].begin(), time[i].end()); } vector<pair<long, long>> score; for(int i = 0;i<time.size();i++) { long long points = 0, penalty = 0, sum = 0; for(int j = 0; j < time[i].size(); j++) { sum += time[i][j]; if(sum > h) break; points++; penalty += sum; } score.push_back({points, penalty}); } long long rank = 0; long long po = score[0].first, pe = score[0].second; for(int i = 1;i<score.size();i++) { if(score[i].first > po) rank++; else if(score[i].first == po && score[i].second < pe) rank++; } cout<<rank+1<<"\n";}
int main() { int t = 1; cin>>t; for(int i = 0;i<t;i++) solve(); return 0; }
here you getting compilation error void solve() { int n, m, h; cin>>n>>m>>h; vector time(n,vector(m));
214244452 check this
Thanks for the help!
you can paste the solution here