Hi Codeforces!
We would like to invite you to participate in Codeforces Round 984 (Div. 3) on Nov/02/2024 17:35 (Moscow time). You will be given 7 problems and 2 hours and 15 minutes to solve them. The penalty for an incorrect submission will be 10 minutes. There may be interactive problems in the round.
The round will be ruled according to the standards of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, there will be a 12-hour phase of open hacks. After open hacks all accepted solutions will be rejudged on successful hacks. We've tried to make decent tests — just like you, we'll be upset if you have dropped solutions after the end of the contest.
Reminder that only trusted Division 3 competitors will be included in the official results table. This is a forced measure to combat unsportsmanlike behavior. To qualify as a trusted Division 3 competitor, one must:
- participate in at least five rating rounds (and solve at least one problem in each of them)
- not have a point 1900 or higher in the rating.
Whether you are a trusted Division 3 participant or not, if your rating is less than 1600, the round for you will be rated.
The tasks were authored and prepared by a team consisting of Seny, eugenechka.boyko.2_0-0 and myself.
The round is based on the recent Lipetsk Team Programming Olympiad for school students. Please note that if you are a participant of the Olympiad, you are not allowed to participate in this round. Thanks to the coordinator of this Olympiad myav and the author Small_machine, whose tasks were not included in this round due to their high complexity.
We thank very much:
- Vladosiya for excellent coordination
- 74TrAkToR, Sokol080808, FBI, ssor96, itz_pabloo, IceHydra, justlm, SashaT9, nirjoy_139, lorenzotinfena for testing the round
- MikeMirzayanov for creating the wonderful Codeforces and Polygon platforms.
- You for participating!
Looking forward to Round 984. Let’s have a good contest. Good luck, everyone!
the contest was BS
BS?
Biased
Binary Search
I wish I could approve more than one time
I've never seen bad contest like this.
I hope we have better Div3 contest next time
please answer that if i had submitted a solution just before time up and it is running test cases and after time up the solution was accepted, will it be counted or not
If you submitted before timer run out, then solution will count
As a tester i almost became a tester and I am happy about it.
As a non-tester, I did not test it.
as a tester, i can assure you that these problems are, indeed, problems!
As a !tester I think you will like the problem sets
Even though I will be considered a trusted participant, when I'm trying to register, it says, "You are registering "out of competition" reason: rating should be between 0 and 1,599 in order to register for the contest." Why is it so?
your rating is $$$\ge 1600$$$, so you are an unrated participant
Then what about the trusted participant thing mentioned in 3rd paragraph? More than 5 contests and <1900
About the results table of the round.
The max rating not at 1900 or higher imo is to cross out the scenario that someone already participated a lot and had a high skill ceiling that purposely threw their ratings down to oblivion just to be rated in Div3/Div4.
In short, preventing smurfing from legit/long-reputated account.
But in fact, unrated participation is a way to increase your rating on your second accounts. So, we already have a lot of cheaters.
True. Honestly those measures hold more to the moral ground than actual enforcement. That's something, but not perfect.
I pray that we will not have an unrated parc. in div2/div1.
But we can do something like you can't create more than 1/2 accounts from 1 mac-adress.
that will be cool
bro,it's DIV 3 let it be for us for beginner.
as a tester, i want to sleep, i hope you enjoy the tasks
hope to enjoy this round
we hope so too:D
what is the difference between div1, div2 and div3? Is it only the level of difficulty?
Yes, div1 is the hardest, div2 is slightly easier (often, div 2 contests run in conjunction with div1 contests, where the div 1 contest starts with the div 2 C problem), then div 3 is easier (I'd say div 3 E is equal to div 2 C in a lot of cases), then div 4 contests (which aren't as common) are the easiest
thanks...
Finally! An adequate round without pendochinese authors!
With love to my kittens
I SHALL RETURN SPECIALIST
I don't know what you mean...
promlems❌ problems✅
thanks
.
chill dude just a contest
Agree. I got 4 pretests passed without an hour of the contest. But two of them (C andD) failed system testing and i went from +100 to -25
worst presets.. worst problem pattern.. worst contest
2 of my solutions failed system testing because of weal ass pretests.
hi guys i want dat delta tomorrow watch me ok i become the 500 rated directly or maybe 600 as well please watch ok ok i am curt btw i am
As a time traveller, this round is going to be historic. Also, the replies to this comment will be filled with "this aged like milk" after the contest. Good Luck!
You, sir, are a genius.
nah, I am just a sleep deprived a-hole.
aiming for pupil this round
No interactive problems pls T_T
Good luck everyone :)
Hope to be expert soon.
Guys, can someone please provide me the standard template for an interactive problem, it would be of great help.
Why would you need a template, just remove the fastIO part of your template and thats it. You can also make a ask function, so you dont have to type out the interactions, but thats it. Also dont use endl in your normal code, use \n, its much faster.
Thanks Brother, can you just explain why to remove the FastIO part?
since it messes with the input and output and puts everything at the end, you cant interact properly with the system because you cant output the questions in the middle of your code
Can't you just use cout.flush() after every output in cpp along with the fastio part?
yea, i think you can, but that makes the output the same speed as if you didnt have fastio, and also you have to constantly put flush after every cout, which is a hassle imo
If you put your inputs and outputs in a single function and use them then there won't be any hassle.
E.g. query and output functions in 289277508
Let's go!, div 3 is good for me
wish to be pupil after this round.
++
I hope too.
As a contestant, I hope I don't make stupid mistakes.
As a F1 fan I hope Norris wins the sprint race while I AC div3.
I will not solve 7th problem and Piastri will not let Norris pass.
As a F1 fan i hope Norris locks up into turn 1 tomorrow and comes P11
Currently I'm facing some problem in my account. I couldn't see the implementation to anyone else's code. Codeforces shows me N/A. How to solve this issue.. Can anyone help me?
You have not made a submission on a single contest that you registered in, you cannot view other's codes. I do not know why.
I had the same problem as you , if you log in your account in another device , just log out .
I'm new to Codeforces. Is this contest useful for me?
specialist plssssssss codeforces
Where can I read editorials for the contest?
we will try to do the editorials as soon as possible, it will appear in the announcement
I hate Div3...
I hate C
i made so many tiny errors costing me like 30mins total. so much implementation for this contest
I've enjoyed F, cool problem, thank you.
we are very glad:D
nice tasks
implementation forces
What is the purpose of problems like D?
implementation practice ig
D was too direct problem, and don't really requires anything other than some implementation skill. I think problems that only ask you to impelemnt something should be avoided in a rated round, or at least in Div.3 A,B.
i felt the same, the contest was so much implementation based. i just couldnt implement D
It is possible to code D neatly, my code isn't heavy to implement.
CODE: 289531869
My code is even more cleaner for D.
Submission : 289536072
Me after reading D: wtf is this!
I spent wayyy too much time handling this Test Case lol
problem D description could have been better ngl I spent first 1 hour on problem reading question wrong this layer thing could be highlighted instead of writtenn in small font I though you have to traverse clockwise on every cell smh
yeah, I didn't understand what a layer is until I looked at the provided examples.
I hate it when the time limit for problem F is 1 second
That's cuz I guess we can do it O(1) using range xor properties.
that is true!
first of all, $$$a \oplus b = c \Rightarrow a \oplus c = b$$$, so we need to find xor on range $$$[0;\ n]$$$. let the number $$$x$$$ be $$$(i,\ k)$$$-good if $$$x \equiv k\ (\mod 2^i)$$$.
$$$\DeclareMathOperator{\xor}{XOR}$$$ let's try to find xor of all $$$(i,\ k)$$$-good numbers from $$$[0;\ n]$$$. firstly, all numbers from $$$0$$$ to $$$n$$$ are $$$(0,\ 0)$$$-good, and finding xor of all numbers is a popular task (you can find many implementations of it). let $$$\xor(n, i, k)$$$ be xor of all $$$(i,\ k)$$$-good numbers $$$\le n$$$. then
now, let's find xor of all $$$(i,\ 0)$$$-good numbers. one thing to notice is that $$$2^i \cdot a$$$ is the same as bitshifting $$$a$$$ to the right, so this case is equivalent to the last one with one exception. let $$$f$$$ be the biggest number, such that $$$2^i \cdot f \le n$$$. then
lastly, $$$0 \le k < 2^i$$$, so $$$k$$$ changes only $$$i$$$ last bits of a number. that is why we can deduce the following (assuming $$$f$$$ is the maximum number, such that $$$2^i \cdot f + k \le n$$$)
now, let $$$\xor(l,\ r,\ i,\ k)$$$ be the xor of all $$$x$$$ such that $$$x$$$ is $$$(i,\ k)$$$-good and $$$l \le x \le r$$$. then $$$\xor(l,\ r,\ i,\ k) = \xor(r,\ i,\ k) \oplus \xor(l - 1,\ i,\ k)$$$. then, answer to the problem is just $$$\xor(l,\ r,\ 0,\ 0) \oplus \xor(l,\ r,\ i,\ k)$$$, cause every number is either interesting or good
Very well written. I just thought of xorring f*2^i for all f such that k + f * 2i is within l and r. since k has lesser bits than ith bit, we can treat their xor independently. as for the xor of f * 2 ^ i, we can think like normal range xor but all the xorring is happening starting from the ith bit instead of the first bit so the result is just the range xor of all f, then shifted by i, and as for the k, if there are even f's then 0 otherwise k.
sounds true, when testing i just didn't want to think much, so i made the first solution that came to mind, and all work above is just my line of thought
Awesome explanation, I did the same here https://mirror.codeforces.com/blog/entry/135766?#comment-1214968 just idk how to use latex in cf, how to do this?
just put your $$$\LaTeX$$$ commands between '$'
omg so beautiful, can i steal it for the editorial?)
yeah, why not! just put credit somewhere :)
I think it is worth to note that you can seperate these operations, so to calculate the range $$$[0:r]$$$, you can first calculate the xor of all values (this is well known since $$$1 ->n+1 ->0 ->n->1 ->n+1...$$$) and then xor that with all values in $$$x$$$ in $$$[0:r]$$$ that are interesting. Their value is $$$k * (f\%2)+ (XOR(f-1)) * 2^i$$$, where $$$XOR(x)$$$ denotes the xor for all vaules in range $$$[0:x]$$$.
So for the range $$$[0:r]$$$, the answer is $$$XOR(r) \oplus ((f\%2) * k) \oplus (XOR(f-1) * 2 ^ i)$$$
submission
what (i,k) mean?
woah!!
For Problem-E, how to reduce the time complexity?
My current Implementation gives me TLE
Each Query * Each Country * Each Region (q*n*k)
CODE
use binary search. OR operation result is always greater than both operands, so flow increases over each country within a region.
Dear Lord, now I understand the solutions for E
You use bisect (Binary Search for Python) to get the valid ranges and then min-max them to get the answer
This works because
OR operation result is always greater than both operands
.Cool way to approach it. Thanks :)
use a map to contain the query of "r" changes, only check those columns to avoid TLE.
NGL, your solution for Problem-E scares me but I got the approach
Thanks :)
I'm just a pupil who writes spaghetti code haha. Oh well at least you got the idea.
here's a little cleaner version of my sub: 289704966
its not necessary though, map's constant is heavy, might be better to just binary search over range n
can you show me a submission?
I tried to implement it like this, maybe close enough to your idea 289704359
Yeah that's the same idea as mine, here's my implementation: 289709736
How is this even possible in problem G?
submission
Basically I check that my answer satisfies all condition, but I still got WA2. In rust asserts work in release code too, so I'd expect RE if my answer is wrong. Am i dumb?
probably your solution exceeds the requests limit
I also check this condition. Waiting for open tests to confirm that I am acoustic)
In interactive tasks like this one (where you can either output a answer or terminate the program if the requests are exceeded) RE goes to WA, since the participant can terminate the program including throwing any exception.
Good to know. Now I will use MLE for this purposes :)
That's not entirely true! For example the testing problem mike made back when interactive was first released correctly reports RTE as RTE. 101021-1 - Отгадай число, https://mirror.codeforces.com/blog/entry/45307
My guess is that whoever coded the validator for 2036-G - Библиотека Магии was lazy and didn't bother making an RTE display as RTE. It would be nice if CF had standarized how RTE on interactive works, but that is clearly not the case.
In the task you cited, there is no choice between outputting the answer and terminating the program to get WA (this logic is not a novelty of any of the contest organizers, I have seen many tasks where such a choice was given)
Redirecting "Unexpected EOF" (including from throwing an exception) to WA is not some grossly wrong decision. Such a possibility is given in testlib.h (see ENABLE_UNEXPECTED_EOF macro) and is marked as suitable for interactive tasks.
So from what I understand, if you don't use the macro, then if the user's program RTEs, it will be reported as an RTE.
I'd argue that reporting RTEs as RTEs is a lot better than reporting RTEs as WAs. Interactive problems are confusing enough to debug to begin with. And someone could just make a homemade MLE/TLE assert anyways.
Tried so hard,
Got so Far,
But in the End,
got 6k rank .....
Never give up, honey.
Problem D
is kind of an extension of the Leetcode problemspiral-matrix
.Absolutely absurd.
Wasted so much time on C and btw Java's substring is O(N). How on earth is that even possible! Could've solved even D if it wasn't for this retarded language.
Why to use substring which has O(N) TC. Just take 4 indices as per need as substring scans whole array I guess.
For the check afterwards if it makes or breaks the 1100s. Had to write it manually.
Uhhh no. The problem is with your
n = new String(str);
in your TLE submission.Yeah haha, that was the issue thank you
289515042
Could you please help in this one ? The time complexity is O(t(q+n)), right(ignoring the map queries) ? Then why is it taking 2999ms to run ? The time limit was 3s, so somehow managed to pass. How do I optimise it further ?
I just read through your code, there are some lines where you assign the strings
t=s
ands=t
(This costs O(n)), so it can grow to O(t(q*n)), basically.Aah, right! Thanks a lot. The t string was redundant. I could just directly have modified the character in s.
For problem C can anyone please tell what is wrong with this solution: Submisssion
I think the range is i-3 to i+3 you put <i+3 making it i-3 to i+2
Thanks, how did I not get that.
try out this test, it might help
The result is 3x YES, NO, 4x YES, NO
Did you come up on your own with this case?
of course my own, you can see I have WAs at C... then I hack myself with this test case
btw I like the way you solved E in 1 go then go back to D-C.. actually impressive which I can't do for a while (skimming problems then aim at better accuracy). For now I just doing problems in default order.
Usually I feel like I can solve problems (the logic building part) but it's usually dumb errors in my code the get me, like the above code, or my logic is completely broken. So, I prefer to move onto the next problem.
This doesn't work out in my favor when I can't even solve the next questions.
Nice to know the strat, probably when I'm stuck and figured my logic is broken, it's better moving on to the next problem. (Still have a long way to climb)
F was very good about the idea I wonder if there any other solutions
This is my solution — https://pastebin.com/BCxvvJH8, my idea was to basically first find the XOR of all the numbers in the range [L,R], and then find the first & last occurrence of number of type
x
, in the range [L,R]. Then observe if the count (number of such numbers in the range) isodd then k contributes to XOR
, else not. And the XOR of such numbers can be proved to be the rangeXOR(firstcount, lastcount). The answer would be the XOR of all these i.e.(XOR of numbers from L to R)^(XOR of numbers from countofx_morethan_L to countofx_till_R)^(k)).
[ Proof of 2nd Term in the XOR ]()
Problem F can be solved int just two steps
The final is XOR of values obtained in the above two steps
The rest lies to calculate the AP XOR efficiently which is same as this ques (http://http://poj.org/problem?id=3495)
implementation forces lol
pD and pC are exactly the same problem with annoying implement. No skill on pD, just implement, really bad problem.
I'm a happy man now after all the practice is actually paid off, result is yielded (I peaked my performance). Thanks for the div 3 contest.
Implementation, Implementation and only Implementation.
interesting F
Implementation forces sucks...
G is interesting and difficult tbh.. G2. Ruler (hard version) didn't help me to come up with some useful thoughts..
D was extremely annoying. It shouldn't have been a part of this contest, especially when spiral matrix (on leetcode) is such a well-known problem.
Even though it is a well known problem, you couldn't get AC in one go, so there is something to learn even from problems like D. Stop crying and get better.
Yes, I agree with you. We can't have contests as per our mood/need. Sometimes it balanced, sometimes it is implementation heavy sometime not...
So many people cry in math heavy contest (976 div2), greedy also cry (981 div3). Now implementation heavy also cry... (this contest)
Conclusion No matter the contest people will cry (:
If you had a little bit of brain, you'd try to think about what I'm inferring in my comment. The point I was making is that there's often a lot of cheating when popular pre-existing problems are put up in contests. That's all.
FYI, it's not considered cheating to refer to pre-existing sources on the internet in a Codeforces contest.
Right, my bad. Anyways, I still think that it is a bad choice to put up questions whose 70% logic can be copied from an already-existing source on the internet.
Can someone please explain what is expected in
Problem F
. (I didn't quite get that expression itself). Thanks in advance.If you know python, I give you my naive code that express the F problem (of course this is just naive approach)
ImplementationForces
Problem F sucked.
respects to the authors but my honest review is that the contest was 'senseless' and of less quality. I gave up when I saw C and D and realised you just need to write a bunch of code and waste lots of time debugging (you could say I have implementation skill issue). D was also soo similar to spiral matrix on leetcode. I just felt demotivated moving forward.
Maybe I have to work on my implementation but traversing a grid in some beautiful way does not improve my thinking.
the contest was BS
BS forces
BITWISE-forces :D
I appreciate the effort of the authors of this contest, But the problems were not that good, I feel like I didn't learn new things in this contest or even have fun while solving the problems as they were just implementation, and other problems were very standard problems.
it's just a contest out of millions next contest might be based on something else
its div 3, I don't think you should necessarily need to understand advanced data structures to do well. As a noob im happy to get more implementation practice like this.
Yes, but I mean that it needs different topics to cover not just implementation and brute force. its div.3 not div.4
Thanks for the criticism. Yeah, the first part of the contest is probably too trivial, and the second part is too difficult for most of the contest participants, although interesting
If I venture to come up with more problems in the future, I'll try to take into account all the mistakes with this contest
I really appreciate your efforts, It's your first contest as a problem setter, So it's great as a beginning, I am waiting for your next contests. Thanks, a lot
Based, +1 for the heads up
appreciate how you took the feedback. To add, it would have been okay if it's div 4. We look forward to your next one :). P.S: Thanks for showing me I need to work on implementation though lol.
This guy is gold in taking criticism.
How to solve C ? what is the best complexity ?
O(n+q)
I kept track of number of occurrences, and for each query checked if it would make or break an occurrence, by checking the bits around it.
I was accepted with O(N + Qlog(N+Q)) using set 289529638
Influence of changing one bit only reaches a few segments of length 4, so each query can be processed in constant time after you have calculated the initial amount of 1100 in linear time.
What is the intuition behind your solution ? Why do you subtract count of "1100" before change ?
count the initial number of 1100 and for each query you just have to check 4 bits around the change
In Problem G, why is this (https://mirror.codeforces.com/contest/2036/submission/289601805) code giving Idleness limit exceeded error?
I am flushing after each
cout
. Besides on my local compiler it is working fine (can it be possible an interactive problem messing up in submission verdict but working fine in local?)I think it's the synchronizing thing, I had this kind of issue before. See this submission with the synchronizing thing giving
Idleness limit exceeded
and this submission without the synchronizing thing giving WA (it's an another interactive task). Hope it'll help you.yep, this was the first thing I tried, still got the same error.
Besides in the links you shared, I am curious to know whys is it giving the error? Since you are flushing the stdout after each output
Can anyone help me out why this is TLE for problem E?
you create a vector of k in q queries -> 10**10 complexity
Yes I solved it now. I'm so sad man, how did I not see that?
btw why you use alt? could've comment by the main acc...
you are iterating over the whole K's in each query consider only what is mentioned in the current query
Yes thanks I solved it now.
implementationforces
.
Thank you very much for the contest.
Can someone please help me why my submission for problem E isn't working. I spent a lot of time but wasn't able to figure it out.
found why it was wrong
Nice problem F.(only problem which required thinking in A-F).
Uh, thank you. Yeah, we realized that the first part of the contest didn't turn out so well. I'll try to learn from mistakes
I hope you find G task interesting too)
In Problem F, could someone please clarify the meaning of $$$x \not\equiv k \pmod{2^i}$$$?
when you mod x by 2^i, result shouldn't be k
(x % (2^i)) != (k % (2^i))
https://en.wikipedia.org/wiki/Modular_arithmetic
Thanks, it helped, I got my doubt resolved by this statement from the wiki
The parentheses mean that (mod m) applies to the entire equation, not just to the right-hand side (here, b).
Time for me to go back to newbie.
Div3s are great contest...
I think this is a very good contest given that it targets participants with rating < 1600.
I solved problems A-E which didn't really require a lot of thinking to find the main idea but these problems did need some thinking to find the most effective way to implement solutions as well as some skill and focus to write the code and test it.
For me, I didn't consider alternatives to implement the main idea and that's why I suffered and never have a chance to even look at problems F and G.
If problem F and G requires some thinking, like a Div 2 D, then this is a very good contest for Div 3.
Can anyone help me figure out why the response from judge in my submission is negative?
submission
you are making mistake in finding the value of $$$start$$$ when $$$t = 0$$$
Yea but you can see in this submission that although the first is correct, my output is contains negative.
I still cant figure out why its become negative.
it looks like you exceeded the request limit when all three numbers are large
I think you still making mistake in finding $$$start$$$ you see you are checking this way :
1
10
100
1000
10000
this is not always the correct approach , you have to search this way :
1
11
111
1111
11111
Someone please hack this https://mirror.codeforces.com/contest/2036/submission/289514229 string parameter of check() function isn't passed by reference , so it took 2.5seconds. Later i corrected it and submitted again and it ran in 100 ms. So i suppose passing by value should result in TLE for certain test cases??
Why not hack yourself?
I just hacked it
Well done mate . Thank you
in problem D layer is defined as closed strip
also there is defined no defined start point so this means that layer is circular
so why this solution 289520489 is incorrect
Edit : the layer is circular, my code fails on some other issue
i think to calculate the number of layers we have to do min(N, M) / 2 intead of just N /2
try this testcase
1 4 2 37 47 57 17
if we do n/2 layers count will be 2 but its only 1
that's not the issue
consider this
2 2
43
51
the only layer here it is 4315
so my code will give 1
while checker will give 0.in your solution you iterate left up layer start cell from 0 to n/2-1, but correct will be do it from 0 to min(n,m)/2 (think for yourself why), so your solution will failed in tests where n>m and where 1543 is on the right side from bottom to top
can you give any test for n > m where my sol fails.
you may have access to the hack test
Print the indexes you are accessing when n >> m and you will get the error.
can you give hacking test.
The hacking case was pretty large. But I guess this testcase will give a runtime error.
I also found a tc that will give wa verdict.
The output should be 0
try this, the output is 1
some one please tell me why this python solution 289486115 gives TL
start getting used to writing code in c++) dict object in python is quite slow relative to cpp unordered_map (but still working for amortized O(1)) a python solution may exist with using list with indexes as bottle types (but im really still not sure)
yes, this python solution passes all tests
The problem is that sets and dicts in Python are vulnerable to hacking due to the hashing function being predictable. You can read more here.
My own python exp: I did got FST once the same as you and I learned my lesson.
Never sort a dict. if you really need to sort, sort an array 1st then input it to dict.
btw here's how I do B without maps 289482585
i did ABCD in contest, read E, and couldnt bother writing the code after getting the idea in 5 seconds, and after that i just didnt bother doing the rest of the contest, and i wont bother to read F and G, since ABCDE are just boring, unoriginal and implementation based problems. this is probably the worst div 3 i participated in, and was actually probably the first contest i actually just quit doing in the middle of the contest due to how boring it was, even though i knew the solution to the problem. im sorry if its harsh, but i think being honest and giving genuine feedback is the most important thing, and I hope you improve in your problemsetting skills.
and also I think the statement for D is terrible, and i dont understand how that is ever allowed to be an actual statement. half of the difficulty of the problem is comprehending whatever you meant to say in that abomination of a statement
Thank you for your sincerity, I will try not to make similar mistakes in the future
It's a pity you didn't read F and G — according to other participants, these were the tasks that were interesting and useful (I realize that this is not an excuse and that all tasks should be interesting, not just a few)
Waiting for ur next round!
As a hacker I hacked 50 solutions
Somehow this gave me no points wtf
THIS IS THE MOST TERRIBLE CONTEST EVER. weak tests for E, implementation for ABCE, and almost no algorithms involved. My solution had an obvious error in it and it passed the tests for E.
upd: I hacked myself :)
The pretests passed without checking l>r?? LOL thats wild
damn, now I have to pray I dont get FST after hacking phase rofl.
P/S: btw how do you realize your mistake after contest?
I just looked at everyone else's solution and realized I didnt check l>r
I don't seem to understand the expectation people have with Div.3 and why they didn't like the problemset. It seemed that the problemset was balanced. Only thing I can add is that the language could've been better, Apart from it I don't see any other negatives. I liked writing the binary search code for problem E. and other problem seemed good as well for Div.3.
Thank you for support!)
Many participants did not like that in some tasks it is much more difficult to realize the idea than to solve the problem. I understand them and agree that this is wrong
but pls make the pretests stronger, ok?(especially for E)
Note: im RE_Prince's alt acc
Unfortunately, it is no longer possible to improve the pretests for E, but for the future we will definitely keep this in mind and try to think of more “silly bugs” in the pretests
The authors promised that tests would be decent. But pretests turned out to very weak tests... So, people blame the authors.
General problem with div.3 and ABCs is that they have several problems in the beginning that are basically a waste of time. I'm not saying this is a bad problemset design, but what happens is that ABCs and div.3 mainly teach people how to code fast without thinking that much and when they start solving ARCs and div.2 completely different skillset is required and there is no gradual transition between those contest types.
The only real solution that works for me in div.3\ABCs now is changing the order: instead of ABCDEF doing something like DEFABC or EFABCD, so that I can enjoy harder problems first and then solve easy ones if there's time left, which makes contest experience much better.
I thought the problems were alright, A-E are mostly implementation, but you can make them relatively simple with the right approaches. F was nice, I tried to figure out the xor properties on ranges for a O(1) answer, but just got a headache instead
Overall this contest wasn't good, I disliked that D was purely implementation, and E had a rather wordy statement. I heard that F and G were actually fun, so I will upsolve those and hope to feel the same way, however for the first 60% of the contest, it was quite bad. Tasks should, even if educational, have some observations. Not only was D lacking observations, it wasn't even educational, anyone could mindsolve in a very short amount of time, and it would fully depend on whether they could implement well or not. While that is still skill dependent to some extent, tasks should be educational imo, as that is the true value this site provides in the first place. E was ok, however it could have been written more clearly. While I know I've said some harsh things here, its because I'd like to see improvement from the authors in the future if they decide to continue setting rounds. If they read this, please note it is constructive criticism, not an insult, even if its worded harshly. Thanks for the contest either way.
(also after seeing someone not check l>r and still pass for E, please make pretests better (this ones more funny than depressing though lol)
I am the person who forgot to check l>r [skull]
I HATE PRETESTS!!!!!!!!!!
And it is NOT funny :)
P.S. I upvoted u
lol i found more
289611332
(using upper bound for both LOL) what are these pretests I cant :sob:
be glad you didnt do this lol
I think G is a good problem, but I don't know how to solve it until now. :(
This is what the content part of my solution for G looks like. Try to understand why it is correct (and why naive binary search isn't correct)
I usually dislike XOR problems in general, but I should say this one was very fun to solve for me. It requires only a few but nice observations while it doesn't involve any complicated formula.
Interestingly, problem F was the exact opposite style of this, and I had a very painful time and wrote a very terrible implementation for it :(
I want to go to sleep and I'm already out of energy to respond to all the comments/feedback/accusations that I really want to respond to) But I'll read and consider every comment anyway
good night :)
I tried F and G. F was nice, and I can't solve G yet. Nice problems.
does anyone know where is editorial(i am new i don't know where to get editorial)
it will appear in the announcement when we make it (we hope it will be soon)
thanks
Really enjoyed F and G :D
I wish i can be tourist after this
I personally don't understand why there's so much complaining. As someone who is actually Div. 3 level, the actual intended audience of the problem set, I don't see how it's significantly different from many other contests I have participated in. Perhaps D needed to be swapped with something else, but even that seemingly simple problem took me a while to write the solution. Meanwhile top competitors implemented this quite easily, which shows I have a lot of work to do to improve even the implementation of solution after understanding what is required.
On another note, it is very disappointing how many cheaters compete on CodeForces. It becomes evident if trying to have a go at hacking that a large amount of contestants are blatantly copy and pasting code directly from ChatGPT and/or copying solutions from others. There was such a blatant group of cheaters for Problem E that I had to post here for documentation purposes. It will be interesting to see how many out of this group of 79 cheaters with essentially identical code (ignoring their attempts at obfuscation) get caught by the plagiarizing detection system.
https://mirror.codeforces.com/contest/2036/submission/289530986 https://mirror.codeforces.com/contest/2036/submission/289549723 https://mirror.codeforces.com/contest/2036/submission/289550646 https://mirror.codeforces.com/contest/2036/submission/289551343 https://mirror.codeforces.com/contest/2036/submission/289552002 https://mirror.codeforces.com/contest/2036/submission/289552027 https://mirror.codeforces.com/contest/2036/submission/289552059 https://mirror.codeforces.com/contest/2036/submission/289552369 https://mirror.codeforces.com/contest/2036/submission/289552777 https://mirror.codeforces.com/contest/2036/submission/289553096 https://mirror.codeforces.com/contest/2036/submission/289553129 https://mirror.codeforces.com/contest/2036/submission/289554860 https://mirror.codeforces.com/contest/2036/submission/289555485 https://mirror.codeforces.com/contest/2036/submission/289556958 https://mirror.codeforces.com/contest/2036/submission/289557451 https://mirror.codeforces.com/contest/2036/submission/289557594 https://mirror.codeforces.com/contest/2036/submission/289557896 https://mirror.codeforces.com/contest/2036/submission/289558238 https://mirror.codeforces.com/contest/2036/submission/289558267 https://mirror.codeforces.com/contest/2036/submission/289558391 https://mirror.codeforces.com/contest/2036/submission/289558759 https://mirror.codeforces.com/contest/2036/submission/289559273 https://mirror.codeforces.com/contest/2036/submission/289560879 https://mirror.codeforces.com/contest/2036/submission/289561022 https://mirror.codeforces.com/contest/2036/submission/289561369 https://mirror.codeforces.com/contest/2036/submission/289562329 https://mirror.codeforces.com/contest/2036/submission/289562386 https://mirror.codeforces.com/contest/2036/submission/289563028 https://mirror.codeforces.com/contest/2036/submission/289564867 https://mirror.codeforces.com/contest/2036/submission/289565402 https://mirror.codeforces.com/contest/2036/submission/289565633 https://mirror.codeforces.com/contest/2036/submission/289565714 https://mirror.codeforces.com/contest/2036/submission/289565761 https://mirror.codeforces.com/contest/2036/submission/289565963 https://mirror.codeforces.com/contest/2036/submission/289566931 https://mirror.codeforces.com/contest/2036/submission/289567180 https://mirror.codeforces.com/contest/2036/submission/289567442 https://mirror.codeforces.com/contest/2036/submission/289568346 https://mirror.codeforces.com/contest/2036/submission/289568374 https://mirror.codeforces.com/contest/2036/submission/289568731 https://mirror.codeforces.com/contest/2036/submission/289569272 https://mirror.codeforces.com/contest/2036/submission/289569510 https://mirror.codeforces.com/contest/2036/submission/289569547 https://mirror.codeforces.com/contest/2036/submission/289569813 https://mirror.codeforces.com/contest/2036/submission/289570495 https://mirror.codeforces.com/contest/2036/submission/289571326 https://mirror.codeforces.com/contest/2036/submission/289571633 https://mirror.codeforces.com/contest/2036/submission/289571788 https://mirror.codeforces.com/contest/2036/submission/289572399 https://mirror.codeforces.com/contest/2036/submission/289572862 https://mirror.codeforces.com/contest/2036/submission/289573691 https://mirror.codeforces.com/contest/2036/submission/289573981 https://mirror.codeforces.com/contest/2036/submission/289574722 https://mirror.codeforces.com/contest/2036/submission/289574803 https://mirror.codeforces.com/contest/2036/submission/289575263 https://mirror.codeforces.com/contest/2036/submission/289576543 https://mirror.codeforces.com/contest/2036/submission/289577280 https://mirror.codeforces.com/contest/2036/submission/289578363 https://mirror.codeforces.com/contest/2036/submission/289587465 https://mirror.codeforces.com/contest/2036/submission/289587710 https://mirror.codeforces.com/contest/2036/submission/289587951 https://mirror.codeforces.com/contest/2036/submission/289588136 https://mirror.codeforces.com/contest/2036/submission/289588574 https://mirror.codeforces.com/contest/2036/submission/289588855 https://mirror.codeforces.com/contest/2036/submission/289589042 https://mirror.codeforces.com/contest/2036/submission/289589305 https://mirror.codeforces.com/contest/2036/submission/289590059 https://mirror.codeforces.com/contest/2036/submission/289590743 https://mirror.codeforces.com/contest/2036/submission/289591022 https://mirror.codeforces.com/contest/2036/submission/289591708 https://mirror.codeforces.com/contest/2036/submission/289592120 https://mirror.codeforces.com/contest/2036/submission/289592436 https://mirror.codeforces.com/contest/2036/submission/289594259 https://mirror.codeforces.com/contest/2036/submission/289594506 https://mirror.codeforces.com/contest/2036/submission/289594658 https://mirror.codeforces.com/contest/2036/submission/289595881 https://mirror.codeforces.com/contest/2036/submission/289598838 https://mirror.codeforces.com/contest/2036/submission/289601227 https://mirror.codeforces.com/contest/2036/submission/289601632
My rating was 781 before i give this contest . In this contest i solved 2 problems . But my rating did not increases. I do not know why this occur. In this blog i read that less than 1600 rating will be rated. But my rating did not increase. Can any one help me with a answer?
ratings are not updated yet, they'll be updated just after the hacking phase
Thank you so much for the answer.
for contests ruled according to the standards of educational rounds (like this one), after the round, the participants have the opportunity to "hack" other ppl solutions (which is, find some test that make the solution fail). If your solution gets hacked, you don't lose any points, but if you hack someones solution you get points.
it's been 24 hours
So why are there so many implementation problems? I didn't have time to solve F because of spending much time on E.
in problem E some people use
int i= lower_bound(a[r].begin(),a[r].end(),c)-a[r].begin();
high=min(high,i); // tourist
and some use
high=min(high,i-1) // abc864197532
and both work
why not
int i= lower_bound(a[r].begin(),a[r].end(),**c-1**)-a[r].begin();
high=min(high,i);
plz some explain
In Tourist's solution the valid range at the end is
[low, high)
, for the other it's[low, high]
. Findingc-1
may not work because of how lower bound works: it finds the suitable position forc-1
, that position can have the valuec
as well. So you'll have to take extra steps to make sure you are avoiding a bad high index withc
. Unfortunatly, I made a silly mistake somewhat similar to this. Inspecting my submissions may help understand this better.thanks i finally understand why c-1 not works
Is there a way to check the code for plagiarism in contests?
I tried problem C using Segment Tree, where each node contains the substring in the interval
[l,r]
, and a boolean value that stores the truth value of whether"1100"
is present in the substring in range[l,r]
. This can be implemented inO(|s|+q*log|s|)
. Submission Link: https://mirror.codeforces.com/contest/2036/submission/289723009. Why do I get a TLE?Building your segtree takes O(n^2) time because you are storing the whole strings in the node and combining two nodes takes O(n) time for the string concatenation. To solve this, try only storing the ranges [l,r] of the original string in each node. I think you can also implement it in a way that doesn't need to store the ranges.
Is a recalculation still ongoing? I hope I didn’t pick Unrated participation. :(
I usually wait for a full day with contest with a hacking phase. Be patient.
So it’s normal for the Unrated value (equal to my actual current rating) to be as a placeholder on my rating graph until the recalculation is finished?
Good problems, maybe too much of implementation. I was close to solving F didn't have time left.
Nice work AUTHORS.
Worst contest ever.. like wth.. u accepted the solution during contest but after the contest u declared it wrong..!!!!!!!!!!
Bruh, pretests passed does not mean it will 100% pass on the system test, it has always been like this on Codeforces.
Hi all, i participated in the contest, and solved 3 problems, but here it is only showing that I did 1? What could have happened? They were all accepted in the contest...
System testing is going on, until it is completed, some questions will be in queue so it shows up as not accepted.
Don't worry, after the testing you'll get to know which problems were accepted.
Ok thats great.
Does anyone have working solution for problem B in python. Mine got hacked.
use string key for your dictionary
Here
first time FST TLE in test 41, bingo cell crossed rofl (painful af)
Congrats on having the shittiest pretests so far.
Div.3 and Div.4 most important for the beginners. So more focused on those.
Can anyone point out the edge case I might be missing ?
My solution My approach is to see the difference corresponding value is making , change , before and after . Intially I am counting how many "1100" are possible then based on query I am checking all different scenarios .
Four for each (0 & 1).
Suppose for '0' , cases we loose a "1100" . If we place at first '1' or second '1' .
We gain if we have string like "1110" or "1101" where jth index is correspond to not un necessary 1s.
I am unable to figure what I missed .
When you process the queries, you only check the substrings where i is the first or last character. But it could also be the second or third.
For 0 , when it is placed at 1st or 2nd position we loose "1100" as it is converted to "0100" and "1000" corrspondingly .
Now for gain we gain on followin cases "1110" if 3rd position is the index where we place '0'.
Similarly we gain for following case "1101" if 4th position is the index of placing '0'.
This is what I am doing , covering all the 4 charactes .
Similary I am doing for 1 also .
Any edge case that I am missing , I want to know :).
I got it , I missed in the very last condition , I decremented the count"c--" in the following code instead of "c++".
That is so silly , here is my code (WA) — https://mirror.codeforces.com/contest/2036/submission/289526292
The AC one that I just got — https://mirror.codeforces.com/contest/2036/submission/289784904
Judging by the speed of system tests, it seems Mike himself is validating every submission by hand
because too many python sub got TLE, mine included... I'm thinking/testing ways to optimize after system test.
Is this game still keeping score
Thanks for the contest, loved it.
I just wanted to leave this here xD
i have submitted solutions and they were accepted but why am i not still rated
wait
Where is editorial
289515042
The time complexity is O(t(q+n)), right(ignoring the map queries). Then why is it taking 2999ms to run ? The time limit was 3s, so somehow managed to pass. How do I optimise it further ?
Issue is in creating temporary strings in each query that is taking O(n). That makes the time complexity O(tqn).
Hmm right. Thanks.
I wonder was it the edge case I'm missing with my solution? Submission
when rating upd?
My submission is 289489137.Why can not use find function? Why can't we use the find function? Isn't find O(n)? I see a lot of people are O(n).
Why is the rating still not updated?
My query is also this why the rating not updated
+1