Привет, Codeforces!
Я рад пригласить вас на мой первый раунд Codeforces Round 632 (Div. 2), который пройдет в 08.04.2020 17:35 (Московское время).
Время говорить "Спасибо"!
Хотел бы поблагодарить:
- antontrygubO_o за координацию раунда.
- 300iq, nvmdava, aryanc403, antoshkin, lkosten, pavel-afonkin за тестирование и полезные советы.
- MikeMirzayanov за отличные системы Codeforces и Polygon.
- CuriOusQuOkka за выслушивание моего бормотания пока я придумывал задачи.
- antontrygubO_o за координацию раунда (снова).
Вам будет дано 6 задач и 2 часа на их решение. Разбалловка будет объявлена скоро.
Надеюсь, вам понравится раунд! Желаю удачи!
P.S: YES, IT'S RATED.
UPD: Score distribution: 500 — 750 — 1250 — 1750 — 2000 — 2500.
UPD2: Congratulations to the winners!!
Div2:
Wow, there is no unrated in div2 round!
All:
UPD3: I will post solution in several hours.
UPD4: It was very long several hours, I'm very sorry for that :( Editorial
Auto comment: topic has been updated by PuRpLe_FoReVeR (previous revision, new revision, compare).
Hope it will be rated. But im pretty sure it won't.
Actually it is rated
Is that your real face in your profile ?
Автокомментарий: текст был обновлен пользователем PuRpLe_FoReVeR (предыдущая версия, новая версия, сравнить).
I'm sad because I won't be able to score in this round
why not?
I think Masters aren't trusted participants in Div 2.
Hope your dream of become rated in div2 contest come true one day
why aren't there more contests?? :(
Because it takes time and effort. You can solve practice problems at any time.
:v
You can solve practice problems right now and become expert in only one rated contest!
But... This requires work... I want instant gratification! (•̀o•́)ง
But there is no shortcut for instant gratification in competitive programming.if u practice more then u will need less contests to become expert.
Aaaaaaand you missed the joke :))...
OH.Cool next time i will try not to miss.
Whoosh
You can find list of competitions on other platforms here
Good Job. It is your first contest. I hope it will be good
I think I saw a few days ago that the round was of 2.5 hours. Correct me if I am wrong.
Its true and it was my mistake. Sorry for misleading. Round will be 2 hours long.
"в среда" -> "в среду" (немного режет глаз).
Это автоматически сгенерированный текст у ссылки. Я думал убрать 'в' или нет, решил все же оставить. Вот тут такая же проблема: https://mirror.codeforces.com/blog/entry/73812. Могу только убрать 'в' :)
Да, комментарий больше относился к администраторам, прошу прощения, должен быть уточнить :)
Hoping for no queueforces and strong pretests!
I pledge not to submit without checking the sample cases.
Nope! I code in submit page and I submit without compiling.
Great bro! I need that level of confidence in my life XD.
That level of confidence in real life can be real baad!
Well, this kind of joke in real life is very baad.
are you sure?
Now I'm thinking there should be such a round every few months. A 'No IDE' round, only Notepad.
Is it really RATED???????
Of course and without jokes
Nah,man.We are all messing with you (even the contest statement) :/
Coding > Singing
isitrated?
Yes of course it is rated.
no, itisrated
is it rated?
Of course rated.It's a normal division 2.
Why are so many people asking this question over and over again?
May be to get downvotes
May be they wanted to increase their absolute value of contribution.
Many contestants had trouble entering competitions at work and study times, but now everyone in home, so let's have fun. good luck everyone ^_^
rtd?
Yes, in bold at the bottom, it says:
"P.S: YES, IT'S RATED."
rtd for me?
In that case, no, as div. 2 means under 2100 rating
thx
Darn had to be one day before my birthday T-T
I hope strong pretests are there this time.. Can't we have both strong and small number of pretests?
I tried to do so :)
I hope to become a specialist in this round!
good luck!
All the best :D
*Codeforces round starts*
Codeforces servers:
Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com.
I hope to get Candidate Master in this round!
You didn't even participate...
Perhaps he started, and did not submit anything. Like me.
Thanks, you both didn't participate, otherwise my rank must be (current_rank + 2)
I just had a sleepless night, so I skipped. It was unfortunate. However, I participated today but was slow on D. I will try my best on the next one!
I know, you will very soon become Candidate Master..
Congrats on your first round. Looking forward to solve your problems
contest made life easier to pass quarantine
GO CORONA CORONA GO ....
I got 2 "fst" in the last round, then I became blue. So I hope this round will have strong pretests.
Any suggestion how should I practice to become a blue coder? Nowadays codeforces is giving hard implementation problems in c no and I find it hard to solve somehow.
Solve a lot of Div. 2 C and D problems, they are great for practice. Also, try to upsolve at least one problem after each contest. For example, I see you solved A and B in the last contest. Try to solve C, it's a good problem.
I'll try :) Thank you
May i ask how many hours you and whoever helped you with making problems in polygon spent on the contest?
Hm, I don't know... Maybe about 15-20 hours I was spent only with polygon, without creating test scenarios and problems, just for writing code and statements. It took much longer to come up with the tasks (~1 year). But it was passive work. One month I didn't do anything, and the next I create 2-3 tasks.
Thanks for reply, i hope you get better and better in problem-setting, i think 20 hour is very nice for the first time :).
Thank you for putting in the effort to create the contest! Wishing everyone luck.
Congrats, I'm excited :) I hope there is going to be more contests.
Constest starts... ... Codeforces servers down
True :(
If we register for the contest but don't enter it. Will my rating still go down?
If you don't submit anything, it doesn't count as a participation.
What about F? :)
I wanted to put it but each line has 2 photos I Didn't want to ruin that :P
Press F...
no me
We want more contest!!!!!!!!!!!
Don't be so entitled, just be happy for the contests we get and for the efforts that the creators put into it. If you want more contests you can solve old ones at any time.
Any particular reason for thanking antontrygubO_o twice for coordinating the round?
This round would not have existed without his help during the entire preparation process. This is my way of especially thanking him :)
I think if someone accepts my contest proposal after 3-4 months or more, then i would be too happy to just thank whoever accepted my contest less than 2 times, or maybe just because anton helped him with making problems(then its one for accepting the proposal and reading it perfectly, and one for helping with making problems as a coordinator).
Even if there aren't a lot of contests on CF,there are a lot of contests on different platforms.Stay inside and safe!
Codeforces contest coordinators have been pretty lazy recently. Bad pretests, not many contests to begin with. Out of all the contests they still turn out bad.
I don't think you have a good understanding about coordinators' work, they are not making contests, they check contests made by Codeforces Community and help them to prepare the contest as well, which really takes time.
Maybe it takes 2-3 day to prepare a contest, and there is tuns of contest proposals, it means tuns of tuns of problems, reading a contest should take about two hour at least, so even if 4 man are working 6 hours a day for preparing contests and checking contest proposals, then they can at most check 10 contest proposals in a day, which i dont think is enough for such a big community.
So guess what, can coordinators spend some time on they're own?, far away from working and reading random proposals? for sure they have to sleep.
I know there is few number of coordinators, and not all of them work full time for codeforces, probable the only way to increase number of good contests is to support community to make contest proposals more perfectly and prepare they're contests faster(codeforces is really doing it very well i think), or if the problem is the really long queue of contest proposals(which i think is the case), they may increase the number of coordinators and support them.
Fully related to the topic: I wanna be a coordinator later in my life, so i should plant the seeds from now, yes? =P
Thank you!
@ReD_AwHiLe hoping for the short statements and strong pretest.....?
We want more contest in this quarantine :(
I don't understand why people commented asking this and got lots of downvotes, though it's clear in the post.
Maybe people are getting bored staying home and commenting to have fun.
Is she rated?
And then you make memes xD
Div 1 coders in Div 2 contest everytime
I will just print Hello world then
I was doing this today for div2 C XD
Please arrange more contest during these corona days. :p
We try T_T
I can't able to submit solutions in JAVA, getting RUNTIME error, tried with previous accepted submissions. I don't know where to post this, this site doesn't even have a contact page.
Got it I forgot to remove package declaration at top.
Better post a link to one of those submission, then somebody can tell you why it fails.
hope this contest not to be like previous one !!
!
I will provide you video tutorials for the round after it's done!
yes please
Whats ur channel?
I think it's called Algopedia (not sure tho)
Algopedia
Here it is brothers: https://www.youtube.com/watch?v=SS5eONgsluE&feature=youtu.be
Your photo is so cute.
O kawaii koto
All the best for your first contest. Nice time to get better at CP in this quarantine. Thank you guys.
CF-Predictor, In the last 6 contests he was giving wrong results, I hope that the mistake has been fixed and gives correct results in tomorrow contest.
I am here after almost 11.5 months! 18 months if we ignore one-off contest I participated last year! Feels great to be back!
And I see that the number of participants has gone ~23-24k over past few contests. Used to be ~7-8k back in my days!
Great job guys!
Contest registrations are increasing at a higher rate than the COVID-19 cases.
I hope to become a specialist and stay that way .....
Best of luck ^_^
and i thought my graph was funny
I cannot register for the contest.
Me too.
I will be master tonight. Screen it
Wow, you really did it
I became Candidate this round)
nice done :3
Dear Codeforces web developers, there is a typo in setting->social->city section which is "City where you live ot city you are representing"
It is city where u are representing.
I highlighted the typo! it should be
or
notot
ohh i mistaken it .I thought whether u are asking about the city.
Hope we can all score and make progress in this contest!
Finally, a contest after so long...
.
I think the round isn't simple(for a newbie) My English isn't very good,please forgive me.
Why make such a pointless comment in the first place if you're so worried about your english.
Why hasn't the score distribution been published yet?
Already published . you can check that now .
Here it is!
I am enjoying by reading comments.
I did some virtual contests of division 2 ,i would try to give my 100%. No matter whether my rating increases or decreases .wish me luck and beft of luck to everyone.
Hope this raund will help to me be 1600+, good luck all
hope so.
22k participants ? can a rank under 3k will make me XXXprt
on each contests .. people ask "is it rated" for atleast 5 times.. probably gonna change my username to "alwaysRatedPleaseReadFirst".
thats moment when div1 participants not able to solve div2 D or even C
thats mean it will be fair contest for div2 participants!
thanks!!
Только у меня в глазах двоится когда читаю условие Е?
nice round. I solve F and fail at C.
Seriously man. After seeing div 2C, I was like I am no more div 1 :D
I used Segment Tree to solve C:) It's more like a Div2D, if you ask me.
Can you explain your idea on how to solve using segment trees.?
Basically I try to count the number of bad segments. Lets fix the right border $$$r$$$. Now the segment is bad if it has some zero sum subsegment. For each $$$r$$$ lets find the biggest $$$l$$$, such that sum of $$$[l, r]$$$ is zero. Now if our right border is more (or eq) than $$$r$$$ and left border is less (or eq) than $$$l$$$ it's a bad segment. Now we are doing scanline and whenever we see $$$[l, r]$$$, we update some prefix with ones. You can do this even without sgtree, but I didn't think of it on the contest.
My approach is somewhat similar, but I don't know why I'm getting TLE my code
Try using map instead of unordered_map
Thanks! It worked, but why unordered_map was giving TLE?
Welcome to the club buddy. C++ unordered_map uses a fixed modulo, so it can be blown up to $$$O(n^2)$$$. You can look at this blog, to know more.
Thanks for enlightening me :D
Interesting problems, but I think they are too hard for Div2
I have never related to something so hard.
Even though I didn't solve C but I solved D and I think it's because my mind was not clear.
relatable :/
In Problem C I dont know what the Pretest 8 was but I wasnt able to pass it till end of contest
Maybe this:
ans = 12
Why the hell would you make 4 heavy implementation problems in a row. We are so fucking tired of debugging and shit lord.
What are you talking about? These problems required a few good observations and had simple implementation. I mean first three problems needed less than 40 lines of code.
Hilarious
I Got Internet disconnection due to my provider problems and i got connected about 30 mins ago
Is there any solution for me ?
Yes. Get a new Internet provider.
LOL! For some reason, I pictured Jian Yang from Silicon Valley saying this..
In Div-2B, I was first solving the wrong question and stuck thinking that we can a[i] to a[j] and a[j] to a[i], instead of only able to add a[i] to a[j] for i<j. Can someone tell me how to solve the above version of the problem ?
Video editorials for C and F out!
C
F
I think it's great to have short explanations in video just after the end of the contest. If only I could press like multiple times!
Still didn't get C. During the contest I figured out how to find out bad subarrays using prefix sums. But then I need to remove all superarrays of this bad subarray as well. I was counting it twice in some cases. How are you handling this? I didn't get that.
Basically, I keep the rightmost starting position of such a subarray.
This helps me to count only the subarrays starting at positions which are bigger than that position.
for each index i, find how many subarray ending on that index have sum non zero, for that, we find the highest index j < i starting from which, sum is 0, then we know ans += (i — j);
How to solve C?
Right above you :))
I solved using map and prefix sum .We can calculate number of bad segments .Suppose while doing prefix sum we calculated value 'a' till position 'i' and suppose last such value 'a' has been found at position 'j' , then sum of numbers from 'j'+1 till 'i' is zero and number of bad segments it contributes is equal to (j+1-las)*(n-i+1) (provided (j+1-las) is positive) where 'las' is left position of previous such segment whose sum is zero. We include 'las' to avoid adding contribution multiple times.
submission
How comes that it contributes $$$(j+1-las)*(n-i+1)$$$
suppose array has length 20 . Let first segment whose sum is zero is [3,6] then number of bad segment is contributes = 3*15 . Now let next segment whose sum is zero is [8,12] then number of bad segment it contributes is 8*9. But [2,13] is calculated for both segments . Hence we use las = 3 for second segment.
Hey. I was trying on similar grounds during the contest and I am still trying to figure out my mistake. Can you please help me out?
Here is my submission: 75899238
I think it would be more convenient if you count the number of good subarrays. Just store last index position of the prefix running sum and the answer is equal to the i-map[prefix_sum], update map and last position at each index.
It would be very helpful if I could get any feedback on my code.
Your explanation is very clear, thanks!! I was just facing the problem of adding contribution multiples times.
Cheers, another crowded contest end. Look at the number of participants.
The contest ran smooth tho (for me, atleast). Normally, I'd face lag while submitting and loading problems but today it was different. Submissions didn't last in queue for more than 2 secs. Really nice problems too.
РАУНД — ГОВНО!
Was the n=3 case for E possible or not? I thought it wasn't (couldn't find a good proof but spent a while trying to construct cases to no avail, but I got WA and I was pretty confident about my construction for n > 4.
It's possible
Same problem, for n>4 you can just copy his solution and add stuff the border, but not sure for n = 3.
1 2 4 5 3 8 9 7 6
Seems to work for n = 3
Hey man , How your contest rating went up ?
??? This has nothing to do with the contest lol you can just message me about that
what is pretest 5 in C
I suppose this is the test like:
5 -1 0 0 0 1
or
5 0 1 2 -2 -1
or
6 1 2 4 -5 -1 -1
After I fixed this I got all pretests passed.
the same as me
my solution was failed at pretest 5 too!!!!
I am not sure, but try this:
Expected answer should be 2
For me the text of problems was hard to understand. Especialy 1333A - Маленький Артем was demotivating, since the expectation to solve a more or less nice first prob was not met.
In D i was getting TLE just because i was using endl instead of "\n".
What is pretest 7 in D?
I think it is something like 6 6 RLRLRL After accounting for this TC, i got AC. Previously, my solution too was failing on TC7
My code gives the correct answer for this test case. So, it must be something else.
I don't think so. My code is also giving WA on Test Case 7 but it is giving the correct answer on the Test Case that you mentioned. T-T
Lol i randomly started my comment like you xD.
I dont think so, i know what i missed and i got wrong answer in testcase 7, but i'm pretty sure that its not the case, i say something like 6 7 RRLRLL.
DeadlyCritic bingo
Did you know how happy i was when i saw that after years someone called me? happy to hear that.
WTF, how to solve B and C?
For C, check my video editorial, the comment is on the blog!
For B, I think:
If $$$B[0] != A[0]$$$, solution is not possible.
Else, for every position starting from 1, if $$$A[i] > B[i]$$$, you need to check if a -1 exists in A [1...i-1], if $$$A[i] < B[i]$$$, you need to check if 1 exists in A[1...i-1].
Something like this maybe:
Can you tell me how did you post your code such that we can collapse it? I always wanted to know lol
Use
Spoiler
.My first two submissions in the contest: WA Time I finally solved A: 16 minutes into the contest Codeforces DELTA: +125
This round was so cool! Thank you all who preapred this wonderful competition!
when will the editorials be out??
The verdict I got for problem E seemed wrong to me, am I missing something?
Input : 4
Output:
1 2 3 4
13 15 16 5
14 12 11 6
10 9 8 7
Verdict: wrong answer rook teleports: 0, queen teleports: 0
Doesn't queen teleports 1 time?
Link to submission: http://mirror.codeforces.com/contest/1333/submission/75904855
No it wont teleport at all, u could use the output examples in the statement instead of finding the answer for $$$n = 4$$$.
No. The queens route is:
1 2 3 4 5 6 7 8 9 10 12 11 14 13 15 16
If I'm not wrong.
oh i see now, i thought we cant go through visited cells. Thanks.
Can anyone explain how to solve C ?
Its a simple prefix sum problem.
For each index i, calculate the next index next[i] such that the interval [i..j] has a sum of 0 (this can easily be done with a map and prefix sums). If no such index exists, let next[i] = N+1.
Then, the answer is just the sum from 1 to N of (next[i]-i), since these are the number of arrays that don't have a subarray whose sum is zero.
Thanks for the explanation it really does make sense now. However, I am still failing test case 5, I have no idea why, do you mind taking a look at my submission (anything I am doing wrong)
My solution: maintain on the prefix $$$ [0, p] $$$ such maximum $$$ i $$$ that there exists $$$ j $$$ such that $$$ [i, j] $$$ is a bad subarray.
Then let's count the number of good arrays that end in $$$ p $$$. For that we notice that any array $$$ [l, p] $$$ with $$$ l \leq i $$$ is bad, and any with $$$ l > i $$$ is good.
When I see such questions like counting subarrays I usually think in two ways:
Iterate over lengths of subarrays i.e. count valid subarrays of length = 1,2,3,..,n and so on. OR
Count number of valid subarrays starting from index i = 1,2,3,4 (assuming 1-based indexing).
In this case, I used the 2nd way.
For each index i, count how many good subarrays exist.
How?
Let this be stored in subarray_becomes_zero_at[].
subarray_becomes_zero_at[i] = j implies subarray from [i+1,....,j] is a 0-sum subarray. This basically happens when prefix_sum[i] = prefix_sum[j].
For iterate from right, and store what is the minimum j >= i and k >= i such that subarray_becomes_zero_at[k] = j. Let this j be stored as can_go_till[i] = j. This means, from every starting index i you can go till jth index without having any 0 sum subarrays in it.
ans = sum( can_go_till[i] — i ) for every 1 <= i <= N.
looks like Div 1.5
God I literally misread B and for the entire contest I thought there was no restriction $$$ l < r $$$.
It was a horrible feeling of absolute stupidity when you see over 9k people having solved it and having absolutely no idea of even approaching it.
Luckily I could notice it in the end and implemented it in the remaining 5 minutes but god was it stressful.
Also it is actually now interesting how to solve that (apparently MUCH harder) problem.
same :-(
Lol same here. I made the same comment above. I was stuck in B for a long time, then moved to C and was able to solve in 15 minutes and again came to B and thankfully saw it.
same :P
How could we solve the harder version B? If i<j constraint wont be there?
I actually thought that this was B and was not able to solve it till the end when I noticed the constraint $$$i < j$$$
I believe the question becomes slightly easier if the constraint i < j is omitted.
If A does not contain -1, but B contains a number lesser than its counterpart in A, solution is impossible. Likewise, if A does not contain 1, and B contains a number greater than its counterpart in A, solution is impossible. 0 in A would not play any significant role.
I think a harder version of this problem would be if we were only allowed to use a pair of indices (i, j) only once to construct B or maybe if A consisted of other elements instead of just (-1,0,1).
It is not possible in those cases. But they are not the only cases where it is impossible. It gets very tricky to choose the order and which element to use first.
the hardest c I’ve ever met.
Yup, A and C were extremely hard for their problem class.
A was pretty simple. Just print white in the top left cell and black for all the rest.
i am crying now!!!
Yup, I figured it out too in 7 minutes. But still, I think A was extremely hard for a D2A.
Doesn't make it a bad problem though, just should've been a B and C should've been a D.
yeh, 30 mins for solve A, unsolved C and -100 rating! Good job
me either lol
me toooo..
Needed swap(E, F)
swap(F,D) would be better
Actually I think swap(C,D) and swap(E,F) would be ideal. D is more straightforward than C IMO.
swap(A,B), since A has some pitfalls if you do not see one of the simplest solutions in the first place.
I think F is even easier than C,it took me half an hour to solve C and got WA one time,an hour to solve D and got 3WAs and 1TLE,but only 7 minutes for F and passed it.
The problem C bothered me too much, This is not an enjoyable contest.
listOfAuthorsWhoSetBadContests.push_back("ReD_AwHiLe")
Why such a hard C?
You know it's a fair contest when div 1 Candidates have to go through div2 Problem C and D's editorial !
I dont have any idea how people could solve problem D, the solution for E was expectable, sadly i got stuck in case $$$n = 3$$$ for an hour i guess, after all it wasn't a bad contest if it had a little less ad-hoc problems, in fact i say solving problems in this contest needed luck more than coding power and knowledge.
It was a little modified bubble sort, you have to sort the array. Record all the swaps you can do in one pass, then make those changes, then do the same again. After we have all the operations required. Just distribute them into k groups.
I tried this algorithm, but am getting Wa at test case 7 -> submission
Here is my submission Let me explain a bit more
We just have to sort the array. We traverse the array and store the places we can do an operation. Now after we have recorded the possible operations in one pass. Now make those swaps. This way do it n times. Store all the swaps required to sort the array in n arrays. So we store in a vector<vector> operations all the operations we can do in the ith pass.
At the end, you will have all the swaps that are needed. Thus we also have the operations.size(), which denotes the number of passes required to sort. Let's call this min_operations.
Total count of all operations is max_operations needed to sort.
Now min_operations <= k <= max_operations
Let's take an example k = 6 string = RRRLLL
so min_operations = 5 (if we swap all possibilities at once) max_operations = 9 (if we swap one by one)
now if k = 6, we divide them into 6 groups instead of 5 I just used greedy for that, I filled them by one by one and k-=1 Until k was equal to the number of groups(indexes left) So we got our final answer.
Here is my submission for reference. https://mirror.codeforces.com/contest/1333/submission/75908994 Can you stop downvoting me now guys. T_T
My approach was exactly similar, but couldn't pass TC 7. I guess there was some mistake in the implementation. Thanks a lot, bruh.
@sonu628 The mistake you have made is you have made the changes while storing the swaps. So in a case like RRRLLL You first swap RR LR LL Then you can again swap here, which is wrong.
So we will first record the indexes we can store in an array. And when the inner loop is over, then we make those changes. So you should do something like this
...
Also note that inner loop goes till n-1 now everytime.
I had an off-by-1 error on D, which I noticed a couple of seconds after the contest ended. I haven't felt such frustration in a long time.
Can you discuss your approach to D?
You can notice that the head turn has the effect of turning a
RL
into aLR
i.e. moving oneL
one position to the left. It's easy to see now how many moves you have to make (i.e. the number of times you have to move anL
to the left, until allL
are to the left). Let's call this numberneeded
.The maximum amount of seconds you can have is if you do only 1 move per second, so that is
needed
seconds. Therefore, ifneeded
is less thanK
, we have no solution. Then, during each of the K seconds, whileneeded
is still bigger thanK
, greedily do as many moves as possible. Each move decreasesneeded
by 1. At some point,needed
will either become equal toK
, meaning you will successfully finish with 1 move per second, OR it will stay bigger until the end, which means there is no solution.It's no were written that if "needed" is less than K, we have no solution.
It says you have to do the process in exactly
K
seconds. If you only do 1 move per second, you will haveneeded
seconds, and that is the maximum amount of seconds you can have. Therefore, if that maximum number of seconds is less thanK
, you cannot do it in exactlyK
seconds.It's written number of moves need to be exactly "K"
not even a single question...i dont know how long will it gonna take to score 1 !
Great contest!
Great first round, PuRpLe_FoReVeR, pretty problems :)
Hey, I see you've submitted for Problem E. Would you mind sharing your idea? I came up with something in the last 30 mins but couldn't implement it correctly :(
Find a solution for $$$n = 3$$$ (brute force seems good). For $$$n > 3$$$ we can add $$$n^2-9$$$ to each number (in 3x3 solution). In the remaining cells we put the numbers from $$$1$$$ to $$$n^2 - 9$$$ so that the paths of the Rook and the Queen are identical
I can't see the idea behind how you came up with this but I can see why this may work, wow... and thanks. If you wouldn't mind, can you also explain how you came up with the idea (sorry for bothering if that's what I'm doing)?
(smh I watch William Fiset and then try to model everything into graphs to do dfs/etc on :p making it harder to implement firstly, and then forgetting the idea behind what I'm even trying)
Obviously, there is no solution for $$$n \leq 2$$$. For $$$n = 3$$$ situation is unclear, so anyway I should solve it somehow. To transform the problem into a simpler one is a typical idea in constructive problems, so it is easy for $$$n > 3$$$
Congrats on hitting Master (+302 is huge)!
Thank you. Good luck! :)
How to solve D?
Think of it as a modified bubble sort. We just have to sort the array. We traverse the array and store the places we can do an operation. Now make those swaps. Store all the swaps required to sort the array.
If number of operations is greater than k no answer.
Now divide these operations into k groups.
Here is my solution https://mirror.codeforces.com/contest/1333/submission/75908994
Just hoping it passes system tests lol
And the cheaters of today are:
julianferres and Monazo1997 !!!
Solution D of julianferres: https://mirror.codeforces.com/contest/1333/submission/75910458
Solution D of Monazo1997: https://mirror.codeforces.com/contest/1333/submission/75908368
And if you think admins are actually going to do something you can read this.
Forgot to add turkoarias. Congrats to him to !!
Solution C of Monazo1997: https://mirror.codeforces.com/contest/1333/submission/75894908
Solution C of turkoarias: https://mirror.codeforces.com/contest/1333/submission/75898533
These guys always cheat!!! Why mike doesn't do anything against them. They are cheating in every contest... other rank got affected by them
Yes, I have the same question. You can see in the blog I have been reporting this cheaters for a while and MikeMirzayanov is still ignoring it.
Anyway, thanks for your comment. It is good to know someone cares about having fair contests.
In CF haven't gotten TLE cuz cout before, until this D, and difficult gaps also seem strange.
Same thing happened to me. Since the number of integers we output is not explicitly mentioned in question, I forgot about fast output.
amazing solve F (AC):
daamn son...
Can you explain why, please?
i don't know))) just noticed))
First of all, we can consider that there is a set of numbers and when moving from k to k+1 we just add a number to that set. Second observation is that if X is a divisor of Y then we will never add Y to the set before X. That means that when we add a number to the set, all of it's divisors are already in there and so the new largest possible GCD is this number's highest divisor. We can't get a GCD larger than this one with this number and some other number because this GCD would also need to be a divisor of this number. So, we can always add the number with the lowest highest divisor.
Why do we select the largest divisor, instead of say the lowest (or any other) divisor?
Because if $$$d$$$ is a divisor of $$$x$$$, then $$$gcd(x, d) = d$$$, so largest gcd = largest divisor
Let's take a number $$$i$$$ and it's greatest factor $$$j$$$ it makes sense to add $$$j$$$ to the list before adding $$$i$$$. Now since $$$j$$$ has been added before $$$i$$$ the max gcd on adding $$$i$$$ will be $$$j$$$ only. So just calculate the greatest factors for all the numbers and sort this list and print.
Another solution for F:
we create the answer in reverse order(starting from n to 2). Initially, the set is {1,2,...n}. At any step, the imperfection of set is that number which has at least one multiple in the set. Now we know at each step the numbers for which at least one multiple is present in our set. So we greedily remove any multiple of the largest such number. code
This is so satisfiable, Thank You.
I see some magicians over there. How DreamLolita did solve the first three problems in minutes 5, 6, and 7?
it can be because of being late to contest, after contest begins for 5 minutes you cant register, then after 5 minutes he have solved these three problems and he just copy-pasted, i say he was too slow =P.
Please tell me if you think i am wrong, it happened for me couple of times but i usually go for a harder problem when i'm late.
I am wondering too. The codestyles of his A&B&C are totally different.
The sad part is, if people worked together for algo and code is just written by one guy. We would never figure it out.
That is the magic of teamwork LOL...
The difficulty gap is a bit big between B and C....in my opinion
Contests with reasonable difficulty gaps are more enjoyable.
Pretests are (somewhat) strong, that's good.
We hope to see your contests becoming better!
(Now hacking point plays its role
Hey folks,
Today I tried to hack a solution with a generator and got the "Invalid Input" verdict:
https://mirror.codeforces.com/contest/1333/hacks/628946/test
I still don't understand what exactly was wrong with my test, as I used
writeln!
operations everywhere to ensure the EOLN placement. Could it be a glitch in CF system, especially since I used Rust language which is not (yet) very popular for competitive programming?As expected, the solution I tried to hack didn't pass the systests. I want to make sure the above issue is resolved, so that I won't hesitate doing hacks with Rust in the future.
cc: MikeMirzayanov, antontrygubO_o, PuRpLe_FoReVeR, can you please take a look?
I know the exact reason why this happens (used to have the same problem in PyPy2). A less cryptic error message would be "Missing carriage return (stdin, line 1)". Normally submitting on CF, all whitespace characters are equivalent, eg. it doesn't matter if you print a space or a newline, but this is not the case for hacks. Also CF uses windows, so it requires the EOLN '\r\n' to be used to end lines in hacks. In C++ printing '\n' will on Windows automatically output '\r\n'. However in Rust writeln
meaning it does not print the '\r'. Here is a stack overflow discussion about how to make println output '\r\n', guessing there is a similar fix for writeln.
Thank you, pajenegod! I don't know how to test it now, but it seems like a very plausible explanation. I appreciate you taking the time to dive into the docs, cheers!
In this April I see every round like making April Fool to me.
i think F problem was easier than C.
Can you explain your solution
i wasn't able to solve during contest but u can refer HannaYzade solution thats pretty cool my logic was little bit complex.i was thinking about prime number and all.
I can't believe that this soultion will get TLE for problem C of case 86。 https://mirror.codeforces.com/contest/1333/submission/75862488
Everyone using unordered_map are getting TLE, not sure why..
Worst case complexity of unordered_map is linear because it's hashmap.
Use a custom_hash with that.
Refer to this link
Thanks!
Try using ordered map. Amazingly it passed the test cases.
Probably it's anti-hashmap test.
Everyone can downvote me, but I think it's not honest, when your algorithm is right but it hasn't passed by same way. "Thanks" to author, do it more.
isn't the complexity of count method linear?
But it may take up to $$$O(n)$$$ time to access element in unordered_map in an anti-hash test.
Yes. Unfortunately got the same verdict.
https://mirror.codeforces.com/contest/1333/submission/75908627 My solution for C problem stuck at test case 9, can somebody help me in debugging(* please ignore the template)
Same way brother my one also stuck on test case 9
I don't know what happen to me...I started doing all contests on CF again from 1st April..even not a single time I am able to solve problem C in div2, which was not that too difficult 3 months before.. I guess there are 2 possibilities for this 1) I have to practice hard again to come on the track 2) they are making hard problem sets for contest
This month less experienced setters are coming in front who are giving problems of very odd taste and of high on implementation part..
Nice contest. Special thanks for making strong pretests.
I don't agree with second sentence. Pretests were very week on B and that is fine, but it's not fine that system tests are also very week. I've just hacked a bunch of people ( link ) with few TLE "edge cases" and still a lot of people could be hacked (just sort AC submissions decreasing by time and you will find a lot of O(N^2) solutions). I hope that the authors will make stronger tests next time.
MikeMirzayanov because of connection problems, my same code for D got submitted twice. Once through the problems page and the other through the submit page, and I got a 50 points penalty for resubmission. Shouldn't the system have checked my previous submission and not allow me to resubmit the same solution code again? I believe this might be a bug in the system. Please check.
Here are the 2 submissions: 75895126 and 75895561. They also don't have any difference even on comparing them using the compare button.
Hi. Probably, you used a micro-website, it could be a reason. I have plans to implement it in the correct way there soon. We do some work on micro-websites. For example, today m1 worked via https + announcements have been implemented. Since you took part as an unofficial participant, I don't think I really need manually change submission verdicts.
Thanks for replying.
I don't need a manual change in my verdict but I brought this up since I think this might affect other people as well someday. I didn't actually use a micro website for this. My first submission was through the problem page by uploading a file. Since it was taking too much time to get submitted, so I opened the submit page and copied the code from my editor and submitted it, and it turned out that the earlier one had been submitted as well.
Hopefully, codeforces team will work to improve this, so that it does not happen frequently.
I only got AC on the problem D after i wrote fast output. Before that, i always got TL10
Yet another screencast. The channel have focus in brazilian community so many videos will be in portuguese, but from time to time I maybe do something in english, or with no audio like this screencast
Why on earth did you guys make an anti-unordered_map TC(86)... Think its quite unsuitable for a contest like this which only has limited pretests. What this kind of situation means is that we can't use hash_based STL in contests w/o dirty tricks avoiding anti-hash testcases, which is not quite a necessary skill for Div.2 Contests like this one.
I hacked a person with that test case and all successful hacks are usually put into system tests. So blame me if you want, not the authors.
Wow, that's unexpectful... Respect on your hacks.
If you have not read the blog post by neal on how to protect against unordered map hacks, I’d highly recommend. You can find it with a quick google search.
There is no such test in original testset. I think such things are not what we want to learn from CP. But this trick exists and we must know it.
At the time of the contest i had 2 problems solved. Now I see that broblem B became unsolved. How?
failed on system checking.
There are pretests and system tests. While contest only the pretests are executed.
what is the difference and what for system tests exist?
While contest the queue of problems should be resolved fast, so participants get quick response after submitting.
On the other hand, CF wants to do a lot of tests to be sure that everyting is tested fine.
So, as a compromise, only a part of the tests are executed while contest. That are the pretests. The disadvantage of this is, that sometimes happens what happened to you. You think you submitted a correct solution, but it was errnous.
On some platforms you get "full feedback", which means all tests are executed while contest.
I also learned it the hard way.
Is there a collision linked to the numbers on the pill ? I have never experienced this before (but I haven't used unordered_map a lot either).
Uhh... that's just the meme template. Nothing special about that. But you can refer to other comments in this blog as to why you shouldn't use unordered_map in a codeforces contest.
So this strange thing happened
I got the solution right down to the most basic detail of it
But apparently I got a TLE because I used an unordered_map and not a map
Can someone please explain this unanticipated issue
And then how to judge where to use map and where to use unordered_map
https://mirror.codeforces.com/contest/1333/submission/75869383
My solution for reference
Check this out!
see here
Well unordered_map uses hashing to provide quick access to memory, but hashes aren't stable and there might be collisions in some points (especially when anti-hash testing) and that makes unordered_map to 'rebuild' itself and do a rehashing (depends on implementation). So if there is a lot of data to store it is more profitably to use normal map, or!!! use custom hash function for unordered_map watch here
It is the usual problem with unordered_maps/gp_hashtable, but not the only one
Constructive A is a really good tradition :)
post the tutorial fast :(
great round with interesting problems! Hope I can become orange this time.
A simple solution for F: Just take maximum divisor that not equal to a number for every number in range 1..n. Then sort It and that will be the answer. You can check my submission. https://mirror.codeforces.com/contest/1333/submission/75915783
pls help me i dont know how to prove that by mistaken i have used ideone and someone copied my code what are next steps to get my rating back.
what is ideone
ok i googled it
Thanks a lot PuRpLe_FoReVeR for preparing this round.. Finally became a Candidate Master....
https://mirror.codeforces.com/profile/AnsuFati Correct me if i'm wrong,but isn't Div2<=1900?
<2100
My submission on D took time limit exceeded because i used endl instead of \n. I know it is my fault but can you do anything about it? This is taking AC and this is taking TLE
#define endl "\n"
This will give an error, use
define endl "\n"
Can team codeforces upload explanation videos for harder problems like-div2 D,E,F..It would be helpfull for budding programmer like me.. MikeMirzayanov
There's tmwilliamlin168's channel on youtube with explanations of some rounds
lost the net connection and ... -161 points in rank rating . :?
problem C, TL86, fix:
unordered_map
->map
problem D, TL10, fix: I deleted
ans
vector and printed answer straight to stdoutMy expert rank:
Actually, good problems, but these things just killed me
I got WA test 76 in D any idea please my submission
I think you forgot to check if k is below the lower bound of the possible answers
yeah this is the problem ,thanks
C was a tricky problem. One that makes you think it's easy, but has a bunch of traps. After reading some good solutions, here's some details on how to go about solving it:
Observations / Solution
1) Prefix sums are essential here. As you traverse the array, if you see a prefix sum you've seen before, that means the elements after the last index for that prefix sum to the current index of the same prefix sum add up to 0. For eg., if array is [3 -1 2 -1], the prefix sums would be [3 2 4 3]. Observe how 3 is seen twice since subarray [-1 2 -1] adds up to 0. So positions 2 through 4 constitute a net sum of 0.
2) You could calculate all the bad subarrays and remove them from the overall count of subarrays. But that seems to have many complications with overlaps and is not recommended (at least that's how I started solving this problem, and couldn't figure out how to do it).
3) The right way is to calculate all the good subarrays, piece by piece by systematically excluding the bad subarrays. Normally we compute all possible contiguous subarrays using the formula n*(n+1)/2. However, rather than rely on a one-size-fit-all formula, we should rely on first principles. A cleaner way is to just add up piece by piece as you move along. So for eg. [3 5 9] has 6 subarrays ([3], [5], [9], [3 5], [5 9], [3 5 9]), which can be computed as shown below :
Subarrays([3 5 9]) = (subarrays([3]) that include the first element "3") + (subarrays([3 5]) that include the second element [5]) + (subarrays([3 5 9]) that include the third element "9")
The length of each is simply the length of the subarray up to that point. So for subarrays([3 5 9]) that includes "9", it is 3 ([9], [5 9], [3 5 9]), similarly for "5" that could would be 2 ([5], [3 5]) and for the first element "3", it would be 1 (just [3]).
So Subarrays([3 5 9]) = 1 + 2 + 3 = 6
Basically this is analogous to having a string "abcd" and finding all the substrings (total of 10) :
(If someone has an easier or more intuitive way to calculate/understand the above, please do share)
4) Once you encounter a bad subarray, then don't count it or anything to it's left. This is needed to avoid over-counting and to meet the problem statement requirement. Maintain a last bad position and keep updating it every time you encounter another "bad subarray". Bad_position is defined as beginning_Last_subarray + 1. This is because if you have a subarray like [1 -2 1 3] and you get to the last element "3", then you should still be able to use all but the first element (i.e. [-2 1 3]) towards the count. Simply removing the first element is sufficient.
5) A special case here is when the sum of the first i elements is 0. To solve this, keep prefix[0] as 0. That is, build prefix sum index from 1...n (instead of from 0 to n-1) so the first time you see a sum of 0, it has been seen before.
The rest should hopefully fall in place when you see the source code for any of the top contestants. I've added comments to my submission as well. Feel free to ask questions.
This is so well explained. Thank you for your observations.
Thanks, I appreciate it. Glad to share.
Hey!!. Can you please help me understand why this simple sliding window approached failed. I got WA on test case 5. Here's the link to my submission => 75925799
It seems that you're not handling 0's properly. So if you have [7 0 0 0 0 0], it will account for [7], then [7 0], then [7 0 0], etc. However, you're only supposed to count the first one [7] as anything with a 0 is invalid (as any subarray with 0 is invalid per the problem statement).
Someone upvote this guy .
Can you tell me why my solution doesn't work? I used the n*(n-1)/2 approach(and counted the singles seperately). https://mirror.codeforces.com/contest/1333/submission/75916699
This is even better than editorial!
Why bad position is defined as beginning_Last_subarray + 1 ? Could u please explain it a bit more ?
Let's take a string as an example as it is the exact situation and is a little easier to explain with. If the overall string is abcdef and one of the bad strings is abc, then you don't want to just drop abc altogether and count the substrings in the remaining portion (i.e. def). Instead, you need to start from bcdef to count all the valid substrings — you only needed to get rid of the first a and the rest became valid.
Thanks for problem E! At start I thought that there is no solutuon for 3*3 so I built it for 3*4 and then added another numbers around this rectangle. Send it and got wa4, so I made solution for 3*3 and its accpted :)
Is there a place where someone can help me debug my code?
Problem D:
when using cout << endl, I get TLE on test 10. When using print("\n") I get WA on test 7.
Any explanation? 75936645 75936680
because you merged between printf and cout with fast i/o I mean these lines ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
because what endl do is insert a new line and flushes the stream, flushing stream is expensive operation
http://www.cplusplus.com/reference/ostream/endl/
Sad story. I almost solved problem C, however, i used
unordered_map<long long, int>
in the competition and the hashmap solution failed in the system test with TLE verdict. I changed the hashmap intomap<long long, int>
and the balanced tree solution was accepted.Should we avoid
unordered_map
when the key islong long
?you should avoid
unordered_map
whenever you can.Can you explain why? I faced a similar problem and map worked much faster than unordered_map for adding and fetching elements.
Worst case for hashing is O(n) but since map is a bst, all operations are O(logn)
Read this
Why this solution didn't get TLE if he used unordered map???
https://mirror.codeforces.com/contest/1333/submission/75932108 ecnerwala PuRpLe_FoReVeR
I dont know, maybe because of int64_t instead long long
Thank you
I wonder if that's because I submitted with 64-bit GCC. You could try experimenting with that a little. I don't actually know any good reason, I guess I got lucky. I think in general, unordered_map is fine, unless you're worried about people hacking you with specialized tests. It's definitely slower than an array, though.
Thanks for your response. :D
I have AC with 64-bit GCC when submitted code that got TL before
In general, is better use int64_t? or Why did you do?
I do it because it's slightly more modern/idiomatic C++. I don't think there's any difference in practice.
I used map => AC. But in time duration, I used unordered_map => TLE :<
I copied code 75932108 and use GNU C++17 => TLE
And I tried using GNU C++17(64) for 75932108 and my code before (map and unordered_map) => AC. In this case, I see unordered_map run slower than map. I think int64_t isn't related.
Sorry for poor English :<
Woww, That's right, was the compiler what make works the code. Surely in that version the hash is implemented of other way, I'll have to review it, thank you so much.
I tried other alg (rather similar to alg I used before) to solve C problem.
Result: map got AC (GNU C++17 and GNU C++17(64)) and unordered_map got TLE (GNU C++17 and GNU C++17(64)).
So, I think unordered_map can not be stable like map.
Just my experience, use map instead of unordered_map. (Not sure in any case :<)
Check my submissions for details.
Sorry for poor English :<
See https://mirror.codeforces.com/blog/entry/62393
Hey....something strange happened with me during contest i solved problem A and B but now when i checked result it showing only problem A has been solved and Showing TLE for prob 2.......but during contest it was solved and i scored a total points of 1165(450+615) but now 450 only
Read contests rules. Your solution got TLE on system tests
Hey men,this is a rule int div2,we'll have a system test after the contest.
Thanks for the contest! Problems E and F are really good, in my opinion!
Is C only 1250 Score? I think it would be the harder than D.
When and where will I get the editorial for this contest?
Tomorrow I will add a link to this post.
Still wondering what takes you so long...
I participated in this contest and got only B problem solved. But my rating instead fell. Can someone please explain how? I am new to Codeforces.
See your rank, it's a comparitively high rank as compared to your performance corresponding to the pneultimate rating.
How to see the rank? or better yet, where can I see how the rating works here on Codeforces? Thanks.
Is C++17 faster than C++11 ?
The same solution gave TLE for problem D when submitted in C++11 and was accepted in C++17.
C++11 Submission
C++17 Submission
Hey guys!
As promised, I will upsolve the problems in a livestream on YouTube. Hope to see as many as you there!
https://mirror.codeforces.com/blog/entry/75777
Please post the solutions
When editorial will be posted of this round??
construction forces
Real order: A B D C F E
For me is A B C F D E
For me: A C B E F D. D shouldn't be difficult for me, but sadly I managed to make a bug that got caught during systests :( .
how to solve C ? idea needed
For each index (let's call the current index B), find the largest index (let's call it A) such that a[A] + a[A+1] + … + a[B] = 0. Let's call the array of those largest indices X. You can do that using prefix sums. Then, you just run a for() loop over the array and, for each index (let's call the current index I), the number of good subarrays which end at that index is I – max(X[0], X[1], …, X[I]) + 1. The solution is the sum of those numbers. My code
My solution to Problem C
This solution is a bit different than most of the solutions explained here.
Also this is the first time I'm explaining a solution, so please feel free to share any feedback. :)
I used divide and conquer based approach to solve the problem. The idea was to keep finding a subarray with sum equal to 0 until we find one such subarray. After finding a subarray with sum equal to zero, we'll split the array into two parts, calculate the number of valid subarray for each of the two parts and add them to our answer. Also, we need to subtract something from our answer to eliminate overlapping subarrays in both the parts.
Let's assume that, we are trying to find number of good subarray of array a from index l to r (inclusive). We'll maintain prefix sum and keep on storing prefix sum along with ending index in a map. Whenever we encounter a prefix sum value, which we've found once before this(we've already stored it in the map), we know that there's a subarray with sum equal to zero.
For example, we found out that sum of subarray [i, j] equal to zero. We need to find sum of number of good subarrays in [l, j — 1] and [i + 1, r]. Also we need to subtract the number of good subarrays in the range [i + 1, j — 1].
In other words, if the range of our array is [l, r] and we've found a subarray with sum equal to zero which is [i, j] :-
Number of good subarray in the array [l, r] = Number of good subarray in the range [l, j — 1] + Number of good subarray in the range [i + 1, r] — Number of good subarray in the range [i + 1, j — 1]
If there's no subarray of the array [l, r], whose sum is equal to zero, then calculating the number of good subarray is pretty easy. For example if the array is {1, 3, 1, 10, 5}, then the number of good subarray is 1 + 2 + 3 + 4 + 5 = 15.
My Solution
What is the difference between (Div. 2) and (Rated for Div. 2) ? Also this was my first contest and got rating of 1406 with rating change of -94, HOW ?
1) There's no difference between (Div. 2) and (Rated for Div. 2). It basically means that if your rating is < 2100 and you participate in the contest, your rating will be updated.
2) If you participate in a contest for the first time, your first rating will be 1500 + dt, where dt is your rating change. Think of it as the time you create account, you get base rating of 1500.
Thanks a lot for the reply, searched for this everywhere and found nothing.
Rating change was -94 this time so does that mean my performance was relatively bad for the rating of 1500 ?
Also can you also please explain how will my rating change in the next contest i.e. Educational CodeForces Round 85(Rated for Div. 2) ?
I really don't understand how rating change works.
Thanks again for the reply :-D
Details about the rating system can be found here: Blog Post and if you are in a contest and you are really super worried about your rating, you can check it out here: Rating Predictor
There are several posts about rating system.
There's the first one: https://mirror.codeforces.com/blog/entry/102?locale=en
Post that is 4 years old: https://mirror.codeforces.com/blog/entry/20762?locale=en
And the source code of recalculation system: https://mirror.codeforces.com/contest/1/submission/13861109
Also, it's said that rating change from the first contest is different from usual contests. Expected place (seed) is calculated as 1 + n / 2 for people that are new to CodeForces. However, starting from the second it'll depend on your rating.
I hope several hours won't turn into several days. Please post the tutorials.
Hello, I want to ask a question which makes me feel so strange:
my solution for problem C failed in system testing because of 'Time limit exceeded on test 86', 75866276. While as I check the test data and test it on my computer(CPU: 2.6 GHz 6 cores, Intel Core i7), it runs very fast. My code accepted finally as I try to change the 'unordered_map' into 'map' 75972767. Is 'unordered map' runs with such a big constant? I am so confused about this situation as I used to think that 'unordered map' will run faster than 'map'
I still don't understand why. Can somebody give me some explanation? Thx!
This might interest you
Blowing up unordered_map, and how to stop getting hacked on it by neal
wow! thx!!!
Is it me or anyone else found F easier than C D and E? My Submission
can someone have a look on my submission for Prob C ?
https://mirror.codeforces.com/contest/1333/submission/75984070
I'm getting WA on Test Case 9 , I'm unable to find any error in logic / implementation , and the test case is too large for me to enter it manually.
Perhaps
map<int, int> M
is the issue :)so what modification can I make?
i read that using unordered map instead of map can help prevent collisions, but isn't that only helpful if I was getting TLE , how can using map get me a WA if my implementation and logic was correct ?
You use
long long int
s elsewhere, so I thought you'll get the hint quickly ;) Anyway, my suggestion was to make sure that your indexes for sums are alsoll
s, since 2 * 10^5 * 10^9 overflows withint
s.map<int, int>
-->map<ll, int>
and try againusually codeforces marks the line with red where int overflow takes place, And as trying with map<ll,ll> is also not working, what do you think is my implementation / logic incorrect ?(tho I'm getting correct result for small test cases which I can calculate manually)
https://mirror.codeforces.com/contest/1333/submission/75992773
I just tried using map<ll,ll> , still I'm getting WA
Hmm, I don't know exactly what's the further problem, but I don't quite understand why this line is necessary:
Alternatively you can double-check all your 0-based/1-based indexes.
Since your output is larger than that of the jury's, it means your
ans
is not counting all the non-good subarrays. As you may have already noticed, test 9 starts with-816845378 816845378 ...
which makes all the following subarrays which include these first two elements also non-good.Good luck!
Still editorial is not posted???
When will you post the editorial?
Geothermal I wish you'd publish unofficial solutions :)
seems like there is a problem so that the tutorial is not coming up... https://mirror.codeforces.com/contest/1333/hacks
Interesting, some $$$O(n^2)$$$ solutions for B passed system test
Someone know what "several hours" mean?
I really want editorial
Isn't it too late for the editorials to be posted??
sir please upload the tutorials
Downvoted!! because of 23 hours passed since the contest was started and still no editorial!!
Waiting for editorial be like
can anyone explain how to solve problem "C" ....
here is an explanation.
deadly waiting for editorials!!!!!
Can anyone help why i am getting wrong answer on testcase 7 -76004123
"Indexes must point to children with R-mark" This means that you type the index to the boy who is looking to the left. Search bug around this.
Ohk, I got my error , Thanks..