Happy Holidays Codeforces! 🎅
mesanu, flamestorm and I are very excited to invite you to Codeforces Round 918 (Div. 4)! It starts on Dec/28/2023 17:35 (Moscow time).
The format of the event will be identical to Div. 3 rounds:
- 5-8 tasks;
- 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.
Special thanks to the VIP testers: AlperenT, KrowSavcik!
Thanks a lot to the testers: Qualified, Kaushal_26, htetgm, MADE_IN_HEAVEN, sandry24, hbarp, Vladosiya, LucaLucaM, Gheal, tvladm, Dominater069, haochenkang, xiaowuc1, pashka, vrintle, BucketPotato!
And many thanks to Vladosiya for translating the statements!
We suggest reading all of the problems and hope you will find them interesting!
🎄 🎄 🎄 Good luck to everyone and enjoy the holidays!!! 🎄 🎄 🎄
Thank you
very handsome.
I promise to solve at least 4 problems.
P.S. Cool photo!
and you kept your promise!!
I kept my promise, I can die with a clear conscience.
This is my first out of competition and first unrated round
Legendary Grandmaster with 1435 Rating??
magic
Why not?=)
What's happened these months @_@
--- Oh it's MAGIC. Happy new year!
All the best bro
Thank you! Nice photo.
Every div 4 is good
Finally, this is my first unrated contest... I hope I will be able to solve all problems under contest time .... Merry Christmas and happy new year to all ....
questions❌problems✅Thank you mate for the correction...
why?? ps im new here
I think conducting the div4 contest is the best holidays gift for the people having rating less than 1400.
Hope to be a great contest before Christmas...
Christmas was on the 25th, it's the 28th now :)
(unless you're talking about Orthodox Christmas on the 7th of January :D)
Div4 should be arranged more frequently. Hoping for a great contest!
agreed
Are there watermarks on those Christmas hats?
Yes
thank you for this ! I hope my rating will slightly increase. I was demotivated for a long time due to failures after failures
Hopefully with this contest I can enter green :)
I hope to reach pupil after this contest, insha-allah.
i hope to retain the magic colour even after 10th jan with this round
looking forward to your success!
thanks mate!!
so handsome
It will be my first Div 4 participation ^_^
I would aim to solve >80% problems.
LMFAO!! What a noob
This contest is rated for you and not for me xD
Pupil! Pupil!
The cap on your head looks edited
looks pretty real to me
Its real, i clicked the photo
He's right, I was the camera
yeah, He is right, I was the cap
As a tester, Santa helped me test the contest
This will be my second participation at codeforces. Last was Div 3 I couldn't solve a single one.
I think I will be green this year, Insha Allah. Hopefully, this round will be great for me. I wish I could do it.
Wow! Dominater069 was a tester. That's great!
flamestorm face reveal!?!?!!
div 4 time yay! thank you for the div 4 contest!
I hope I will be pupil after this round
As an unemployed tester, I wish all participants happiness and employment.
As VIP testers, this was our testing room:
i wanna be specialist on this contest :)
Good luck to everybody ;)
Best of luck to all participants!
I wish you all a happy game, and I wish you a good score.
As a tester, I changed my color.
Hi, can I do red testing for this round? (hehehehe)
thank you
Eh, 2022-2023 is over, it was not like 2020, which is good, but I remember it as one of the most important years, I hope that next year will be successful for you all
I hope that for many every new year will only be better
My first Div.4 participation too! As a noob, hope the questions are friendly to me so that I can solve questions that less than 1300 smoothly. good time!
Hoping I could reach specialist :D
Thank you!
Can't wait to get +ve delta
Merry Christmas!
The best ending of the 2023 with div4. BTW nive picture!
As a specialist, my first unrated contest,unfortunately I can't participate
****___After Long Time___****
Just hoping for +ve delta in this one
love it！
I hope the problems are as easy as it is to spot the fake caps in the picture ;)
Happy Holidays to everyone and Merry Christmas. Coding in holidays may not be possible for many but Respect to you if you are here
Thanks for the round!!
handsome photo, the last competition in 2023
Good luck everyone
This is the day i will say goodbye to my green name
do well everyone
in queue LOL
in the statement of Problem D:
mistake: 1<=n<=2*10^5 correction: 2<=n<=2*10^5
So many people have registered for this round that I had to wait 20 minutes to see the verdict for problem A.
Thanks for the round !!!
Loved the problems on this round <3
Awesome problems, guys! Keep it up!
Nice contest
Is the person replying to the questions during the contest a bot or online human???
human
Thanx...
Fun fact: $$$G$$$ can be solved using GPT $$$4$$$ without any hints.
Really? Can you send code
Check my sibmissions. (As you can see i participated unofficial, so it must mot be cheating or smth else:) )
How do you get it accepted with 170ms? I tried your code, and got 2000+ms. Where is the difference from?
I don't know how it is possible:)
Screencast and Solutions to all problems
SecondThread orz
Thanks a lot! It was really nice to see a different view on the tasks
This video is unlisted btw.
it's over,
I will never reach cyan 🤡
Спасибо за раунд, очень понравилась задача G)
Is MO decomposition in F an overkill? :D
My solution: 239387414
might be, solved it using ordered sets, although i believe the author had a simpler solution for F of a Div 4!, btw what was your reasoning behind G?
Basically we clone each vertex $$$n$$$ times. Each clone will be a pair, where first element is number of vertex and second is bicycle we use after we visit this vertex. So, now we just use dijkstra algorithm to find min path to ($$$n$$$, $$$any$$$-$$$bicycle$$$). You just need to find some transitions when you start using different bicycle. Something like this.
You can compress the coordinates, sort the intervals and then use fenwick or segment tree to calculate the answer.
Yeah, it's just nlogn inversion count using merge sort
what is the idea of E? i felt its harder than F and evne G ( if i got the idea of G correct)
think about the prefix sums of the odd-index and even-index arrays. What can you say about the prefix sum values at the left and right endpoints of a good subarray?
Let $$$\mathrm{sum_{even}}$$$ denote the sum of values on even indices on our current subarray, and define $$$\mathrm{sum_{odd}}$$$ similarly.
$$$\mathrm{sum_{even}} = \mathrm{sum_{odd}}$$$
$$$\mathrm{sum_{even}} - \mathrm{sum_{odd}} = 0$$$
Now, multiply all values on odd indices by $$$-1$$$ in the original array. The condition now becomes
$$$\mathrm{sum_{even}} - (-1) \cdot \mathrm{sum_{odd}} = 0$$$
$$$\mathrm{sum_{even}} + \mathrm{sum_{odd}} = 0$$$
The left side is just the sum of the current subarray. Thus, we need to find a subarray with sum $$$0$$$ $$$\Leftrightarrow$$$ you need to find two equal prefix sums.
got it amazing problem and solution thanks alot !
Still clueless could you explain it to me?
What part of my comment did you not understand?
As to why we need that particular subarray where all the odd incidces sum up to zero and why do we need to use prefix sum here.
That's not what I said; odd indices shouldn't sum up to zero. Let me try to explain everything again with more details.
Let $$$\mathrm{sum_{even}}$$$ denote the sum of values on even indices on our current subarray, and define $$$\mathrm{sum_{odd}}$$$ similarly.
According to the problem statement, we need to find a subarray such that $$$\mathrm{sum_{even}} = \mathrm{sum_{odd}}$$$
Subtract $$$\mathrm{sum_{odd}}$$$ from both sides:
$$$\mathrm{sum_{even}} - \mathrm{sum_{odd}} = \mathrm{sum_{odd}} - \mathrm{sum_{odd}}$$$
$$$\mathrm{sum_{even}} - \mathrm{sum_{odd}} = 0$$$
Now, let's multiply all values on odd indices by $$$-1$$$ in the original array. Thus, $$$\mathrm{sum_{odd}}$$$ becomes $$$-\mathrm{sum_{odd}}$$$ in our new array.
This means that the required condition is now
$$$\mathrm{sum_{even}} - (-\mathrm{sum_{odd}}) = 0$$$
$$$\mathrm{sum_{even}} + \mathrm{sum_{odd}} = 0$$$
For any subarray, $$$\mathrm{sum_{even}} + \mathrm{sum_{odd}}$$$ is just the sum of that subarray. This is because every element in the subarray is either counted in $$$\mathrm{sum_{even}}$$$ or in $$$\mathrm{sum_{odd}}$$$.
Now, we just need to find a subarray with sum $$$0$$$.
Let $$$p_i = a_1 + a_2 + \dots + a_i$$$, i.e. the array $$$p = [p_1, p_2,\dots, p_n]$$$ is the prefix sum array of $$$a_1, a_2,\dots, a_n$$$. Remember that this array $$$a$$$ is the one from input, with all values on odd indices multiplied by $$$-1$$$.
Recall that $$$a_l + a_{l+1} + \dots + a_{r} = p_r - p_{l-1}$$$, i.e. the sum of a subarray of $$$a$$$ can be expressed as a difference of two prefix sums.
Since we need a subarray with sum $$$0$$$, we need two prefix sums $$$p_r$$$ and $$$p_{l-1}$$$ such that $$$p_r - p_{l-1} = 0$$$
Add $$$p_{l-1}$$$ on both sides:
$$$p_r - p_{l-1} + p_{l-1} = p_{l-1}$$$
$$$p_r = p_{l-1}$$$
This means that we just need to find two equal values in the prefix sum array. Remember to also include $$$p_0 = 0$$$ in your prefix sum array, since this might be needed when $$$l = 1\ \Leftrightarrow\ l-1 = 0$$$.
Got it.
Thank you for such detailed explanation.
a -> pref sum of odd indidces b -> pref sum of even indices for range l...r to be valid ar — al = br — bl -> (ar — br = bl — al) now you know how do it. it's similar to 2 sum problem
implemented the (ar-br) = (al-bl) through n^2 approach but got tle in 3rd TC , didnot get what is two sum problem mentioned in your post can you provide a reference for that i'll go through it O(n^2) approach
problem
I have done it once using hashset.
does solving this problem will help me understand E ?
yes the idea is same
hint : a + b = c => a = c — b think of bs. then further how can you optimes it
I'll try to do using this hint.
GL
solved it 239414558, initially I didnot get why 'two sum' in this question , but after knowing the 'subarray sum' problem got to know how two sum can be used to find a subarray of sum equals k, and I also read some post explaining about multilping -1 to alterntive ele. ThankYou for the help alpha1215
glad i could help you btw an advice never use unordered map in contest it can tle
any other alternative for map in this question, and also i tried solving F in O(n^2) considering a person meets every person whose staring and ending points are inside his starting and ending point, but the soln needs to be optimised
for first ques you can use simple map it's fine for F yo can sort the people based on their starting position now person i will meet every other person j such i < j < n if the j'th person has ending position less than i'th person after this observation it becomes a classic problem counting the inversions in array to do this there are many the method i know to do this is divide and conquer but during contest i used heap my 239336078
you can solve it with a set , make every even index element negative then loop on the array and insert the prefix sum till i in the set , and find if you have the same prefix already , if true then its a YES .
yeah thanks the implementation isn't a problem but the idea is really amazing i think i need to practice math or maybe need a brain transmission XD
can someone tell me if my approach for G is correct or not for every node i (min time to reach from 1 to i) + (min time to reach i to n) ans is min of all those nodes;
Trying same thing from hours but don't know why it's not working... I hope some explain flaw in this approach
I think the above approach assumes that the optimal route would involve a direct path from 1 to i and then i to n, and this surely is the case in the first sample test case. However, it may not always be the case as the minimum time route is a walk(not a path always) for the problem.
Consider the modified weights and bike slowness:
In this case you may observe that the optimum route goes as 1-2-3-2-4-2-5. So, the solution in this case is time(1,3) + time(3,4) + time(4,5). This can be generalized and you can make test cases where the optimum route is a combination of many simple paths, and so the assumption that time(1,n) = min over i{time(1,i) + time(i,n)} fails.
The optimum route is a combination of many simple pathsThank you so much for explaining. :)
Loved the problemset. Solved 6 problems
can somebody say why 239395416 getting TLE on 21st testcase?
What is the time complexity of my code? Isn't it O(nlogn)? 239378769
distance is $$$O(n)$$$
I thought distance is faster, is there any alternative variation to what I wanted to do?
Time complexity of the distance method is O(N), which means your final complexity is O(N^2)
can I do F in PYTHON without use SortedList?
(Co-ordinate compression + segment Tree) will work too.
Could someone please explain how to approach problems like E? TIA
We just have to found the subarray (with certain sum x) whose sum of odd and even places is same. what we can do is if we multiply -1(either of the odd or even position) now we just have to find the contiguous subarray with 0 sum that can be done by maintaining a prefix sum and a set(basic hashing)...
You can take help by this video..
Can anyone explain ideas behind F and G?
For F, you can see that 2 intervals contribute to the answer only if 1 is completely into another. Noy you can compresd all the coordinates, sort the intervals by ascending xleft coordinate and use segment or fenwick tree to calculate the answer. Tou can see my code for more details.
for some reason, I am unable to view your submissions. Could you please share your code, or tell me how to maintain number of intervals between two coordinates l and r using segment tree?
Problem F can be soved using ordered set.239369576
can you explain it
I kept on thinking the entire contest that set can't count elements greater than an element in log(n) time. Didn't know that something like ordered_set exists in cpp. Thank you so much for your elegant solution.
Gosh these problem setters just made my day. You guys propably don't know how happy you've made me today with this contest. This is hands down the best contest I've ever participated in as newbie. The problems were not too too hard for a noob like me and by no means easy either. i Was able to solve A-C and i know if i had enough time, i would have cracked D (still going to try to crack that bi*ch anyways). B was the my best problem in this contest because it was the thoughest for me and it involved me using something I'm not quite used to(2D arrays). Thanks a lot for such a nice contest.
Bro really overthinking B
I did not over think it at all. I knew the solution to the problem but what took me time was the implementstion, cause like i stated earlier, I don't really know how to work with 2D arrays, heck i didn't even know you could sort a single row(that's how noobish i am), but I'm glad i learnt alot today, and im happy :)
Tell me one thing, did you copy C? Someone for whom traversing 2D array is tough, had template in C (but not in A and B where it might be useful) which was anyways not required.
i have used this code to count the no. of inversions i changed it little bit. so i hope this is not considered as cheating and my submissions will not be skipped as many participant may used the same code
read this blog
now it doesn't matter my F got hacked blind me couldn't see there is insertion operation on vector in worst case case it's O(n^2) but the article says O(n * log(n))
Better luck next time.
` void dxt(int tc){ cin >> n >> s; set v,c; v.insert('a'); v.insert('e'); c.insert('b');c.insert('c');c.insert('d');
} `
I have no idea why this code is printing an additional character, and it costed me a good contest. Can anyone help me figuring out this?
Here, what if i + 2 >= n
Yeah got it, Thank you!
in problem F why the answer for this input is 9 ?
point(4,5) meet with (3,9) at 2nd sec ->count=1; point(2,6) meet with (4,5) at 3rd sec ->count=2; point(1,8) meet with (4,5) and (2,6) at 3rd,5th sec ->count=4; point (-2,100) meet with every other point at 7th,8th,10th,11th,12thsec ->count=4+5=9;
You must find all $$$a_i > a_j$$$ such that $$$b_i < b_j$$$.
The $$$(a_i, b_i)$$$ and $$$(a_j, b_j)$$$ pairs that meet this criteria are as follows:
So in total there are 9 greetings.
finally i'm LGM after this round
why
what
Can any one tell why my submission to G is giving WA ? Also a clarification i need, if Salvic is at city C and has bought some k bikes till now, then he can use any bike(1 to k) to travel to neighbouring cities of j right ?
My latest submission
He can only use bikes from the cities he has travelled through, i.e. only the bikes from the cities that lie on the path(or walk) from city 1 to city C.
right, then probably I understood problem right though late but still.. like the implementation above covers this fact !
Can someone please explain the test case 1 of problem G? how is 19 achieved?
1 -> 2 -> 3 -> 2 -> 4 -> 5
1 -> 2 time = 10 2 -> 3 time = 10 + 2 3 -> 2 time 10 + 2 + 1 2 -> 4 time = 10 + 2 + 1 + 5 4 -> 5 time = 10 + 2 + 1 + 5 + 1 total time = 19
I'll denote the fastest bike that we currently have by $$$b$$$.
The steps are as follows:
Elapsed time: $$$10 + 2 + 1 + 5 + 1 = 19$$$.
u look like kenzo tenma and johan liebert
Hello Everyone What is this trusted participant thing? I see the standings have a trusted participant tag. I participated after long tume. Will this round be unrated for me?
Amazing contest!!! Solved all except E lol. Ordered Multiset FTW in F.
Thanks for the great round SlavicG mesanu flamestorm and all testers.
you don't need Ordered Multiset for F.
Yes Fenwick tree is another option
my first impression on divs (^O^)/
Hoping to become a pupil. Also can anyone explain the test case for F? -10 10 -5 5 -12 12 -13 13 How is it 6?
Everyone greets each other. (-5,5) and (-10,10) meet at 5 (-5,5) and (-12,12) meet at 5 (-5,5) and (-13,13) meet at 5 (-10,10) and (-12,12) meet at 10 (-10,10) and (-13,13) meet at 10 (-12,12) and (-13,13) meet at 12
t = 0. A is at -5, B is at -10, C is at -12, D is at -13.
t = 10. A is at 5, B is at 0, C is at -2, D is at -3.
t = 15. B is at 5 and greets A. C is at 3, D is at 2. 1 greeting.
t = 17. C is at 5 and greets A. B is at 7, D is at 4. 2 greetings.
t = 18. D is at 5 and greets A. B is at 8, C is at 6. 3 greetings.
t = 20. B is at 10, C is at 8, D is at 7.
t = 22. C is at 10 and greets B. D is at 9. 4 greetings.
t = 23. D is at 10 and greets B. C is at 11. 5 greetings.
t = 24. C is at 12, D is at 11.
t = 25. D is at 12 and greets C. 6 greetings.
t = 26. D is at 13.
Thanks
my face when tourist got hacked ._.
what test was he hacked on?
I don't know. I think there is no way for us to know that right now
Здравствуйте, я недавно закончил решать Codeforces Round 918 (Div. 4). Завершил три задания из 8 успешно. Как я могу узнать место и посмотреть результаты?? Заранее спасибо
Во вкладке "результаты друзей"
What was the idea of F? Segment trees?
dp[i][j] = shortest path from i -> j where s[j] is the smallest
my bad, i thought u were talking about G
F: https://cses.fi/problemset/task/2169
sort elements in terms of a[i], find the inversions of array b after sorting (this can be handled by ordered multiset, fenwick tree, segment tree or even merge sort)
segments s1 e1 and s2 e2 giving s1 < s2 cant meet together unless e1 >= e2 ( forgot the equality too since they are all distinct)
sort the intervals by start
Geothermal King of Div4 contests. He ACs the entire problemset so quickly lol.
stared at G for over 2 hours, ggs
How to solve E ? and someone can give me a countertest for 239242264
If you get the answer in the first 2 lines so that you don't input the next lines.
Not even a clue how to solve E by prefix sum and Why to find a zero prefix sum with the addition of sum being calculated with multiplying by -1 to odd indicies :(
sum_odd(l, r) = sum_even(l, r)
<=> sum_odd(l, r) — sum_even(l, r) = 0
or
<=> sum_even(l, r) — sum_odd(l, r) = 0
we can either pick sum of odd elements or even elements, and negate it, now it turns into the classical problem of finding out whether a subarray of sum 0 exists
handsome!
why this solution gets time limit on test 3: https://codeforces.com/contest/1915/submission/239385030
isn't time complexity of it O(n*log n)
distance works in O(n)
std::distance is O(n)
How to solve E and F? can anyone explain it easily! thanks in advance.
F is here: https://cses.fi/problemset/task/2169
Refer to this for E: https://codeforces.com/blog/entry/123876?#comment-1098564
Knew about them 30 minutes before the contest and now it's everywhere
F is the worst problem I have faced till now, why did these tests allow O(n^2) solutions to squeeze in? I did not expect O(n^2) solutions to pass at all.
Can you link the O(n^2) submissions that passed?
https://codeforces.com/contest/1915/submission/239387707
where you seeing $$$O(n^2)$$$ ?
v.erase works in O(n) depending on the index of the element being erased. In worst case, it goes to O(n^2).
oh, I see. $$$5$$$ sec for $$$n = 2 * 10 ^ 5$$$ is really doubtful
They will probably face FST.
I think something like 0 1 0 2 0 3 .. will cause this code to give TLE.
std::distance works in O(n), so your code is O(n^2).
how to do then just subtraction shows error
You cannot subtract two rb tree iterators. Use an ordered multiset.
lol. tourist's solution of G got hacked.
what's lol in this??
div 4 should have more questions..like same number of questions like div2 after D considering as div 2 A
My screencast: https://youtu.be/1cdLQi_0_XQ?si=J7HiLQiXyFT0fe_u finished in 29 mins
I solved 4 problems and Iam a new comer and this contest is unrated for me. Can I know why?
I am not trying to be rude but can you please read the announcement blog again?
can someone try to hack my G solution? https://codeforces.com/contest/1915/submission/239320792
I feel like it should be able to get TLE. I followed an approach similar to bellman ford algorithm. I looped through j and used
dist[1 to i] = min(dist[1 to i], dist[i to j] + s[j]*greedy_dist[i to j])
to relax the nodes like in bellman ford
It seems like the time limit is enough for bellman ford. Try to come up with a case with maximum case and it only takes 2652 ms for your solution to pass.
can we solve f without fenwick tree
Yes, I used ordered set. 239405291
Can anyone please tell what is wrong in this method for problem G ?
dis[i][j] means minimum distance to reach ith node if the minimum slowness factor is j to reach node i.
because you are initializing that time to reach node $$$1$$$ for every slowness is $$$0$$$, which is wrong, since you can reach back to node $$$1$$$ after taking the slowness of some other node and then procees with that for further $$$optimal$$$ answer but you block it since when it reaches node $$$1$$$ its sees the time to be minimum($$$0$$$) already.
Hope that helps !
everybody talking about tourist hacked problem, but
i got hacked on E for using unordered_map instead of map. it's the first and last time i got hacked for this.
Here a useful blog about that: https://codeforces.com/blog/entry/62393
Idk my solution to G was different from most so...
Let $$$dis[i][j] =$$$ minimum distance from $$$i \rightarrow j$$$ without considering bicycle slowness
$$$dis[i][j]$$$ is calculated by running dijsktra from every node
Let $$$dis2[i][j] =$$$ minimum distance from $$$i \rightarrow j$$$ such that we ONLY use bicycle $$$i$$$
$$$dis2[i][j] = dis[i][j] * slowness[i]$$$
We can form a new graph consisting of the original $$$N$$$ nodes such that there is an edge between all pairs of nodes and the weight of the edge $$$i \rightarrow j = dis2[i][j]$$$. Run Dijkstra on this new graph from node $$$1$$$ to get the answer.
Time Complexity: $$$O(NM\log{N})$$$
Submission
maybe i can say win998244353 and ah_shit_here_we_go_again both team worked acc.
They are committed in a completely chaotic order and have different code styles.
239194376 why is it TL? can some one pls look)
It's pyyyython baby. Use python 3 instead of pypy3-64
is python3 really faster than pypy??
at times yes, but mostly it's the other way around
Use fast IO.
input = sys.stdin.readlineMy Screencast
Post contest discussion stream
I was thinking about this problem F, It's something like count the number of inversions in an array
I solved using ordered_set, binary trie and merge sort(Submission), and I know how to solve using Fenwick tree/Seg Tree.
I wanted to know if there is something easier I can do
If:
Walker 1 will greet walker 2.
This is true because if walker 1 starts in front of walker 2, it will reach walker 2's end before walker 1, and if walker 1 ends behind walker 2, it will stop before it reaches where walker 2 stopped.
So we can sort the starting points in ascending order, and then for each walker, we can count how many walkers greet them by counting how many of the walkers we've iterated through so far have an endpoint ahead of our current walker. The order statistic tree facilitates this very cleanly (and at 1/10th the speed). 239357334
It's not too slow, you can use this(Fast IO) to speed up your code
ios_base::sync_with_stdio(false);cin.tie(NULL);I submitted your code again: submission
It's running in 202ms
Thx
why O(nlogn) solution not pass problem F?
Why wouldn't it work? My solution is $$$O(n log (n))$$$
239429264 I do believe this is O(nlog(n)) if I'm not mistaken
The distance method's runtime is O(N). So your solution is O(N^2).
interesting, I've been thinking distance will always run in O(1)
my n*logn*logn solution passed for F using merge sort tree.
Hack this, please!
Solution is correct
Thank you for such fun round!
Can anyone please help me understand why 239392696 for problem E is hacked despite O(n)? Even 239438693 raised tl. TT
F can use sweep line?
can somebody explain it out why my code is getting error for question "CAN I SQbUARE"
for _ in range(int(input())): n = int(input()) x = list(map(int,input().split())) s = 0 for i in x : s+=i
if(pow(s,0.5)*pow(s,0.5)==s): print("YES") else : print("NO")It's not true that a number is a square number if $$$pow(s, 0.5) * pow(s, 0.5) = s$$$. That is only true if the result of $$$pow(s, 0.5)$$$ was an integer. Since the function returns a floating point number, that floating point number times itself will often be equal to s, so your solution will say "YES" for many non-square numbers.
can someone tell on which test case my solution of e got hacked
In short, you shouldn't use unordered_map in CodeForces (or other hackable contest), check this.
In problem E, unordered_map gives TLE, but map gives accepted verdict. Could anyone please let me know why?
Maybe 2e9lg2e5 steps usually runs faster than the limit of 1s; (# of testcases) * (nlgn) = (1e4) * (2e5 * lg2e5)..?
The sum of n over all test cases does not exceed 2⋅105
Thank you for the correction! Now I understood why it was accepted; nlgn <= 2e5lg2e5 runs faster than 1s. Good!
I still don't understand what is wrong with unordered_map which runs for O(const). Do test cases break hash table somehow? :(
https://codeforces.com/blog/entry/62393
My rating was 772 , and I haven't solve a single problem before in div4. But yesterday I solved two problems. It was supposed to increase my rating. But my rating remains the same. Why ? Can anyone explain please.Why this contest was unrated for me (:
Rating will be distributed soon. Good to see another fellow named "Nabid"
I have created account this account year before and I had given the first contest today. This was unrated for me and my contest rating is also showing as unrated. I solved four questions in this round. Can I know the rules of rating and why Iam not rated?
rated hasnt been released yet
In 1915F - Greetings,
I don't know why the First code get TLE, but the Second code passes. I'm not sure about the reason. Can you explain?
First java code : 239385944 — using Treeset, headtail method
Second java code : 239456229 — using ArrayList, BinarySearch method
Is there a significant difference in the time complexity between the two codes?
It's my first Div 4 participation
Why my rating has not increased after giving codeforces round 918 contest. I registered for it an hour before but it is showing unrated. My rating is below 1000
It will increase after the rating for contest get updated.
Have the tasks been retested yet?
I'm actually a bit confused regarding this round, as my rating is below 1400 and yet after solving 2 questions, my rating hasn't been increased. If anyone could please help me explain the situation please.
It will increase wait for few hours or a day
the point is that it's saying it is unrated
No, you are rated for this contest and most probably get a negative delta in this round...
ohk! thanks
Can anyone explain why me solution got AC? it has a time complexity of n^3 https://codeforces.com/contest/1915/submission/239328701
WOW, the size of vector d is 1e13..... I didn't know we could make a vector this big.
no idiot it's n sized vector with each element equal to 1e13
My bad :)
Why haven't our profile ratings changed ? My rating is 870. It should've boosted or decremented my rating
Will there be system testing for this round?
Is this contest Unrated?
mesanu
flamestorm
SlavicG
Where can I find the editorial? or is it unavailable
editorial
Hi, can I know when will be rated? I just participate this contest yesterday, but my profile rating didn't change til now
I don't know accurately but i think it Wil take 6-7 hours more
Thanks bro, maybe I should be more patient
thank you!
One person has been abusing me by sending messages because I hacked his/her solution in this contest. Is there a way to report that person?
For anyone who wants to know more about similar problems like G.
Here is a great blog on shortest path modelling:
https://codeforces.com/blog/entry/45897
Editorial when?
editorial
Thanks, where is it published. I cant find the link in Contest Announcement
They have not published it yet in this post NeverSpot gave me the link I can only find it through the contest author's blog
When will the rating get released?
I solved 5 out of 7 problems and they were accepted. Now it shows only 2 out of 7 were submitted ? What the hell. I just checked 3 hours ago it showed 5 out of 7 were accepted
don't worry system is retesting them again
I analysed and realised that any submission after 40 minutes was being ignored by the software system
system testing is going on, wait for sometime
Is it possible for a solution to be rejected due to TLE during system testing even if the submission was earlier accepted during the contest ?
Yes
During the contest I solved 4 questions but now it is showing that I solved only two questions somebody kindly help
System testing
I would like to ask why this submission receives a WA in the new testcases (C) https://codeforces.com/contest/1915/submission/239236542
You are typecasting to double, so it is possible that some value which is not perfect square can also match(due to precision issues). You had to typecast to long long. If it was a perfect square, then only it will match
Oh, it is quite a silly mistake lol. Thank you very much!
thank you!!
Bro rip lmao A-E was easily doable in an hour. Failed E because of using unordered_map and in C forgot to use long long once.
Hey SlavicG, I think there was something wrong for me, my rating is less than 1400 and this contest should be rated for me, but it shows that it isn't the case, it also shows that in my profile. How can I solve that?
Is there anyone else who gave this round for the first time(unrated before this) and even after 24hours your account is still showing unrated??????
I wasn't unrated before giving the contest, but my rating hasn't been updated yet.
Will i be rated if i have given contest first time and solved 4 problem in this div4 round??
Same situation
is this contest unrated ?
it was a nice contest for me.... happy coding for everyone
Why did my F TLE？ https://codeforces.com/contest/1915/submission/239528521
s.insert(it,x);insert()instd::vectoris $$$O(N)$$$, not $$$O(1)$$$Why was this unrated for me? I've never been >1400 so I'm really confused
What is the problem with the unordered_map? I used the same solution just a little change using map instead of unordered_map got AC on problem E.
Why is this happening?
TLE submission:
AC submission:
UPD: Found solution on this
ans
I participated in the contests and solve few problems while I'm newbie then why didn't I recived any points yet
I have submitted the contest on time but havent been rated for it yet, how much time does it take usually?
It's my first division 4 contest and I'm quite new to the platform..someone please guide me
I don't know why my rating is not updated. Can anybody help?
Wait for 24-48 hours after the contests
Thank you!
In Question E
Why unordered_map has given TLE in test case 16
But ,using normal ,it gets accepted,Although we are using only find function of map
because worst case of find in unordered_map is O(n)
but in map is O(log n)
so in some case, it will TLE.
FINALLY
I am a specialist NOW
Could someone please help me find the editorial? Or perhaps lead me to the solutions of E, F and G questions? I tried to implement the solution of vgtcross given in the comments under but I am not sure where I have messed up. Here is the submission. 239587509
unordered_map, you should probably read this (unless you did already).Thank you. Appreciate the help.
I solved two questions in the contest and both were correct then why did i get an overall negative 28 and a penalty of 54
.
I became Specialist...
Hello! This is my first ever comment on CF. I have a question regarding prob F. I have 2 codes: one uses a vector to store left boundary of interval & one uses a set. The one using a vector is getting accepted, but the one with the set is giving TLE. Does anyone know why is that? Here are the links of the 2 submissions.
https://codeforces.com/contest/1915/submission/240288584 https://codeforces.com/contest/1915/submission/240288739
Thank you in advance :)
https://codeforces.com/blog/entry/45902
distance() is O(n) -> complexity being O(n^2) when using set
Thank you so much. But isn't inserting in a set 0(logn) & inserting in a vector 0(n)? Doesn't that make up for the difference? ie In a set : insert log n and distance n. In a vector: insert n and upperbound logn
tf sorcerery is this
Inserting in a vector is O(n) too. So how does this submission get accepted? Isn't it O(n^2) also? If you figure it out please lmk.
I'm really not sure why this is working. Possibly because vectors use the hardware much better than sets — was reading this — https://stackoverflow.com/questions/20960936/fastest-insert-c?rq=3
either ways, the solution with vector is theoretically worse time complexity and definitely O(n^2).
You should use a self balancing binary tree such as red black tree when doing this problem (like using ordered set from gnu pbds package) instead of vector. eg my submission — https://codeforces.com/contest/1915/submission/239449554
i think possibly the time limit on this problem being 5 seconds is a lot and should be 2 seconds. But honestly im impressed this even runs till the end without timing out. freaky stuff.
Thank you soo much! Just another note: if you observe the running time of the code using vector, the time is almost reduced by half something which I cannot find an explanation for.
although i could not take part in it on time,but after i vp,i feel good?happy everyone
Плохой раунд
All my attempts were ignored due to the fact that my code for task E in logic coincides with others. I didn't post or take the code anywhere. Due to the fact that we are solving 1 problem, the logic of the code may also be the same. Please can you fix this![user:System]
I really want to author some problems for Div.4 it really improves my skills Hope to contribute in coming Div.4 Rounds mesanu , SlavicG , flamestorm , MikeMirzayanov
I have an ideas for it .