Welcome to Natlan, Codeforces!
sum, Proof_by_QED and I are like a dog with two tails to welcome you to participate in Codeforces Round 988 (Div. 3) at Nov/17/2024 17:35 (Moscow time). We have cooked up $$$7$$$ problems to be solved in $$$2$$$ hours and $$$15$$$ minutes.
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. After open hacks all accepted solutions will be rejudged on successful hacks.
Note that the penalty for each wrong submission in this round is 10 minutes. Also, note the rule restricting AI use!!! If you are caught using AI in an unorthodox manner, bad things will happen to you. We will be watching you all...
IMPORTANT!!! There is at least one interactive problem in the problemset. Please familiarize yourself with the guide for interactive problems beforehand.
Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, 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 rating of 1900 or higher at any moment in time.
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 (unless you register unrated).
We would like to orz the following individuals for making the contest possible:
Vladosiya for the pogU coordination.
Our army of testuwuers: (VIP) Dominater069, amoeba4, Friedrich, awesomeguy856, AlperenT, Error_Yuan, 18o3, Intellegent, efishel, Edeeva, Lilypad, wuhudsm, Vladosiya, Filikec, kevlu8, (VIP) chromate00, Prady, mathtsai, SolCollider, larush, RobinFromTheHood, macaquedev, and dazlersan1.
MikeMirzayanov for being MikeMirzayanov.
Let's just pretend that Natlan didn't come out two months ago.
As a writer, I welcome you to Natlan with open arms
(I never played Genshin Impact before in my life)
As a tester.... Visit a local Scientology center, attend a free seminar, or take a personality test and find out how Scientology can support you on your journey. Awaken your true self and step into a world of possibility — Your path to a better life starts here!!!
As a tester, I have been wondering who Natlan was.
As a tester, I just learnt that this round is Genshin themed (I don't play Genshin)
As a tester, I recommend the round — it is excellent.
As a tester, I think this will be the best Div3 ever. Enjoy it!
tester As ! , love std::shuffle I a
fun also problems The were ! very
Is it a typo?
fixed, thanks
As a tester, I need to google Natlan.
sorry for this, but can you tell me that which cartoon that your pfp comes from? I was finding this for thoooooouuuuuussssaaaannnndddds years since I stop watching tv
KikoRiki
thank you,it's been so long :cry: hope your comment can give you contribution
As a tester, the problem are great. Have fun and good luck
Hi Aditya, how can one become a tester at Codeforces?
when someone you know becomes an author :-)
Hey quater_nion, I just messaged Cry to give me any oppurtunity for testing or problem-setting if possible.
Did you possess any prior experience, or this was your first time?
I had done testing for 3 contests earlier, you can also ask wuhudsm for the same. Also you can test for TheForces Rounds too.
As a VIP tester, I can guarantee you that the tasks are tasks.
Also,
As a tester: Genshin, Activate!
I think this is the coolest contest announcement I've seen recently.
as a genshin hater, I'm looking forward to hopefully gaining quite a lot of rate change in this contest
so do i. when this disgusting awful gayshit die?
Oh, its time crashs with my Ragional Contest of ICPC, Shanghai Station! I'm now in mihoyo's HQ, wishing every participants good luck and high rating! And wish me to win a medal :) By the way, Genshin? Launch!
i hope this div3 doesn't have as trash testcases as the last one.
ye, totally agree :)
i still remember that i hacked myself :))))))
As a genshin player, I hope this will be a good round.
The arrogation of mankind ends now.
boooooo!
genshin mentioned
I love you for the Gwnshin reference❤️
ZaDiv3
well exactly we have a natlan contest before gta VI
The picture in the post brings back memories of the song "Close to the Sun" by TheFatRat. It takes me right back to high school days, when the line between passing time and wasting it was just a little blurrier.
Feel free to give it a listen if you're in the mood: https://www.youtube.com/watch?v=oJuGlqO85YI
Thanks for the nostalgia boost!
I will eat shit if I can't become Expert after this contest.
YuanShen
It should be "at most one" interactive problem for any div3 or div4 contests. There is absolutely no value in learning these kind of problems for lower rated participants. It brings "joy" only for higher rated contestants who got bored at some point and invented a "new kind of fun". Do you think it's fun for newbies to solve these kind of problems? They have enough problems just to come up with any solutions at all :D
They don't want to spoil the number of interactive problems, but rather the fact that it will be used so people who don't know how to solve them can look at the interactive guide. Hence the "at least one" statement was used.
Even in Div 2/1 it's not super common to see 2 interactive problems in a problemset.
Quick question, why are people with rating higher than 1900 not “trusted participants of the third division”?
Those people are likely to be too good to be in Div. 3, and could have intentionally pulled themselves down to the rated range to win the contest, if they were to be included in the official standings table.
Hmm, so if you're too good for a division you're not allowed to be on the leaderboard. Interesting decision...
Well, that's why we have rating bounds for each division in the first place...
high rated people can make new id's and can win anyways.
Making alts is strictly forbidden by the rules. Also,
number of rated contests >= 5condition is there so that they won't feel like spamming alts just to win low divisions.Announcement: Welcome to Natlan! Actual contest: Welcome to Khaenri'ah! Hope it won't be the cataclysm for my rating.
Good luck in the contest!!!
But, what is a VIP tester?
Cannot turn it down as a player of Genshin Impact
It is Guaranteed that there will be no more than $$$N$$$ interactive problems.
Genshin is bad, i recommend that you need to touch grass after 3 years
i recommend everyone who play genshin to touch grass immediately
It's been almost a year since I started doing CP seriously. Now my rating is 1361, hope to become specialist in this one.
I think participating in genshin impact round feels like being "GAY"
If I didn't perform well , I'll touch the grass.
i hate newbies
not me trust
look on the bright side, more newbies can help gain more rating
score distribution?
There are no score distrbution for div 3, every question is worth the same.
eagerly waited for Such cool Div3 (as a newbie). thank you !!!
As a participant, I bet atleast one problem is about Mualani!
I have an exam tomorrow, should I study or hit expert ?
I suggest study, cause you can hit expert next time, but you can't do your exam again.
codeforces >>>>>>>>>>>>>>>> school
deserved. u cheated during the div3 so u cant reach expert :)))
HOORAY!! ANOTHER CHEATER CAUGHT :))))))
As Genshin Impact player, I am pleasantly surprised. It's too good to be true.
IF I DON'T RETURN THAT DAMNED SPECIALIST, I SHALL RETURN THE NEWBIE
hoping for pupil this round
solved till C
liked C, got stuck on D tho
Well wishes to all
go to expert and candidate master
why problem D is in russian i only know french arabic and english should i learn russian to gain rating points and solve the problem ??? i am trying my best each contest to get any point and you guys came with russian language
Click the United Kingdom flag at the top to switch it to English (and if you want French or Arabic, I believe GPT translation is allowed, though I need to double check on that)
no but first it appear that "problem statement is not available in english" i can send you the photo if you need
That's odd, are you sure you are on the right problem (Sharky Surfing, or Акулий серфинг in russian)? A picture would be useful, thanks.
send me your insta i will send it to you there
I would prefer not to give out my personal instagram account, and additionally that would make it hard for anybody else to jump in and help. You can use an image host such as imgur and imgbb, then link to it or enter it into the picture button (ctrl + p) to post it in a comment
https://imgur.com/a/WAKwDYx go to this link
Try this link or this one
If neither of them work, this might be a genuine bug that you may want to report to codeforces.
As a Chinese, I wonder who Superultra is. Is it a user name?
sum goes by superultra on discord (messaging platform)
Great E
this exactly what a div3 should be, great problems!
I thought that problem C was harder than D
anyway, ill finally get to pupil :D
Personally, C was harder to notice the observation, but was really simple to write compared to D, which was an easy observation but more difficult to write
plus, priority queue is ever so slightly niche for a div 3 D
I find that so interesting about codeforces contests. They are much more focused on the observation difficulty rather then "data structures/techniques" difficulty. Like sometimes I can't even solve Div 2B's (if it is a observation problem), when it seems that everyone here can, and on the other hand the same ppl dont know basics about heaps, graphs, segtrees, etc.
That's what I like about codeforces, the questions (for the most part) aren't "do you know this random theorem or this random data structure", but require more thinking. Sure, there will be some insanely standard questions (such as Ruler — easy version or A good string) that require little thinking outside of knowing an algorithm, but for the most part, the questions are unique and fun to solve.
Only annoying part about that is difficulty feels a bit inconsistent, I'll be able to look at a 1400 and solve it immediately then struggle on a 1200 / 1300, but that's just how it is.
Yeah codeforces its really good to train logical thinking But well, we can't deny the random theorems and data structures bc thats what ICPC contests ask for unfortunately :/
D solution Please
store the power ups as you traverse, when a power boost is required use the biggest of the them.
For each time we pick up an item, we definitely greedily select the one that provides the greatest improvement to our abilities among the items we can take but haven't yet collected.
Therefore, we can use a heap to manage the items. We enumerate each obstacle, add all the items available before that obstacle to the heap, and then take items from the heap until we can jump over the obstacle.
The code:
How to do D?
For each time we pick up an item, we definitely greedily select the one that provides the greatest improvement to our abilities among the items we can take but haven't yet collected.
Therefore, we can use a heap to manage the items. We enumerate each obstacle, add all the items available before that obstacle to the heap, and then take items from the heap until we can jump over the obstacle.
The code:
tourist wtf?? How does one complete problem E in 1 min??
Look carefully. It was his second attempt.
He use three minutes to submit for the first time, and another minute to fix his error.
I think it was a nice set of problems. I struggled in trying to figure out where I was going wrong with E ... genuinely losing my mind. I don't think there's a problem with my idea/proof, but just maybe something small in the implementation... :(
UPD: Well, since the editorial is posted, I suppose I might as well explain my thinking for E:
IMPOSSIBLE if and only if there exists no "01" substring, which is equal to querying the entire string and getting an answer of 0.
Otherwise, there is some "01", and we start querying all the prefixes [1, 2], [1, 3] ... [1, n]. Suppose the first one to give a non-zero answer is [1, i]. Let that answer be R. Then, since all prefixes before [1, i] gave 0 as an answer, the string over [0, i-1] is i-1-R 1's followed by R 0's. Also s[i] must be 1. To determine the suffix s[i+1, n], we query over the prefixes still [1, i+1], [1, i+2] ... [1, n], and, at each query, if the answer increases from the previous one, we have a 1 there, otherwise it is 0 there. In total, we take exactly 1 query for each char in s[2, n], meaning we require n-1 queries.
Does anyone know if there is something wrong here?
i think it's correct
UPD: i think your implementation should have used long long. you took input as an integer, which can overflow and made the condition (r1 > prev) false.
No, I redefined int to be long long. The issue was actually that "interQuery" function returned a god damn char instead of int by accident. :(((
(Also the biggest number to be dealt with in this problem is on the order of (10^4)^2 = 10^8, so there is actually no need for long long anyways).
anyone who solved last problem, please teach me new things
In problem D, after the problem statement changed, still wrong. Or am I high?
In the second test case, she cannot jump over the first hurdle.Actually it's the third hurdle that she cannot jump... I debugged my code for this.
UPD: Now I noticed she also cannot jump over the first hurdle, I'm actually high.how to optimize G my solution is $$$O(n * k ^ 2)$$$
where $$$k$$$ is max no. of factors
Use inclusion exclusion
my is inclusion exclusion
omg I just hear about it last month, but rarely face it and meet it today, can you explain more
You need to calculate $$$\sum_{d|u}dp[d]$$$, and you can compute the prime factors of $$$u$$$ as $$$P=[p_1, p_2, \dots, p_n]$$$. Then we have $$$\sum_{d|u}dp[d]=\sum_{S\subset P}(-1)^{|S|+1}\sum_{p\in S}dp[p]$$$.
it's silly G was ChatGPT solvable, I'd review all submission of G among rated participant if I were coordinator.
yeah i was really surprised to see a rather classic problem...
The G problem has an original problem, which is Problem J from the 2022 ICPC Guangxi Provincial Contest. You just need to modify the modulus and the range, and you can submit it directly to pass.
Link: https://pintia.cn/market/item/1541299013331705856
Somebody hack my solution for B. If
k - 2is a perfect square and its root isx, we should check if we have 2x's in the multiset right? I did not do that.Like example
[2, 1, 1, 1, 1, 1]my solution outputs2 2.Submission
That is not a valid input. It is guaranteed a solution (n,m) exists
The example you gave is invalid because there is no answer possible.
Why it works? x*x = k^2
The sequence has only 1 x. This means there are two integers y and z such that y*z = k and y<z.
Sinze x*x = k, therefore y<x and will be iterated over earlier than x and you'd already found the answer then.
Hello!
Can anyone help me with the idleness limit exceeded on this submission for question E
You have to flush after printing the answer as well IMO
Can anyone please explain G in simple terms. thank you :)
Is tourist for real? y'all sure he is not an AI?
AI isn't that accurate yet :P
Also, you sure are HUMAN? Because no real human would need to scream that in their username.
I enjoyed this contest :)
In problem D, shouldn't first test case be false instead of true? Need to jump from li-1 to ri+1 that is ri — li + 2. But the total power up that can be collected is 8 for the first hurdle and it is less than 9 that needed to be jumped from 6 15.
You start with 1 power.
Inconsistent output for 2037 B. Intercepted Inputs https://codeforces.me/contest/2037/submission/292083626 Test case 1: 2 1 4 5 3 3 my output is shown as 2 2 but when I run it else anywhere (online and my machine) its giving 1 4. Can anyone help me understand what is going wrong here?
Note that the for-loop order of an ump is an implementation-based behavior. You shouldn't seperate calculating answer from building the ump.
292066305 siliconrhino chatgpt obviously,this guy solve e,f,g in 10 minutes. get him get him :P
MikeMirzayanov check this out
The G problem has an original problem, which is Problem J from the 2022 ICPC Guangxi Provincial Contest. You just need to modify the modulus and the range, and you can submit it directly to pass.
Link: https://pintia.cn/market/item/1541299013331705856
I can't access the link. Can you send an image?
https://s2.loli.net/2024/11/18/4pbDxBJu7aRTH6g.png
Is this image link accessible?
The organizer of this ICPC contest is Hangzhou Dianzi University. Maybe yuo can find more info there.
Thanks, good to know. We would never have found it on our own D:
Oops... Assured this is a coincidence. We ran it through the yuantiji AI and no tester has reported seeing that problem before. Since its a rather obscure link I think luckily this coincidence did not affect the rankings much.
With CP having existed for so many years and millions of problems arising, this will inevitably happen.
as a mualani main, D was cool but i couldn't surf through natlan and nice contest
Has rating changes been rolled out?
wc，yuan
Where is Editorial ?
You are not allowed to see
Why is the Editorial!!! not allowed to view.
Can someone explain why i get idleness limit exceeded, this is not new, almost for every interactive problems. I tried deleting fast io, endl, \n, also in this code i make assertion. How it could be possible: my code
Because you are asking queries
2 * (n - 2) + 2times and you can at most asknqueries. I wonder how you reached the expert rating 3 times even if you can't figure out this simple thing.But im not wondering why you are still a newbie with that much problems, 2 * (n — 2) + 2??? Are you kidding?
My bad. You are asking queries
n + 1times. i.e.,1stqueries in the beginning, thenn - 2queries in the for loop, and lastly,2queries wheni == n - 2.And I am sorry for doubting you!
I am also, but i make 1 query before start, then i make n — 3 queries from i = 1 to i = n — 3, then i is n — 2 and i make 2 queries, total is n. Also, i know my solution is probably wrong but im not on it.
I figured out your problem! Yes, you are asking at most
nqueries. But you are not printing the answer forn = 2. Consider the below test case,Your code is not going into the for loop,
for (i = 1; i < N - 1; i++). BecauseN - 1 = 1forN = 2. Hence not printing the answer instead of printing1. That's why it says the Idleness limit is exceeded.Thanks, really.
Why when I try to view the Editorial, it says 'You are not allowed to view the requested page'?
Can someone please explain the binary search approach for D ?
Looks like the editorial has been taken down. Please fix cry
Hi, can someone pls help me?
my rank in standing page says 1594 as rank, but on my profile, the rank of the contest says, 1905. Can someone help me understand why two different ranks?
This part in the announcement explains it:
"Remember that only the trusted participants of the third division will be included in the official standings table."
"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 (unless you register unrated)."
For D i don't get where this logic is wrong? For every hurdle i just checked whats the minimum number of jump boosters i need to take .. for that i took a set where i stored the power ups taken after the last hurdle to the initial hurdle i am on ... And a priority queue where i stored the power ups i didn't take from the beginning to the current hurdle i need to pass. My tar for every hurdle is the amount of jump power i need — sum(the jump power i have).. when my tar becomes less than 0 i check how many power ups i could initially not take that is in the set that's why cnt--.. after taking all the power ups before a certain hurdle if my tar is greater than 0 then i just take the power ups in the priority queue untill my tar becomes less than 0 and do cnt++.. if it cant then i do flag =1 and print -1 later on. Heres my code https://codeforces.me/contest/2037/submission/292074400
You should pick power-ups from high to low, not low to high
I picked from high to low .. can you please give a test case where this code wont work
Doesn't
st.begin()return the minimum value?why is editorial not available?
masterpiece
It was humorous.
lol I love this
ABC Editorial meanwhile
https://mathmodel2.github.io/ex/cf1.html
code giving correct answer in code editor but codeforces judge giving this error :wrong answer Integer parameter [name=r] equals to 5, violates the range [6, 5] (test case 1) can you some tell why this happening ~~~~~ void solve() { int n; cin >> n;
auto ask = [&](int l, int r) { int x; cout << "? " << l << " " << r << endl; cin >> x; return x; }; string ans = ""; int value = ask(1, n); if (!value) { cout << "! " << "IMPOSSIBLE" << endl; return; } else { int l = 2; while (l <= n) { int x = ask(l, n); if (x == value) ans += '1'; else ans += '0'; value = x; if (!x) break; l++; } for (int j = l; j <= n; j++) { ans += '1'; } cout << "! " << ans << endl; return; }}
int main() { int t; cin >> t; while (t--) { solve(); } return 0; } ~~~~~
You cannot query $$$[n, n]$$$.