Hello, Westeros!
I'm glad to invite you to Codeforces Round 736 (Div. 1) and Codeforces Round 736 (Div. 2), which will be held on Aug/01/2021 17:35 (Moscow time).
The round will be rated for both divisions. Each division will have 5-7 problems and 2 hours and 15 minutes to solve them. There will not be an interactive problem, so yay!!!
This round would not have been possible without the following individuals:
- Aleks5d, for awesome coordination of my round.
- Benq, for extensive testing and contributions throughout the round, especially for 1548E - Gregor and the Two Painters.
- Monogon, for discussing problems and statements with me for hours on Discord.
- amgfrthsp, for translating statements into Russian.
- MikeMirzayanov, for Codeforces and Polygon.
32 testers
The round had a total of 32 testers. I tried to get a "rainbow" of testers to help guarantee a most balanced round. Thank to you to each and every one of them!
- Benq, hos.lyric, ecnerwala, Um_nik
- TadijaSebez, Monogon, galen_colin, Tlatoani, dorijanlendvaj, rqi
- emorgan, TheOneYouWant
- penguinhacker, ptd, AquaMoon
- ajpiano, arvindr9, ijxjdjd
- wxhtzdy, nnv-nick, alexwice, gupta_samarth
- Starlight-Sailor, 4qqqq, gerzytet, coderz189, NemanjaSo2005
- RobinPH, zyzzsama, SlavicG
- QBaraki
- tdpencil
This is my first round ever written, and I sincerely hope you enjoy it, regardless of your rating!
Score Distribution
Div 1: 500 — 1000 — 1750 — (2000 — 1000) — 3500
Div 2: 500 — 750 — 1250 — 2000 — 2500 — (2000 — 1500)
UPD: Editorial
Winners
Congratulations to all our winners in the round!
Div1
- heuristica, congratulations on the AK!
- tourist, congratulations on the AK!
- yhx-12243
- heno239
- Isonan
Special congratulations to antontrygubO_o and Subconscious for definitely reaching the rank of Legendary Grandmaster!
Div2
Fastest Solves
- 1549A - Gregor and Cryptography: robivirt at 53 seconds!
- 1549B - Gregor and the Pawn Game: speedforces at 4 minutes!
- 1548A - Web of Lies: tourist at 3 minutes!
- 1548B - Integers Have Friends: tourist at 7 minutes!
- 1548C - The Three Little Pigs: gisp_zjz at 19 minutes!
- 1548D1 - Gregor and the Odd Cows (Easy): tourist at 20 minutes!
- 1548D2 - Gregor and the Odd Cows (Hard): tourist at 65 minutes!
- 1548E - Gregor and the Two Painters: mango_lassi at 80 minutes!
Thanks for the early score distribution!
Yeah no problem!
There's no reason to needlessly hide the score distribution.
Newbie Testers Go Here
anyways I'm excited for this contest good luck to all those who are planning on participating
can newbies be testers?
anyone can be a tester if he/she is a trustable friend of the author or the author himself asked someone for testing
I hope to be solved at least two problems...
Codeforces, sorry for my comment, I will not write comments like this anymore. :(
Div 2 Speedforces incoming
As a tester, let me participate officially
upvote for +100 delta
As a tester, zyzzsama stole my as a tester comment :(
Anyways, I liked the problemset of this contest a lot, and I am sure you would also do the same ! Wish you enjoyable contest duration :)
Discrimination of testers on the basis of colour :(
"#justice_for_testers" XD
tester lives matter
As a tester, problems are great!
Benq, for extensive testing and contributions throughout the round, especially for problem G.1-gon, for discussing problems and statements with me for hours on Discord.I tried to get a "rainbow" of testers to help guarantee a most balanced round.check here for the hint-based editorial!Stop it... don't give me this hope...
As a VIP tester I recommend everyone to gain rating!
purplecrayon is purple :<
purplecrayon is actually a crayon :O
What about DioHERO?
As a tester, I think you will collectively get down on your knees and orz Agnimandur for his hard work and awesome problems after contest. I recommend you to read all of his problem statements and wish you good luck!
As a tester, this round is balanced for every participators in both divisions. I recommend you to read all the problem and try to solve as much as you can.
Good luck!
I miss u brother :(
Thanks for a great set of problems. I recommend everyone to participate and gain rating! OMG My first "As a tester..." comment
I recommend you to participate and be master again :P
Am I the Only One who Read ** OMG My first "As a tester..." comment**... In this comment?
No
How to write an invisible text? (OMG My first "As a tester..." comment)
Use some html, I did
<font color="white"> insert_text_here </font>Thanks
I hope to become specialist after this round
Biggest lesson I have learnt is to never target any certain color or rank in cp.I still don't forget the day I registered for codeforces. That is a memorable day of my life.A young kid ( I am still a kid ) had no other other thoughts in mind except writing some codes and how to get the AC verdict.As months went by,I slowly started to think about colors but recently I had come to some realisations :
My love for problem solving is greater than any random color
If I keep loving what I do I will eventually end up reaching my highest potential
Competitive Programming is something which has gifted me a beautiful life.I should keep loving it and not take it as a duty.I should take it as my passion and hobby
Expectations: (see above) Reality: I solve contests to gain my rating (It's just a joke, don't be so serious <3)
i am at 1399 , i was hurt by this lighthearted meme
This may not be the best place to ask it but can we deduce the difficulty of problem from the scoring distribution? Like here in Div2, there is high gap between score for problem B and C.. does it mean the same for their difficulty gap too?
There is no certainity about difficulty of a problem on the basis of a its score in the contest.
Thanks :) Hope to solve till C!!
is Div2 for people <1900 or <2100 ? in these rounds.
<1900
I don't know what's the benefit of ratings distribution. Problems will come and
ratingswill go.Good job
You got "rainbow" of testers, but not "rainboy". That might have led to unusual round ;)
That unusual round might have a scoring distribution like :
(2500 - 2000 ) -2500 - 2000 - 1250 - 750 - 500Now I wonder what will happen when the contest starts...
depending on your rating you are a rated contestant for one contest and unofficial contestant for other. But as long as you don't submit code on a single problem. It is taken as you not participating in the contest
If so he can submit in div2 till pretest passed to avoid penalties in div1.
Well, I have seen a participant in situation like this, and he said 404 Error was displayed when contest started :D
It seems that all registered participants whose rating is higher than 1899 have been deleted from div.2, so I can't find out what will happen(
Hope the problems with the scoring distribution 2000 will be like in previous round(not educational)
ahahah that problem D in round 735?) yeah, it was to ooverrated, should be like 1000
and thanks MikeMirzayanov for this amazing platform
You could have said it without tagging him :|
Umm... Lemme edit
Why so many downvotes people? He changed his comment :(
In this announcement
Total comments = 32
Tester's comments = 69
As a non-tester, I will participate this round!
Positive post
2000 points for div1C OMG
As a tester I can confirm that Agnimandur put a great deal of time and effort into creating a very clear and engaging problemset. I hope you guys enjoy the problems as much as I did.
rainbow follows VIBGYOR btw
Thanks for putting effort for this round! Also hint-based editorial is nice :)
I hope the problem statements are short and the pretests are strong.
Thank you, the pretests are strong!!
I hope I become specialist after this one.
Best of luck, you are near at specialist
Thank you so much!!
I Like Div2-735 round because of short statement and more interesting problem. Hope this round will be more interesting. );
dont bomb the contest
I don't bomb on innocent platform like (Codeforces). Cz, Everybody loves it. I also love it.
Is Codeforces halal, probably not
I think, you should focus on yourself brother. It is not debating site.);
bin laden is a terrotist there is no debating
I trust a Game of Thrones fan
Did the newbie testers outperform the experts?
As a tester, I can confirm that this round has good problems and I hope that you will enjoy it
I hope i don't struggle with B again
https://millionaire.fandom.com/wiki/Shiva_Oswal
Agnimandur is it you? Amazing!
Agnimandur orz!
“regardless of your rating!”I hope so,but it keeps decreasing.T_T
so div1 has only one harder problem than div2? maybe it should have been div(1+2) in this case
Count again, for me it looks like the usual two.
the last div2 is (2000-2500) and the one before last in div1 is (2000-2000) so it's the same problem which means div1 has one extra harder problem right?
Ah, ok, I see.
Better than contest with 750 as first problem :)
Oh f I just realised that you are shiva oswal ,champion of history bee tournament , see this, orz
My trash luck , I forgot to register so I have to wait for 10min. 5k submission for problem a . now when I can finally register, I am in long queue.
First few minutes problem statements to me (In m2 and m3. not able to check m1.)Your text to link here...
I hate div 2 C.
///
thank god i got it finally, wish the same for you guys. But the contest was surely very well made.
+1 ( may be i am too bad to understand the statement (: )
Statement of C was very confusing :(
Yeah, like why use the word "die" in the statement. I missed the part where they are resurrected and all friendships restored. Wasted an hour trying to see what is wrong. Could've been much clearer with a better wording.
Thanks for such an amazing round!
Thanks for great round , solved upto C
RuntimeErrorForces
Getting wrong answer at pretest(5) for D
i think the mistake you are doing is for test case :-
[3,4] here ans should be 1 but my code was giving 2 and get wa in test 5. so you can verify from this case.
it's giving 1
I created the difference array, computed the gcd of subsequent terms, but it's giving wrong answer at pretest(5)
Which terms did you take to compute gcd?
welp, I can't read.
It is guaranteed that all the numbers in a are distinct.
...
Does your code manage the case n=1? That was my problem.
I submitted B first time right when CF crashed, then I went to one of the mirror sites, the submission wasn't showing up. I submitted again, only after that did the first submission show up. Both were TLE, so I got penalty for both. Is there a way to remove the penalty, considering it happened because of the crash? The codes were identical, which confirms my story.
The second submission has been removed, thank you!
I have faced same problem like u
I fixed all such cases automatically.
On the same question i submitted twice with just 31 sec gap one through codeforces website and second through m1.codeforces.com.First approach was correct so they took 50 points for resubmission.Those 54 points cause of codeforces crash is causing me 500 rank difference.The codes were identical, which confirms my story.Don't know why MikeMirzayanov is not looking into it.Maybe cause i am just a specialist. :(
cf predictor not showing results anyone has the same issue
+1
Congrats antontrygubO_o you'll be LGM for the first time!
the unclear problem c statement cost me -50 :( ,maybe they could have told something like "for type 3 queries, we want to give the number of invulnerable nobles, IF we start killing all vulnerable nobles till there are none left" maybe that could have helped
How to solve D?
i think binary search can do it but my solution getting TLE
i tried similar,
lets say for an sequence $$$A$$$ of integers $$$[a_1, a_2, a_3, ... a_n]$$$, there exists an integer $$$m \ge 2$$$ such that $$$a_i\bmod m = k$$$ for $$$1 \le i \le n$$$ where $$$k$$$ is a constant.
that means $$$a_i \equiv a_{i+1} \bmod m$$$ for $$$1 \le i \lt n$$$.
$$$\implies (a_{i+1}-a_i)\equiv 0 \bmod m$$$ for $$$1 \le i \lt n$$$.
that implies that all consecutive differences in $$$A$$$ should be divisible by $$$m$$$ or $$$0$$$. Lets define another sequence $$$D$$$ of integers $$$[d_1, d_2, d_3 .. d_{n-1}]$$$ where $$$d_i = |a_{i+1}-a_i|$$$ for $$$1 \le i \lt n$$$. its clear to see now that $$$\text{gcd}(d_1, d_2, d_3, .. d_{n-1})$$$ will be a multiple of $$$m$$$. (Because all elements of d should be multiple of $$$m$$$ or $$$0$$$)
so we know if gcd of consecutive differences in array elements is $$$ \gt 1$$$. then there must be a $$$m \gt 1$$$. for which $$$a_i\bmod m = k$$$ for $$$1 \le i \le n$$$.
Now, in problem we have to check $$$\binom{n}{2}$$$ such sequences if they satisfy this $$$m \gt 1$$$ or not.
We can easily observe that if $$$\text{gcd}(a, b, c, d)=1$$$ is true, then $$$\text{gcd}(a, b, c, d, \text{(any integer)})=1$$$ would also be true.
so we can do binary search at every index $$$ 1 \le i \le n$$$ for an index $$$i \le j \le n$$$, such that sequence $$$[a_i, a_{i+1}, ... a_{j}]$$$ hold true for condition $$$m \gt 1$$$ (which i wrote in paragraph of this explaination).
this was my first attempt.
but we can also use two pointer to find $$$i$$$ and $$$j$$$, and that should reduce total time complexity by a factor of $$$\log n$$$. but still i am getting TLE in attemp2. :(.
attempt1
complexity is $$$\mathcal{O}(n \space \log^2n \space \log{10^{18}})$$$, first log from binary search , second from segment tree query, third log from gcd function.
that is not suffucient for $$$n = 10^5$$$. because $$$10^5 \times 20 \times 20 \times 60 = 2.4 \times 10^9$$$ that is high.
So i did second attempt turning my binary search into two pointer.
attempt2.
complexity is $$$\mathcal{O}(n\space\log{n}\space\log{10^{18}})$$$, first log from segment tree query and second from gcd function. this is similar to editorial's complexity. but still i am getting TLE and i am unable to figure where is it getting wrong.
My stupid ass was building a segment tree of max size (2e5) for every test case. i didn't realized that it will be called from every test case. :(. and also missed n==1 base case.
Can u please check my solution, I have used segtree+sliding window+gcd. Here is my solution https://codeforces.me/contest/1549/my
very first of all sorry for late reply.
first of all , that is not sliding window, in sliding window we fix the width of window at first.
you have implemented two pointer, same as mine (but slight differently). { min ran at <200ms all cases }
i found one error in your code and three errors that have yet not gave you WA/RE.
you are passing
vector<ll> difftobuild()by value.this will cause your program to copy all values of
vector<ll> diffto another newvector<ll> diffofbuild()scope.and this will happen every time your code call
build()because there will be $$$2n$$$ calls to
build()and every time it will copy $$$n$$$ element of
vector<ll> diff.this will cause to $$$2n^2$$$ unnecessary operations just to copy diff in every call.
you can avoid this by writing following code:
&specifies that this argument is called by reference and not by value. so it will not copy youvector<ll> diffrather just pass the regerence to originaldiff. hence will save of unnecessary $$$2n^2$$$ operations.This is where you are gettting TLE from.
here you are allocating space for segtree on stack memory. this will definately cause stack overflow and will give you RE. here is a video to know about allcoations.
You can allocate this
segtreearray on global scope, that will save you from RE.check your code what will happen when
n==1.Here you are first checking if e < n-1 // size of diff array
and then incrementing it in first if condition
and value of e could be n-1 in the line 4. this can cause RE.
thats all what i could find out of first glance there could be more.
Thanks for such a detailed error analysis. Finally, I was able to get AC in it.
you are welcome.
Binary Search on answer + segment tree for range GCD. The segment tree gives TLE in Python so I used the Sparse table for that.
Using two pointers work. The fact that the contiguous array of the difference array (array containing the differences of the original array) has to have gcd greater than 1 in order for a subarray to be good allows this approach (hopefully) works
I DID THAT, BUT GOT WA IN PRETEST(5)
The funny thing is when I got WAs, I just resorted to good ol' #define int long long and it worked for me, but I got WA in pretest 7 so this may not be applicable for you.
Sparse Table + GCD + Two pointers
Let's make an array b for differences a[i] — a[i — 1]. Now let's use the two pointers technique to find the largest subarray of b with gcd > 1. The answer is its length + 1. Code:
Video Solution for D, this is how i did it!
First contest where I was able to solve A, B and C. Maybe they were too easy but still.
Problem C is actually very nice if perceived through generating functions. We're basically interested in the sequence generated by
$$$F(x) = \sum\limits_{n_0=0}^n (x+1)^{3n_0}=\frac{(x+1)^{3(n+1)}-1}{(x+1)^3-1}$$$
Here numerator can be calculated in $$$O(n)$$$ after which $$$F(x)$$$ can be obtained by standard long division division also in $$$O(n)$$$.
I figured out a different method : Lets start at second s, and say last second is e, then
S(x) = -C(3s,x+3) + C(3e+3, x+3) — 3*(S(x+2) + S(x+1)). This can also help in solving it on O(n) I think.
TL was very tight :')
It seems like none of the testers spotted the easy solution of Div1D1.
What was the easy solution? I used pick's theorem for finding that number of boundary points should be multiple of 4.
After that you can split the points into groups based on the x coordinate and the y coordinate's remainders modulo 4.
I'm pretty sure that was one of the intended solutions for D1.
Then I don't know how it is harder than C...
C is such a troll problem.
That's exactly what I submitted in testing... (Infact, mod 2 after diving all coordinates by 2)
Time constraint on problem C is too tight I think. Just calculating factorials caused tle :(
A moment of silence for those who read the announcement about C after 1 hour from reading the problem including me
Edit : it's actually my fault if i read the problem better i would have understood that but I did the same mistake again i should not hurry up solving before completely understanding the problem
Damn! I didn't read it and got WA on pretest 4.
same :( ...
Does anyone know what pretest5 was? Using 2 pointer approach. I did handle n=1 and 2 separately.
I used segment tree (for gcd) on differences and then binary search to find longest length.
I cried for 30 minutes but then I realised..
1 2 15 14
(hope this testcase helps you pass pretest 5 :)
Way too many points given to Div1D1/Div2F1 for its actual difficulty, in my opinion.
Idk why but problem D seems to be easier for me.
Same :-)
In my opinion, it was hard
please try to avoid useless implementation problems like C.... couldn't the problem setters find any better problem??
You found it hard doesn't mean the problem was bad. And you can't just bash problem setters for the same.
whether i find the problem hard or easy is irrelevant to the problem being bad... in my opinion that problem was just there to give people some typing practice
What implementation was there? The trick was to understand you only need to know how many nobles there are that are not friends with higher nobles. That's it. look at my solution...
Why? The best way to train is to focus on your weakness and improve it, even I got a little bit tricky on problem C.
lmao, I was 7th person to solve D, yet I struggled to solve B for an hour. I sometimes hate myself. :(
Div2 Problem C was elegant! Enjoyed solving it!
How to solve B?
Check if you can kill enemy pawn in the same column, previous column (if enemy exists) and then next column (if enemy exists) for each pawn. Submission
also keep updating those pawns that have already reached the end line.
I have submitted solution for b twice within a interval of 30 seconds both the solutions are exactly same.Thing is when i was submitting my first solution the website crashed so i submitted again from m1.codeforces.com .I lost 54 points cause of that it would be great if someone can help me through this.MikeMirzayanov
At least MikeMirzayanov should look into it and update me.
Thanks MikeMirzayanov.Keep up the good work
WEIRD CODEFORCES COMPILER and WHY DOES THE CUSTOM INVOCATION EVEN EXIST DURING THE CONTESTS.(T_T)
Hello Codeforces community,
I joined codeforces recently but faced a weird issue in todays contest. In the problem C.Web of Lies.
The answers to sample input were compiling and showing perfectly correct answer in my sublime code editor and even online on more than 5 different sites.
BUT, I don't know what sort of a compiler does codeforces have (T_T) it always showed wrong answers on the sample test case.
More over if I try to use the CUSTOM INVOCATION, it literally takes 10 minutes to compile 1 piece of code.
WHAT TO DO IN SUCH A SITUATION, when all other compilers are showing correct result but codeforces compiler doesn't and the custom invocation is almost useless through out the contest.
Please someone with prior experience EXPLAIN how to tackle.
I know something must be wrong in my code.... BUT WHERE DO I DEBUG IT? (T_T)
Your profile pic is violating CF terms and conditions, consider changing it.
Look, in some compilers, it ignores out of bounds or erasing elements not in the set and so on. but in Codeforces the compiler doesn't, it prints an unexpected answer. here are some tips when you face these problem:
Div1 B is basically same as this problem
How to solve Div 2D? please write your solution in hints.
Difference array
Find the size of the largest subarray in the difference array which all elements have GCD>1
Use two pointers
I did the same thing. It failed pretest 5. Any idea what it could be?
I was stuck at pretest 5 TLE because i bugged two pointers inequality
Maybe ?
Ans is 1 right? I did handle n=1 and n=2 separately.
not sure, I got two wrong answers because of that case :/
I love your problems <3.
E is #combinatorics
F is #geometry, Pick's theorem? I don't know for sure.
Not only the topic you covered but also: Short, clear statements.
You got my orz, sir!
Waiting for the solution!
I HATE GCD
I LOVE GCD
How to solve C ? I couldn't even get a clue after 1.5 hours
All you need to do is maintain $$$indegree$$$ for each vertex and add initial $$$vulnerable$$$ vertices in a set . For $$$query$$$ of type 3 $$$answer$$$ will be $$$n-vulnerable$$$ $$$points$$$. For type 1 $$$query$$$ increase $$$indegree$$$ of smaller vertex by 1 and add it to the set if not already added . For type 2 $$$query$$$ decrease $$$indegree$$$ of smaller vertex by 1 and remove it from set if it's $$$indegree$$$ after update becomes 0
Oh.. Thanks a lot. I was doing something complicated unnecessarily
Make a frequency array $$$f$$$, where $$$f_i$$$ represents how many nodes $$$j$$$ are greater than $$$i$$$. The answer is $$$n - k$$$, where $$$k$$$ represents the number of nodes $$$i$$$ where $$$f_i \gt 0$$$. For each $$$1$$$ operation, increase $$$f_u$$$, where $$$u \lt v$$$ by one. If $$$f_u$$$ was initially 0, then increase $$$k$$$ by one. For each $$$2$$$ operation, decrease $$$f_u$$$ by one. If $$$f_u$$$ was initially 1, then decrease $$$k$$$ by one.
I submitted a similar solution during contest, but it failed pretest 4 as WA. Can someone help? 124599669 Edit: Just found out why. It was because I unnecessarily reset the states after doing query type 3.
Can anyone tell me, what's wrong in my code.
int n,m; cin>>n>>m; vector<int>adj[n+1]; for(int i=0;i<m;i++){ int x,y; cin>>x>>y; adj[x].push_back(y); adj[y].push_back(x); } int has[n+1]={0},fam[n+1]={0}; for(int i=1;i<=n;i++) { int cc=0; for(auto it:adj[i]){ if(it>i && has[it]==0){ cc++; } } if(cc>0){ has[i]=1; } fam[i]=cc; } int cnt=0; for(int i=1;i<=n;i++) if(has[i]) cnt++; int q; cin>>q; while(q--) { int x; cin>>x; if(x==3) cout<<n-cnt<<endl; else{ int y,z; cin>>y>>z; if(x==1){ if(y>z && fam[z]==0 && has[z]==0){ cnt++; has[z]=1; } else if(y<z && fam[y]==0 && has[y]==0){ has[y]=1; cnt++; } if(y>z) fam[z]++; if(z>y) fam[y]++; } else{ if(y>z && fam[z]==1 && has[z]==1){ cnt--; has[z]=0; fam[z]--; } else if(y<z && fam[y]==1 && has[y]==1){ cnt--; has[y]=0; fam[y]--; } } } }Great problems!
Great contest!
i like the sentence "the wolf does not eat the little pigs, he only makes plans"
is fft possible for d1c somehow? i understand that modulo is bad, but maybe it's possible with some magic
Yeah, I designed the problem to be as hard as possible for FFT to pass. Maybe it works, IDK, but it would be a very very tight squeeze.
Any particular reason for this choice? I don't think FFT-based deconvolution is any more or less interesting than the long division approach I ended up coding.
It's barely even possible to calculate multiplicative inverses of $$$1, \ldots, 3N$$$. No way even a single $$$O(3N\log N)$$$ FFT would pass.
Or so I thought...
You can use the formula $$$(n!)^{-1}=((n+1)!)^{-1}\cdot (n+1)$$$ to calculate multiplicative inverses of factorials in linear time, and thus multiplicative inverses in linear time.
Ah, of course! I was always using the trick that $$$(2n)^{-1} = 2^{-1} n^{-1}$$$.
Nice trick. I usually find inverse modulo $$$m$$$ for all numbers from 1 upto n with $$$i^{-1}=-[m/r] \times (m\%i)^{-1} (mod\, m)$$$ and then multiply them all together to get inverse factorials. (Proof can be found here: http://e-maxx.ru/algo/reverse_element#4 )
This works in 764ms.
For the last one hour I was stuck on D with this problem- "If I apply two-pointers on diff array, how can I find gcd of each segment?". At the last minute, it occurred to me that I can use Segment Tree. But it was too late by then. Looks like I have to practice more seg tree problems.
Great Problems tho. Loved them all :)
Or if you are in the minority like me — use the sparse tables :P
I also used sparse tables. I still don't know how two pointers works
Notice that for $$$i$$$ if it contributes to the final answer $$$f(i) \gt = f(i - 1)$$$ This essentially means that we should keep some suffix of the maximum result for $$$i$$$ in the result of $$$i + 1$$$. So just traverse left indices from $$$0$$$ to $$$n - 1$$$ and greedily try to match the maximum suffix of $$$i - 1$$$ to $$$i$$$. Take a look at my submission to understand it better.
To practice this sort of things take a look at last educational round's E or CodeChef Lunchtime Div1A that was held yesterday. Both of them utilize two pointers in the same fashion this one does.
Got it, thanks. I confused myself. I thought there was some raw two pointers magic to solve it without using sparse tables or segtree, but the two pointers is just the alternative to binary search
Why aren't they allowing segment trees to pass in D. I didn't knew about sparse tables.. :((
Actually I passed the pretests using segment tree
depends on whether you used binary search or 2 pointers
Yeah, I totally get it.. I should have used 2 pointers
I have passed pretest(hopefully system test also) using binary search + segment tree
Pray for ACCEPTED ^)
Editorial has been released!
Thanks for a quick editorial!
why the system tests are so slow?
seem like OJ is lazy today :)
Seems like system testing stopped, does anyone now why?
Cool contest!
Is it just me or did the expected rating calculator break during contest?
Yeah, it was broken throughout the whole contest for me
Because the server banned the API for rating calculator during the contest,so everyone was affected.
Problem C- Web lies My code is giving memory limit exceed on pretest 4 Can anyone give an efficient solution ? so that i can check where I did wrong. submission :- 124601371
paste your code and run it on (https://ideone.com/) and share the link . It is very difficult for anybody to read your code now.
You seem to be using an adjacency matrix to represent your graph, which has O(n^2) space complexity. Try using an adjacency list instead.
system testing is teasing now !
Come on guys, technical issues are unavoidable but at least you need to communicate. Or are we due for another donation campaign?
It was great to listening to Light of the seven while reading C.Web of Lies. that's why my fantasy drived me far away from the solution.
I was getting constant GOT nostalgia while solving D2C.
Best editorials <3
Why is system testing slower than my learning rate?
Was someone as savage as me to submit a flow solution to div2B? XD
I believe no XD
Hopcroft-Karp-Karzanov algorithm with some optimization might pass the tests within the time limit. Because the number of edges will be at most 3n.
Yes, sure. With Max flow I meant the max matching approach.
I did XD
SAAAAAAAAAAD man! I got MLE in problem D for not handling the case n=1 as I was using Segment tree. Even though I don't know why it gives MLE I think in this problem, it should give a runtime error.
Same. Not handling n=1 case. And got MLE. (╯︵╰,)
Same didn't realized that until I saw your comment, I thought maybe $$$4N$$$ was too large but fortunately writing iterative segment tree worked it didn't required handling $$$n=1$$$ case separately.
I was thinking the same as you, typically! but the problem is that the contest ends before I finished writing the iterative segment tree as I haven't trained before on the iterative ones.
Time taken for system testing == Number of times the site crashed
You didn't even took part in the contest, what system testing are you waiting for?
I submitted A first time right when CF crashed, then I went to one of the mirror sites Codeforces3, the submission wasn't showing up. I submitted again, only after that did the first submission show up. so my first solution was skipped last solution wask taken. Is there a way to remove the last submissions, considering it happened because of the crash? The codes were identical, which confirms my story.
→ Reply
As a newcomer it's really frustrating for me. I think CF CF team will consider my situation.Thank you
Apparently you can't resubmit your same code.
You literally copy-paste this comment and moreover, YOU FORGOT TO ERASE THE "→ Reply" text
Come on, at least make an efford
Hehe nice, imitation is the sincerest form of flattery...
I replied it in your comment that i have faced the same problem like you.My english isn't good so i decided to copy your.by the way give me some pro tips that how can i be a master like you?
No worries, I just found it funny. There aren't many pro tips I can give you, but here are a few notes for you current level: 1) don't focus on known algorithms, you will never see them in div2 A and B problems 2) focus on coding and learning to debug efficiently (you will always make mistakes) 3) always upsolve problems A, B and sometimes C from rounds, if you miss a round try to do it virtually.
Biggest tip is to have fun and don't worry too much about rating. You are at a point where much improvement is possible. Best of luck!
what a person should focus on if the person can solve A,B,C(sometimes) in contest. Upsolve C,D ? or something else
If you're high pupil/specialist and solve ABC, at that point you should start learning some very basic algorithms, maybe about graphs (not above DFS and BFS!) and dp (again, nothing too complicated). Always upsolve C and D (D might be a bit hard, but try to read the solution anyways). If you're solving ABC and you're not at least high pupil, you should still follow the last plan and practice more coding.
Did anyone else solve B by maximum matching? Yes, I'm that dumb!
aniervs actually did that
I'm so happy that the editorial mentioned this solution too.
time until sys test end
tl retest(tl retest)
Benq, for extensive testing and contributions throughout the round, especially for problem G.I couldn't find problem F or G xD. I wonder what happened?
Testers look at the round as combined, so G refers to div1E.
Oh, okay. Thank you for clarification.
From problems to editorial, I can see that you have put in a lot of efforts to make us learn things. Thank you so much for this round!
Thanks for the contest <3. Hope you make more contests like this one.
During the contest Codeforces freezed! But I was able to submit the soolution for the second problem in main website. But it didn't show any confirmation of the submission. As a result, I assumed that my solution wasn't submitted hence I submitted the exact same solution again on m1.codeforces.com. If both the solution are exactly same why should the first solution be skipped and not the second one ?
I think problem D was pretty similar to a codechef problem Max Subarray GCD.
lol I thought in C you have to print the number of moves in which the process ends
Wait a minute, how am I on the fastest solves list? I didn't even close to be the fastest solve on A.
Yeah sorry about that, fixed now.
Does Gregor (in the problem statements) stand for Gregor Clegane (Game of Thrones character)?
As a code author, I hope you gained rating!
Tourist is at a point where 2nd place is also costing him some ratings!
Let's wonder when tourist will lose rating at the 1st place XD
But actually, maybe it's not realistic :(
Only if tourist gains inf rating XD
Editorial dissapeared. Agnimandur take a look please.
Why does it says that I'm not allowed to see the editorial?
Why cant I access the tutorial?
How can I see the Editorial?I was told that "You are not allowed to view the requested page".
same thing here Agnimandur
The tutorial seems still wrong now.I hope Agnimandur knows it.
Why can't I access the editorial? Is there anyone who has the same problem?
I can't neither. I am not allowed to view the requested page
That's so strange. Might check it tomorrow
Why can't I watch Editorial?It gives me "You are not allowed to view requestedx ..." warning.
It will get fixed. Yesterday too same issue came up but got fixed after few hours :)
Can't access Editorial. Please fix it.
It has been fixed now. Thanks for Fixing itIt is fixed now :)
Do cp they said, It will be fun they said.. :_)
Thanks