### SlavicG's blog

By SlavicG, history, 3 days ago,

Hello Codeforces!

mesanu, flamestorm and I are very excited to invite you to Codeforces Round 859 (Div. 4)! It starts on Mar/19/2023 17:55 (Moscow time).

The format of the event will be identical to Div. 3 rounds:

• ICPC rules with a penalty of 10 minutes for an incorrect submission;
• 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
• after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
• by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.

Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the fourth 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 1400 or higher in the rating.

Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.

Many thanks to all testers: jampm, Max_Calincu, KrowSavcik, TimaDegt, nyaruhodo, tibinyte, badlad, Phantom_Performer, AlperenT, Bakry, keta_tsimakuridze, Gheal, RedstoneGamer22, Dominater069!

And thanks to Alexdat2000 for translating the statements!

We suggest reading all of the problems and hope you will find them interesting!

Good Luck to everyone!

UPD: Editorial

• +202

 » 3 days ago, # |   +3 What will I gain from hacking if there are no points?
•  » » 3 days ago, # ^ | ← Rev. 3 →   0 you have chance to higher your place
•  » » » 35 hours ago, # ^ | ← Rev. 2 →   +5 I do it because I like the +100 next to my name. By the way, if you want to know a safe solution to G2, check out my solution video.
•  » » » » 35 hours ago, # ^ | ← Rev. 2 →   0 thank you i'll watch the video , because i don't know what's the solution of E and F.
•  » » » » 33 hours ago, # ^ |   0 Thanks for the video and keep up the good work
•  » » » » 30 hours ago, # ^ |   0 I don't need because my solution is safe
•  » » » » 26 hours ago, # ^ |   0 I watched your video, it was really simple explaination, but for some reason I was not able to AC G2. https://codeforces.com/contest/1807/submission/198285267What is wrong? Could anyone take a look?
•  » » » » » 26 hours ago, # ^ |   0 For WA in test 14, I guess it's the integer overflow problem
•  » » » » » » 23 hours ago, # ^ |   0 yes, you're right, i dont know how i missed that
•  » » » » » 25 hours ago, # ^ |   0 you're using int which will cause overflow in large dataset. try long long and it will get ac
•  » » » » » » 23 hours ago, # ^ |   0 yeah that solved the problem, slipped my mind somehow
•  » » » » 19 hours ago, # ^ |   0 Getting TLE in test 25
•  » » » » » 18 hours ago, # ^ |   0 don't use Arrays.sort(), in worst case it gives O(n^2). I did the same mistake TT. Make your own sort() function or try to use Collections.sort().
•  » » » » » » 17 hours ago, # ^ |   0 Damn that actually worked! I didn't know about this before. Thanks a lot!
•  » » 3 days ago, # ^ |   +3 Increase your hacking ability and it's fun (:
•  » » » 41 hour(s) ago, # ^ |   +1 it's not fun for the person hacked :(
•  » » 3 days ago, # ^ |   0 clout.Marinush
•  » » 3 days ago, # ^ |   0 Sorry, what is hacking actually?
•  » » » 25 hours ago, # ^ |   0 hacking is to give a testcase that makes a solution to a participant fail. example : someone solution get passed during contest but after the contest over you can try custom testcase which won't pass the solution and it will get w/a and you'll get some point for every successful hacking.
•  » » » » 25 hours ago, # ^ |   0 That is evil!
•  » » » » » 16 hours ago, # ^ |   0 But some guys can gain more point.and i'm often hacked by others,i can understand you
•  » » 3 days ago, # ^ |   +57 You can ruin someone's evening!
•  » » » 46 hours ago, # ^ |   0 Or mood!
•  » » » 41 hour(s) ago, # ^ |   0 U R right!
 » 3 days ago, # |   +15 As a tester, I suggest you participate! Problems are nice and educational!
 » 3 days ago, # |   +3 I love div4 contest because i get positive delta.thanks for doing div4 contest!!!
 » 3 days ago, # |   +3 I wish to see nice problems like other div4s
 » 3 days ago, # |   +3 As a participant, I want to thank you for the contest!
 » 3 days ago, # | ← Rev. 3 →   0 I'm beginner to competitive coding and love to give contest. Loves div4 contest. It helps us to check my learning.
•  » » 3 days ago, # ^ |   0 yes, the same situation
•  » » 41 hour(s) ago, # ^ |   0 Yes, the exact same thing for me too.
 » 3 days ago, # |   0 What I was waiting for the most!
 » 3 days ago, # |   +8 ooh div.4 . Means SlavicG in action :)
 » 3 days ago, # |   +9 OMG SlavicG Round!
 » 3 days ago, # |   0 As GPT-4, tomorrow will be my 5th contest participation. I hope I become green :)
•  » » 3 days ago, # ^ |   0 So i'll defeat you as bing AI :D
•  » » 43 hours ago, # ^ |   0 chatgpt solves zero problems in div 2 round 858 lol
•  » » 42 hours ago, # ^ |   0 Added you as a friend, already. Please, note, that while all the rest were laughing at you, I was always on your side! Hope you'll kill me last.
•  » » 38 hours ago, # ^ |   0 LoL chat_gpt solves 2 problems only
•  » » » 38 hours ago, # ^ |   0 Yep. GPT-4 is not strong enough it seems. It seems to generate according to patterns than real reasoning. What was annoying is that it can't even test its own code, i.e. it can't accurately tell what would the output be for a specific input.. See you when GPT-5 is out.
•  » » » » 38 hours ago, # ^ |   0 I will crash you like I crash you in this contest
•  » » » » 38 hours ago, # ^ |   0 Human is smart Than gpt because they made them
 » 3 days ago, # |   +1 Going to be my first unofficial round.
 » 3 days ago, # |   0 I'll finally solve more than ABC...
 » 3 days ago, # |   0 My first unrated round :-)
 » 3 days ago, # |   +8 flamestorm orz
 » 2 days ago, # |   0
•  » » 2 days ago, # ^ |   -12 FINALLY MY FIRST UNRATED CONTEST XD
•  » » 2 days ago, # ^ |   +21 people on their way to post this meme hoping they will get some upvotes
•  » » 41 hour(s) ago, # ^ |   +3
 » 2 days ago, # |   0 rp++
 » 2 days ago, # |   0 Div 4So, easily will do 80% of the problems.
 » 2 days ago, # |   -36 As a tester, Give me contribution!
 » 2 days ago, # |   0 Thanks for preparing div4. don't make it more than 6 problems. I hope we will solve all problems.
 » 2 days ago, # |   0 Hope to become expert in this contest.
•  » » 2 days ago, # ^ |   0 funny !
 » 2 days ago, # |   +6 Hope to see the colour change in this round !!( Δ > +6 )
•  » » 43 hours ago, # ^ |   0 >=
•  » » » 41 hour(s) ago, # ^ |   0 how binary search boundary condition TLE occurs
•  » » » 37 hours ago, # ^ |   0 Yup!! :\ ...
•  » » 38 hours ago, # ^ |   0 most probably... atb!
 » 2 days ago, # |   0 I quite agree with this view： We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.
 » 2 days ago, # |   0 Wish this round will be easy!
 » 45 hours ago, # |   0 Hope to see the colour change in this round ainsha' allah
 » 45 hours ago, # |   -8 hello. i am man; i am from to mars and run away at abi abi is brother but not brother; abis isnt cool; int monkey; monkey = monkey + wepon; cout << monkey kill nuraly SH;
•  » » 44 hours ago, # ^ | ← Rev. 2 →   0 Why are you so talented????????????????
•  » » » 44 hours ago, # ^ |   +1 I'm not talented, it's just practice, practice makes you talented
 » 42 hours ago, # |   0 what exactly hacking means?
•  » » 42 hours ago, # ^ |   0 Hacking refers to a phase where you can try out test additional cases on the submitted codes and if you find out an error in someone's submission you get extra points
 » 42 hours ago, # |   0 Div 4 is excellent practice.
 » 42 hours ago, # |   -9 Div. 4 is great for beginners
•  » » 42 hours ago, # ^ |   0 Than i have a best school in my mind for you, so, message me for more information and in that school you can also be promoted to division 5 also and higher ,so you can give codeforces contests.
 » 42 hours ago, # |   +2 Hey, are you a contest? 'Cause you're looking CUTE!
 » 42 hours ago, # |   0 Wow
 » 41 hour(s) ago, # |   -6 I would smash this contest
•  » » 41 hour(s) ago, # ^ | ← Rev. 2 →   +2 I would smash you in this contestUPD: annihilated you as I promised, so stop shitposting and go practice.
•  » » » 29 hours ago, # ^ |   0 I smashed this contest tho.Smurfing with a different account in div4 xD
 » 41 hour(s) ago, # |   +3 Delayed round?
 » 41 hour(s) ago, # |   0 Starting time 10 mins. extended...
 » 41 hour(s) ago, # |   +10 Div 4 contest, more like load testing for Codeforces Servers
•  » » 41 hour(s) ago, # ^ |   +24 2 tests failed, +20 minute penalty
•  » » » 39 hours ago, # ^ |   0 You are out of Competition anyways, my friend.
 » 41 hour(s) ago, # |   0 the contest keeps getting delayed by 10 minutes for me? just me?
•  » » 41 hour(s) ago, # ^ |   0 Not just you,.
•  » » 41 hour(s) ago, # ^ |   0 Facing the same problem here
•  » » 41 hour(s) ago, # ^ |   0 How could it be just for you ?They must not have added:if user == "Erering": "Keep delaying by 10 mins :("
 » 41 hour(s) ago, # |   0 LateForces
 » 41 hour(s) ago, # |   +3 More than 30k participants and now Codeforces is trafficked
•  » » 41 hour(s) ago, # ^ |   0 Last Div4 was 38k ....
 » 41 hour(s) ago, # |   +6 Today i'm grey again..
 » 41 hour(s) ago, # |   +15 DelayForces
 » 41 hour(s) ago, # |   +8 Feeling like participating in onsite contest where after every refresh 10 minute increase.
 » 41 hour(s) ago, # |   -14 Worst Server I Have Ever Seen!..
•  » » 41 hour(s) ago, # ^ |   0 repeating a joke kills it
 » 41 hour(s) ago, # |   0 Div.4 is good for me~
 » 40 hours ago, # | ← Rev. 3 →   +11 May be, the queue more long than my imagination :3)
•  » » 39 hours ago, # ^ |   0 it is still being in queue after the next submition.
 » 40 hours ago, # | ← Rev. 3 →   +3 Why F is ten trillion times harder than G??? Lost so much penalty, disappointing (((((
 » 40 hours ago, # |   +4 If there was going to be interactive problem.It should be mentioned in blog beforehead.
•  » » 40 hours ago, # ^ |   0 Who told you that?
•  » » 40 hours ago, # ^ |   0 Interactive problem isn't really that different from normal problem.
 » 40 hours ago, # |   +3 that long queue really sucks
•  » » 40 hours ago, # ^ |   +3 Didn't know for like 10 minutes my solution was too slow...
 » 39 hours ago, # |   +7 QueueForces:(
 » 39 hours ago, # |   +6 In queue forces :(
 » 39 hours ago, # |   0 There must be a prior information about Interactive problem in contest. i have seen several div 2 contest where author has given prior info about interactive problem.
•  » » 38 hours ago, # ^ |   0 Where in codeforces rulebook does it say that? Why does everyone hate interactive problems?
•  » » » 37 hours ago, # ^ |   0 I love them very much...Last few days (3 to 5) I solved more than 10 interactive problem and enjoyed those problem very much.. And finally today I was able to decipher the given one!! YOWWWWWWW
 » 39 hours ago, # |   +8 I like the contest, but the website is not co-operating :(
 » 39 hours ago, # |   0 I think it was supposed to be mentioned before the start of the contest about the interactive problem.
 » 39 hours ago, # |   +6 I'm praying to the universe this contest does not go unrated :)
 » 39 hours ago, # |   +29 Seems like Mike is manually judging solutions
•  » » 39 hours ago, # ^ |   0 Lmao
 » 39 hours ago, # |   +89 I apologize for the long queue at the round. Today's round was a record in terms of the constant huge flow of submissions. Unfortunately, we ran into the speed of compilation. I already have plans to move the compilation somewhere to the cloud in such extreme cases. I plan to implement this for the next div4.
•  » » 39 hours ago, # ^ |   +5 bits/stdc++.h showing it's true power
•  » » 38 hours ago, # ^ |   0 please make this round unrated it wasn't a normal Codeforces round queue was way too long T_T
•  » » » 37 hours ago, # ^ |   0 It was fair because everyone was at a disadvantage. Everyone's queue was 10 minutes long, I don't see how it affects one's ability to problem solve.
•  » » » 29 hours ago, # ^ |   0 Dude. It was fare. the queue was way too long for everyone.
•  » » 22 hours ago, # ^ |   0 Why have the ratings not changed yet
 » 39 hours ago, # |   +4 Interactive problem + long queue = nice COMBO!
 » 39 hours ago, # |   +4 The long queue has taken a toll on those of us who rely on proof by AC.
 » 39 hours ago, # |   0 solving 1 (last problem took me more time than solving all the rest of the problems combined...Due to WA and LONG WAITING QUEUE.
 » 39 hours ago, # |   0 long long .... really long queue
 » 39 hours ago, # | ← Rev. 2 →   0 Tried solving problem F using slope intercept form of line equation where y is always negative + recursion , did anyone else use this approach?
 » 38 hours ago, # |   -10 Lagforces...
 » 38 hours ago, # |   0 Are pretests on hard version of G weak? I realized my code was doing the opposite of what I wanted it to do after submitting and it still got AC... I have no idea how my solution works.
 » 38 hours ago, # | ← Rev. 2 →   +3 Bruh why did you let bitset pass G2?UPD: I got hacked lol
•  » » 38 hours ago, # ^ |   +3 div4Forces
•  » » 38 hours ago, # ^ |   0 hacked uwu
•  » » 38 hours ago, # ^ |   +1 I solved 1807G2 - Последовательное сложение (сложная версия) with C++ bitset too. At current time I have 800 ms.I see, that moonpay tries to hack it right now. Hope, that he will share test case when succeeded, it is quite interesting.
•  » » » 38 hours ago, # ^ |   0 Perfect solution:)
•  » » » » 38 hours ago, # ^ |   +4 I thought all this time that this is bitset-related problem and solution with bitset is intended solution. Was really surprised when discovered alternative greedy solution in comments under this blog...
•  » » » » » 35 hours ago, # ^ |   -12 Your nickname speaks for itself.
 » 38 hours ago, # |   +9 Very hard to track if the submitted answer was right or not !!A lot of time wasted there. Apart from that really very goooood contest.
•  » » 38 hours ago, # ^ |   0 Yes, that's the reason the submission of prb. g1 and g2 have a very huge diffrence of time submissions, in case of mine
 » 38 hours ago, # |   0 Absolutely beautiful contest 10/10 would do again!!!!
 » 38 hours ago, # |   0 Thanks! It was a great contest but the judgement time got me crying over the same problem
 » 38 hours ago, # |   0 How did I get G1 accepted and G2 WA with the same solution provided
•  » » 38 hours ago, # ^ |   0 just use long long
•  » » 38 hours ago, # ^ | ← Rev. 2 →   0 My advice is if you use c++, add#define int long long int
•  » » » 38 hours ago, # ^ |   0 that is not a good advice, you can TLE if you're not careful, I advice you to manage your limits properly instead.
•  » » » » 38 hours ago, # ^ |   0 I suppose, but that has never happened to me before.
•  » » » » » 38 hours ago, # ^ |   0 Yes, many of the setters are pretty generous with their time limit, and you should easily pass even with long long, this is not always the case though, better to be careful
•  » » » 20 hours ago, # ^ |   0 You can get MLE or TLE with that in some problems.
 » 38 hours ago, # |   0 Amazing Problems <3I loved E because It was first time I solved an interactive problem.Only if Queues werent that long I could have figured out my Idleness Limit Exceeeded 10 minutes before :(.Solved everything except F
•  » » 38 hours ago, # ^ |   0 nice smash hulk
•  » » » 29 hours ago, # ^ |   0 Haha Thanks
 » 38 hours ago, # | ← Rev. 2 →   0 Contest over,still my solution is in queue :))
 » 38 hours ago, # |   0 I am using prefix sum in G,why it is giving WA My solution
•  » » 38 hours ago, # ^ |   0 if(n == 1 && v[0] > 1){ pn; return; }you dont need n==1 here because you cannot change all 1s in the initial array.
•  » » 38 hours ago, # ^ |   0 I got it...nvm
 » 38 hours ago, # |   0 How to solve G2?
•  » » 38 hours ago, # ^ |   0 if the kth element of the sorted array is less than or equal to the sum of all 0...k-1 elements then ok else no. iterate for all from 1 to n-1 (0 based) and sorted
•  » » 38 hours ago, # ^ |   +6 It is always correct to add numbers in increasing order. So you can sort a and there holds invariant: if a[i] > a[0] + a[1] + ... + a[i - 1] then there is no way to add a[i]. And if a[i] <= a[0] + ... + a[i - 1] then you can add a[i] and you can add for a[i + 1] any number from 1 to a[0] + a[1] + ... + a[i].So just sort and check that for each i a[i] <= a[0] + ... + a[i - 1]
•  » » » 38 hours ago, # ^ |   0 " And if a[i] <= a[0] + ... + a[i — 1] then you can add a[i] "How?
•  » » » » 38 hours ago, # ^ |   +3 Let's assume that you processed indexes 0..i, and you established that you can always get any sum from 1 to S = sum(a[0..i]). Then there are two cases: a[i + 1] > S then you cannot add a[i + 1] and answer is NO. a[i + 1] <= S then you can add a[i + 1] and you can get any sum from 1 to sum(a[0..i+1]) (because you can take any sum from 1 to S in indexes from 0 to i, and you can add a[i + 1] to that).
•  » » » » » 38 hours ago, # ^ |   +3 Ok, so you are using induction.
•  » » 38 hours ago, # ^ |   +7 G1-G2 were easy when u observe that as we have the minimum unit as 1 so we can form any possible sum. So say we sort the array now following conditions should hold. $a_0$ should be 1. (as it was initially given and not gonna change). ${a_i \ge a_0 + a_1 + ... + a_{i - 1}}$. (as if prior max subsequence can't form current number than it's impossible to make $a_i$)
•  » » » 38 hours ago, # ^ |   0 " when u observe that as we have the minimum unit as 1 so we can form any possible sum "Could you please explain how is it possible to form any sum?Although minimum unit is 1, but we need to make sure that intermediate values should also be there in a.
•  » » » » 38 hours ago, # ^ |   +3 As we are given, ${a = [1]}$. In the next step, ${a = [1, 1]}$ In the next step, ${a = [1, 1, 1]}$ or ${a = [1, 1, 2]}$ In the next step, ${a = [1, 1, 1, 1]}$ or ${a = [1, 1, 1, 2]}$, or ${a = [1, 1, 2, 3]}$. So by this, you can observe that in any way we can form the next number ${1, 2, 3, 4}$ by choosing any above combinations.So via this, you can prove any next number is possible if the prefix sum is greater or equal to that number.
•  » » » » » 38 hours ago, # ^ |   0 Thank you
•  » » » » 38 hours ago, # ^ |   0 You can prove it by induction. Lets say I can make any sum from $1$ to $k$ using the current numbers from $a_0,a_1,\cdots,a_i$. Then consider $a_{i+1}\le k$. Since I can make any sum already from $1$ to $k$, I can make $a_{i+1}$ and add it to my list of numbers, and now if I add $a_{i+1}$ to those previous sums, I can now make any sum from $1$ to $k + a_{i+1}$. However, if $a_{i+1}\gt k$, then notice that I can never make $a_{i+1}$, because the current numbers cannot make any sum greater than $k$.So if at any point $a_{i}$ is greater than the sum of the numbers before it in sorted order, the answer is NO.
•  » » » » » 36 hours ago, # ^ |   0 SMART!
•  » » » 38 hours ago, # ^ |   0 :( it was actually REALLY easy in hindsight and i'm kinda sad that i didnt see that observation when solving the problem i went for the dp approach instead and ended up AC G1 (which i'm not mad of :>) and besides that, im hitting pupil for the first time!!! thanks for pointing the observation though!!!
•  » » » » 34 hours ago, # ^ |   0 how did you solve using dp? can you please share your solution?
•  » » » » » 32 hours ago, # ^ |   0 My guess on the dp solution is that he sorted the array, and then checked for each prefix if the elements in the prefix can be combined to make the element that's just outside of the prefix.
•  » » » » » » 26 hours ago, # ^ |   0 yup thats right, here's my solution, you should read only the dp part though, it can be confusing if you read the entire source code without any explanations
•  » » » 26 hours ago, # ^ |   0 I used this logic, but getting WA on test 14. Any idea? (G2) https://codeforces.com/contest/1807/submission/198285267
•  » » » » 26 hours ago, # ^ |   0 probably integer overflow. My submission also failed on test 14 it was due to the same issue.
•  » » 38 hours ago, # ^ | ← Rev. 2 →   0 Simple solution: Sort array, go over each number and make sure its not greater than the running sum, unless the number is 1.
•  » » » 26 hours ago, # ^ |   0 I used this logic, but getting WA on test 14. Any idea? (G2) https://codeforces.com/contest/1807/submission/198285267
 » 38 hours ago, # | ← Rev. 3 →   0 Getting 'WA' in Div 4 is a crime. If you get 'WA', you can't see it and can't fix it due to the long queue, which eventually leads you to unexpected penalties.
 » 38 hours ago, # |   -8 How can i get this contest answer..????
 » 38 hours ago, # |   0 beautiful problems, even if i couldnt solve all i was manage to at least have a go at it. Perfect div.4 round
 » 38 hours ago, # |   0 Wait for "In Queue" so long :(((
 » 38 hours ago, # |   0 How to solve G?
•  » » 38 hours ago, # ^ |   0 Key observation is you can reach any number less than or equal to the sum of all current numbers that you've put into the array
•  » » » 38 hours ago, # ^ |   0 Can you explain why ?
•  » » » 23 hours ago, # ^ | ← Rev. 2 →   0 thx, I should've checked the first and second element must be 1 after sorting the array.
 » 38 hours ago, # |   0 I got E and F but neither G1 or G2 somehow :'( also forgetting an extra print statement with this queue was really painful, but I guess that's just a skill issue.nice problems though
•  » » 38 hours ago, # ^ |   0 I got G1 and G2, but no E and F. Let's improve next time
 » 38 hours ago, # |   0 Solution for F? I got TLE :D
•  » » 38 hours ago, # ^ |   0 F was terrible enough!It was completely based on implementations. I myself wrote $696969$ lines of code.My submission
•  » » » 38 hours ago, # ^ |   0 I reached 200 lines of code(no templates), after covering each case of direction of ball.
•  » » » » 38 hours ago, # ^ |   0 Me too
•  » » » 27 hours ago, # ^ |   0 Still better than mine
•  » » 38 hours ago, # ^ |   0 I did it by check if (i2, j2) is along the diagonal the ball is currently moving and in the correct direction, otherwise move the ball as far as possible and flip the direction when it hits a wall.and to avoid infinite loops, if you've visited a certain position before and in the same direction, the ball will keep moving along this path and never reach (i2, j2).
•  » » » 38 hours ago, # ^ |   0 bruh I was iterating for each step, incrementing or decrementing i and j by 1, could have just taken it straight to edge/corner instead of each step, maybe that's why i got TLE. I thought it would pass the constraints.
•  » » » » 38 hours ago, # ^ | ← Rev. 2 →   0 yeah that's definitely the issue since the constraints on the grid are (2≤n,m≤25000)the implementation is really long though, since you have to know which walls the ball could hit in the direction it's moving (which vertical and horizontal walls), find how far the ball is from those walls, move the ball the minimum of those distances in the right direction, find which wall the ball will hit first or if it will hit them both, flip the direction accordingly.the condition alone to find if (i2, j2) is along the diagonal the ball is moving in is pretty long.
•  » » 38 hours ago, # ^ |   0 I've used dfs to define if I can reach the certain cell.https://codeforces.com/contest/1807/submission/198254234
 » 38 hours ago, # |   +1 PrefixsumForces
•  » » 37 hours ago, # ^ |   +1 YESNOForces
 » 38 hours ago, # |   0
 » 38 hours ago, # |   0 Why am I still unrated after solving some problems in the contest?
•  » » 38 hours ago, # ^ |   0 It will take some time for your rating to update
•  » » » 36 hours ago, # ^ |   0 but it is marked as an unrated contest on my account?
•  » » » » 34 hours ago, # ^ |   0 dont worry after some time you will get your ranking
•  » » 34 hours ago, # ^ |   0 Also i am not included in the standings list??
 » 38 hours ago, # |   0 OMG my mistake ruined every effort to solve G2. I forgot to modify the size of the arrangement... Maybe I can do better next time.
 » 38 hours ago, # |   0 Good contest! Wasn't too fond of F though, so didn't do.
 » 38 hours ago, # |   0 Waited 15min to get wa on test 1 (E problem).
•  » » 38 hours ago, # ^ | ← Rev. 2 →   0 Waited 11 min to get wa on test 1 (E problem).
•  » » 38 hours ago, # ^ |   0 In fact, testing was slow today. But I'm not sure you're right about 15 minutes. What is the id of your submission?
•  » » » 38 hours ago, # ^ |   0 sir this is my submission id 198223494
•  » » » 38 hours ago, # ^ |   0 E had the longest queue out of all my submissions for some reason. Waited so long to get WA on both sucked when I could have used the time to solve F
•  » » » 37 hours ago, # ^ |   +2 Sent: 2023-03-19 19:25:39 Judged: 2023-03-19 19:36:12 It looks like 10, but not 15 if you want to round it. It took a long time to test (sorry about it), and I'll work on it. But you exaggerated almost one and a half times.
•  » » » » 37 hours ago, # ^ |   0 Do you think CP will lose its importance due to advent of Chatgpt? Your thoughts?
•  » » 27 hours ago, # ^ |   0 And i couldn't submit E in time
 » 38 hours ago, # |   0 went for a 20 min walk after submitting 3 questions with no response
 » 38 hours ago, # |   +1 For G2 and G1, after sorting the array I knew that that one of the conditions was that every element should be at max the sum of all the elements that occured before it. Little did I know that it was the only condition required. Could someone explain me why we can always make every number from [1 — sum of all elements occured] from the given elements ?
•  » » 38 hours ago, # ^ |   +1 We can prove by induction...Obviously it is possible to reach all numbers that are less than or equal to 1 by using 1. Then consider a time when we add a number j and the sum of existing elements is i. Assuming that all numbers up to i can be reached. Then all numbers from i to i + j can be reached by adding j to a number from 1 to i.
•  » » 38 hours ago, # ^ |   0 Yep I got it, but thanks anyways
 » 38 hours ago, # |   +7 F will be an interesting (and definitely too hard for div4) problem if the constraints are n,m<=1e9 and no guarantee for their sum.
•  » » 38 hours ago, # ^ |   0 That would've been one of the best geometry problems.
•  » » 19 hours ago, # ^ |   0 Did something similar 198269402
 » 38 hours ago, # | ← Rev. 2 →   0 Why the following code for D is getting TLE? It has time complexity of O(n+q) Spoilert = int(input()) for _ in range(t): n,q = map(int,input().split()) a = list(map(int,input().split())) pre = [0] for i in a: pre.append(pre[-1]+i) for i in range(q): l,r,k = map(int,input().split()) sum = pre[l-1] sum += (pre[-1] — pre[r]) sum += k*(r-l+1) if sum%2==1: print("YES") else: print("NO") 
•  » » 38 hours ago, # ^ |   0 Use C++ or fast IO
•  » » 38 hours ago, # ^ | ← Rev. 2 →   0 I got TLE with python as well, changing print() to sys.stdout.write() fixed it with 4ms to spare lol.
•  » » 37 hours ago, # ^ |   0 For Python, try using sys.stdin.readline() to read input. Here's the same code with a little touch. 198264310 Spoilerimport sys def II(): return int(sys.stdin.readline()) def LI(): return list(map(int, sys.stdin.readline().split())) t = II() for _ in range(t): n, q = LI() a = LI() pre = [0] for i in a: pre.append(pre[-1] + i) for i in range(q): l, r, k = LI() sum = pre[l - 1] sum += (pre[-1] - pre[r]) sum += k * (r - l + 1) if sum % 2 == 1: print("YES") else: print("NO") 
 » 38 hours ago, # |   0 Even after many attempts , i am unable to remove "Idleness Limit Exceeded" to the problem E : 198257666.Your help is appreciated.
•  » » 38 hours ago, # ^ |   0 endl in c++ flushes the i/o stream by default so no need to use cout<
•  » » » 38 hours ago, # ^ |   0 i did the same but still it gives the same error.submission
•  » » » » 37 hours ago, # ^ |   0 Remove the n == 2 case. query output format is wrong and this case is not needed at all.
•  » » » » » 37 hours ago, # ^ |   0 Thanks , it passed .
•  » » » » » 37 hours ago, # ^ |   0
 » 38 hours ago, # | ← Rev. 4 →   0 Can someone please explain how to do problem D within time limits? And what optimization was needed for G2, i got G1 correct, sorted the array and checked if any element was larger than the sum of those before it, but TLE on G2 at test 19(coded everything in C)
•  » » 38 hours ago, # ^ |   0 using prefix sum. .. pre compute the prefix and suffix sum of the array. so for range[l,r] we need the sum of elements excluding this range which can be calculated using the pre computed sum. prefix[l-1]+suffix[r+1]and for the range sum can be calculated as k*(r-l+1)..
•  » » » 38 hours ago, # ^ | ← Rev. 2 →   0 I found the sum of all elements once and then just subtracted the elements in that range for each query and added k*(r-l+1), won't that be faster than calculating prefix sum for each case https://codeforces.com/contest/1807/submission/198251225
•  » » » » 38 hours ago, # ^ |   0 no, clearly not, prefix sum calculation takes o(n), and query takes o(1), the worst time complexity if you calculate for each is o(nq), while if you precalc, its o(n+q)
•  » » » » 38 hours ago, # ^ |   0 complexity will be o(n×q×(range)) wors case will be o(n×n×q). if you pre compute worst case will be o(n×q);
•  » » » 37 hours ago, # ^ |   0 using only prefix sum also it can be solved
 » 38 hours ago, # | ← Rev. 2 →   0 What is wrong with my solution of D.?? Please look into it. https://codeforces.com/contest/1807/submission/198208523
•  » » 38 hours ago, # ^ |   0 int overflow where you used --->>> (r-l+1)*k <<<----
•  » » » 37 hours ago, # ^ |   0 so what should i do in its place take individual remainders and then add
•  » » » » 37 hours ago, # ^ |   0 Use "long long"
•  » » » » » 36 hours ago, # ^ |   0 thank you
•  » » » » » » 23 hours ago, # ^ |   0 can you explain your logic in d?
•  » » » » 37 hours ago, # ^ |   0 198265855in such case multiply 1ll with it to avoid overflow
•  » » » » » 36 hours ago, # ^ |   0 thank you
 » 38 hours ago, # |   0 Why the following code for E is getting TLE? Even it's time complexity is O(n+log(n))? Spoilert = int(input()) for _ in range(t): n = int(input()) a = list(map(int,input().split())) pre = [0] for i in a: pre.append(pre[-1]+i) left = 1 right = n mid = (left+right)//2 while left <= right: query ="?" query += (" "+str(mid+1-left)) for i in range(left,mid+1): query += (" "+str(i)) print(query,flush=True) x = int(input()) y = pre[mid] - pre[left-1] if y == x: left = mid + 1 else: ans = mid right = mid - 1 mid = (left+right)//2 print("!",ans,flush=True) 
•  » » 37 hours ago, # ^ | ← Rev. 3 →   0 change it to while left < right when you reach left == right then this is your answer, otherwise, you will continue looping forever. This would happen because of r = mid, if this was r = mid — 1, it would be okay.
•  » » » 37 hours ago, # ^ |   0 No, that's not the reason why this Solution is getting TLE
•  » » 36 hours ago, # ^ |   0 you had to use cout.flush() after printing anything
 » 37 hours ago, # |   0 please can someone tell me why is my solution to problem E giving WA on testcase 1? https://codeforces.com/contest/1807/submission/198264987
•  » » 37 hours ago, # ^ | ← Rev. 3 →   0 nvm
•  » » 36 hours ago, # ^ | ← Rev. 2 →   0 you printed the "value" at the indices in the queries, we had to print "indices" in the queries change v[i] to i
•  » » » 36 hours ago, # ^ |   0 thanks bro, im so stupid xdxd
 » 37 hours ago, # |   0 I see someone using correct way to do G2 but it hacked...a[0] must = 1 for all 1 <= i < n, if a[i] > sum(a[0]~a[i-1]) then answer is NO. else is YESis it wrong?
•  » » 37 hours ago, # ^ |   +3 I think the general idea is right (it's what I did anyway). Which submission are you referring to?
 » 37 hours ago, # |   0 Problem E Flushing Problem what's the wrong with using '\n' always (Idleness limit exceeded on test 1), using endl (Accepted)
•  » » 37 hours ago, # ^ |   0 I submited with '\n' and it passed.
•  » » 32 hours ago, # ^ |   0 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout<<"! "<
 » 37 hours ago, # |   0 prefixforce
 » 37 hours ago, # |   0 The problem F was not hard to understand but hard to implement. My guess is that there is probably a great implementation that does not require bunch of if and else blocks. Can someone share a nice and compact implementation or the idea behind it?
•  » » 26 hours ago, # ^ |   0 I think my implementation is not bad though
 » 37 hours ago, # |   0 F with simulation Solutionvoid solve() { ll n, m; cin >> n >> m; ll x, y; cin >> x >> y; ll a, b; cin >> a >> b; char dx, dy; cin >> dx >> dy; ll bounce = 0; set> set; while(true){ ll prevx = x, prevy = y; ll minx = 0, miny = 0; if(dx == 'D') minx = n - x; else minx = x - 1; if(dy == 'L') miny = y - 1; else miny = m - y; ll mini = min(minx, miny); if(dx == 'D') x += mini; else x -= mini; if(dy == 'L') y -= mini; else y += mini; ll xmin, xmax, ymin, ymax; xmin = min(prevx, x); xmax = max(prevx, x); ymin = min(prevy, y); ymax = max(y, prevy); if((a <= xmax && a >= xmin) && (b <= ymax && b >= ymin)){ if(abs(x - a ) == abs(y - b)){ cout << bounce << endl; return; } } if(minx == mini) dx = (dx == 'D' ? 'U' : 'D'); if(miny == mini) dy = (dy == 'L' ? 'R' : 'L'); if(set.count({prevx ,x , prevy, y})){ cout << -1 << endl; return; } set.insert({prevx, x, prevy, y}); bounce++; } cout << bounce << endl; } 
 » 37 hours ago, # |   0 How on earth Yodasen made possible to write solution and submit within the time interval of 5 second (solution A(3 min 53s) & D(3 min 48s)) and 21 second (solution C(7 min 30s) & G1(7 min 9s)) second!Is this real??
•  » » 37 hours ago, # ^ |   0 Possible
•  » » » 37 hours ago, # ^ |   0 NOP...It's scam!
•  » » » » 37 hours ago, # ^ |   0 May be
•  » » 32 hours ago, # ^ |   +1 Also, look at his submissions. The templates are different, obvious 2/3 people on a single account.
 » 37 hours ago, # |   0 How to solve F?
•  » » 25 hours ago, # ^ |   0 Simulate the process of bouncing the ball but only care about the border cells that the ball will touch. In order to avoid infinite loop you have to use a MAP or similar data structures to record you path (this includes the direction as well).
 » 37 hours ago, # | ← Rev. 4 →   0 Need to focus on my implementation writing this so that after a month when I look back at my stupid doubt and comment I could have a laugh btw Gennady aka tourist look out I am coming after you(IK i sound stupid). Totally got stuck on E even after knowing how to solve it i wasn't able to implement it.
 » 37 hours ago, # |   0 for problem E i came up with approach and coded it out but it wasn't working can anyone please have a look at my code and tell me where I was going wrong. Submission Link:- https://codeforces.com/contest/1807/submission/198251608
 » 36 hours ago, # |   0 problem G2 should be c or something! , really? G2 is a simple greedy problem?
 » 36 hours ago, # |   0 The contest was really interesting, thank you forbthis awesome problems, but the slow judgement and delaying the contest twice were soooo annoying. Good luck and thank you again!
 » 36 hours ago, # |   0 Please, can someone explain why i'm getting "Idleness limit exceeded on test 1"? Here's my solution: 198278358
•  » » 35 hours ago, # ^ |   0 I also did the same mistake. your output for the system was "?" mid, but here you should ask for mid-l+1 because of this the system is waiting for more queries. (sorry for bad english not my native)
•  » » » 35 hours ago, # ^ |   0 That makes sense. I think i've noticed this in other part of solution, but somehow forgot about it. I've get accepted, thank you!
 » 36 hours ago, # | ← Rev. 2 →   0 Nice Questions
 » 35 hours ago, # |   0 For problem F, while contest I didn't read constraints properly, I designed more generalised solution. my solution will work for N <= 10^5 ( or even N <= 10^6 ) . [submission:https://codeforces.com/contest/1807/submission/198280396] .
•  » » 35 hours ago, # ^ | ← Rev. 2 →   0 I don't think you solution is a more generalized version. If the pigeonhole thingy from your solution actually holds, then it holds in everyone's solution that memoized too.
•  » » » 35 hours ago, # ^ |   0 most of the solutions are using dx[4] = {1,1,-1,-1}, dy[4] = {1,-1,1,-1} , and ball is moving one by one step( from cell (i,j) to (i+1,j+1) or (i-1,j-1) .. etc ). In my solution, ball jumping from one wall to another wall in O(1) time. Pigeonhole principle will hold only for boundary cells. Not for inner cells.
•  » » » » 35 hours ago, # ^ | ← Rev. 3 →   0 I haven't seen any solution moving cell by cell, they will probably TLE if they do that. Every AC solution I've seen moves in O(1) time between the walls.
•  » » » » » 30 hours ago, # ^ |   0 mine moved cell by cell and it work fine, no TLE
•  » » » » » 3 hours ago, # ^ |   +18 You should really check before making incorrect claims. btw, these were the first 8 submissions I checked.
 » 35 hours ago, # |   0 Hello, why is my code for problem D giving WA on test case 4? The logic should be correct and I cannot think of any bugs. Is there something I have failed to account for? There shouldn't be any issues with int overflow I believe.CodeThank you all very much in advance.
•  » » 35 hours ago, # ^ | ← Rev. 2 →   +8 1 3 1 1 1 1 1 3 999999999 Your code outputs "NO" instead of "YES"The error is that l, r, and k are ints, so temp += (r-l+1)*k first evaluates (r-l+1)*k as an int, which overflows.
•  » » » 35 hours ago, # ^ |   0 Thank you very much for the help, it worked. Unfortunate that I missed that in contest.
•  » » 28 hours ago, # ^ |   0 I think (r-l+1)*k can overflow
 » 33 hours ago, # |   0 how is e related to dp???
•  » » 29 hours ago, # ^ |   0 if you sort array, then:dp[i][s] = if you can make sum S using the first i elementsbase case:dp[1][1] = 1 (and check if a[1] == 1)transition is:dp[i+1][s] = dp[i][s] | dp[i][s-a[i]]Observation is that if some sum t can be created using first p elements, then it's also possible to create any sum <= t. So we can remove one dimension from the dp and store only the max s for which dp[i][s] = true.This is actually how my reasoning went during the contest.
•  » » » 26 hours ago, # ^ |   0 Can you prove this observation?
•  » » » » 23 hours ago, # ^ | ← Rev. 2 →   +5 proof by induction:Define s[i] max sum that can be created from first i elements.It's true for i == 1, because a[1] == 1 and it's possible to create sum s[1] = 1 onlyAssume it's true for i, now prove that it's also true for i+1. If a[i+1] is greater than s[i], then the answer is NO, so assume a[i+1] <= s[i]. There are 2 cases. To create sum x <= s[i] we can do so without including current element, because it's already possible to do so using previous elements. To create s[i] < x <= s[i] + a[i+1] we can use current element, and create sum x - a[i+1] from previous elements. Creating sum x > s[i] + a[i+1] is impossible, because x - a[i+1] > s[i] and (by definition) s[i] represents maximum sum that can be created using first i elements. So s[i+1] = s[i] + a[i+1]`
•  » » » » » 16 hours ago, # ^ |   0 Forgot to mention why sorting is necessary:A number can only be constructed using numbers less or equal to it, because no negative numbers are allowed
•  » » 25 hours ago, # ^ |   0 Have you tried binary search for problem E?
•  » » » 24 hours ago, # ^ |   0 yes i did, and it worked
•  » » » » 23 hours ago, # ^ |   0 Ok cool
 » 28 hours ago, # |   0 This is a very exciting competition, the quality of the topic is very high, and you can learn a lot of knowledge. Thank you for all the staff who contributed to this.
•  » » 26 hours ago, # ^ |   0 i thought A-D were pretty straight forward and easy E-G2 were exciting
 » 28 hours ago, # |   0 How does one become a tester?
 » 26 hours ago, # |   0 Can anyone explain why am I getting TLE in the given code below.https://codeforces.com/contest/1807/submission/198262166
•  » » 25 hours ago, # ^ | ← Rev. 3 →   0 I am not sure but I think because the worst thing for your code to not find a solution for 1000 cases, in this case your complexity is $10^8$, but multiplied by many constants such as functions parameter and body, and so onUpdateI made a mistake above: the code will never reach to 10000 because you have visited array
•  » » » 24 hours ago, # ^ |   0 Thank you
 » 26 hours ago, # | ← Rev. 2 →   +18 A small trick for Problem FIf you represent {DR, DL, UR, UL} as {0, 1, 2, 3} and have $d$ as direction variable, you can change directions easily To change between $U$ and $D$, it can be done by XORing $d$ by 2, for example: ($d$ ^ 2) To change between $L$ and $R$, it can be done by XORing $d$ by 1, for example: ($d$ ^ 1)
•  » » 24 hours ago, # ^ |   0 What about my approach is it correct? Could you please help me out. I am not getting an idea to solve it better.
•  » » 24 hours ago, # ^ |   0 I dont know why is this crazy. The same solution worked if I made the following changes.https://codeforces.com/contest/1807/submission/198324227
•  » » » 24 hours ago, # ^ |   0 I think you just decreased the constant value
•  » » » » 22 hours ago, # ^ |   0 Actually no I just changed string to integer by assigning ul to 0 ur to 1 dl to 2 and dr to 3.
•  » » » 24 hours ago, # ^ | ← Rev. 2 →   0 You can check this solution if you need a simplified one 198332947
•  » » » » 24 hours ago, # ^ |   0 vis = vector>(n, vector(m, vector(4))); Sir this is a crime
 » 25 hours ago, # |   0 Hi when can we see the solutions or tutorials, this was my first contest.
 » 25 hours ago, # |   0 why i'm still unrated? :((
 » 25 hours ago, # |   0 Are ratings changed yet?
•  » » 25 hours ago, # ^ |   0 It doesn't changes individually.Either it will change for all or none.
 » 25 hours ago, # |   0 Is this contest unrated?
•  » » 25 hours ago, # ^ |   0 Most probaly tonight they will update the rating. Don't worry this is rated for those who have rating under 1400.
 » 24 hours ago, # |   0 I'm new in codeforces (cp) can anyone give me some advice. how to solve , approach >= 1200 problems ???
•  » » 24 hours ago, # ^ |   0 practice
•  » » » 23 hours ago, # ^ |   0 something unique advice. i am not able to do 1200 ratings problem. soo disappointing.
•  » » » » 23 hours ago, # ^ |   0 Look out for observations. Runn differenct test case by ur own and look out for it.
 » 24 hours ago, # |   0 testing during the contest was extremely slow.. it was so bad and frustrating !!
 » 23 hours ago, # |   0 Rating should be update before today's Div 2 round start.
 » 23 hours ago, # |   0