Codeforces Round #758 (Div.1 + Div. 2)

3 years ago, # |

+56

I loved the problems.

→ Reply

Maango16

3 years ago, # |

← Rev. 2 →

Note The Unusual Timings

:')

→ Reply

shubham_bit2

3 years ago, # ^ |

+40

Unusual Timings are becoming usual these days :|

→ Reply

Ooommmkrs

3 years ago, # |

-29

Will it be based on ICPC style scoring or problems will have separate points like in normal div 1+2 rounds?

→ Reply

realRainFestivalqwq

3 years ago, # |

I think div.1 + div.2 always be a big challenge and it means large rating increasing or decresing. Hope everyone can gain more rating!

→ Reply

Mahim

3 years ago, # |

+20

After 10 days of break, finally a codeforces round. Hope this round will be good.

→ Reply

3 years ago, # ^ |

+250

After 10 days of break, finally

Wait until you get to Div. 1 if you think 10 days is long.

→ Reply

Mahim

3 years ago, # ^ |

← Rev. 2 →

For div 1 coder, like you, the word should be "long long long long".

→ Reply

Rating is the motivation and that's the fact.

3 years ago, # ^ |

+36

long long long long

I believe the technical term is __int128 :)

→ Reply

NaOH_Frog

3 years ago, # ^ |

No no no it is __int256. You've counted wrong, long long long is __int128.

→ Reply

somerandomaltacc3034

3 years ago, # ^ |

+189

→ Reply

ssvb

3 years ago, # ^ |

-83

Nothing prevents you from doing unrated participation in Div.2 rounds. That is if you want to have fun solving problems together with the others and then discuss interesting solutions after the contest is over. Also in an unrated round you are free to start solving problems in reverse order if wasting time on Div.2 A/B/C/D is not enjoyable.

→ Reply

aryanc403

3 years ago, # ^ |

+88

→ Reply

ssvb

3 years ago, # ^ |

-43

I participated in an unrated Div.3 contest on Codeforces when I briefly became expert. And I participated in a few unrated Div.3 / Div.2+3 CodeChef contests too. Not to mention AtCoder AGC contests (unrated for a different reason). All of these contests were fun and challenging, even though they didn't affect my rating. So what exactly would I not get?

→ Reply

aryanc403

3 years ago, # ^ |

+42

Participating in the first unrated contest (because one is an outside the rated range) is wholly different from consistently doing it.
Judging from your comments (related to different languages and compilers) that may not be the case with you. But it's the case with the majority of people here.

→ Reply

3 years ago, # ^ |

+102

Then the original commenter still shouldn't complain because nothing prevents them from doing HackerEarth contests and geography homework.

→ Reply

ssvb

3 years ago, # ^ |

-47

I have nothing to say about your "geography homework" claim, because it's a total nonsense. I'm putting the rest of my reply under a spoiler, because it's a bit too long:

Spoiler

→ Reply

3 years ago, # ^ |

← Rev. 2 →

+30

You are overthinking it.

The meaning of my first comment: Div. 1 contests are more sparse than Div. 2 and it is kinda funny to see Div. 2 people complaining.
The meaning of my second comment: A Div. 2 contest is not the same as a Div. 1 contest, just as a Div. 2 contest is not the same as a HackerEarth contest.

That's it. That's the meaning of these two comments. Extracting anything else from there is a bit silly.

Here is my reply to your essay

Then you are participating in a combined division contest, one of those easy problems bites you in your behind and your conclusion is that ... the format of Div.1+2 contests is just wrong. Of course this has to be it! Because it can't possibly be your own fault, right?

Why must you extract more meaning from my comments than they contain? My comments are not a secret way of saying "I hate combined division because I recently lost rating on one". Just like I don't think that your comments are a secret way of saying "I love combined division because I recently gained a lot of rating on one", you should not think something similar about me.

The idea that I look down on Div. 2 contests is also just false. I don't know where you get that from but I guess you must be reading some of my comments and as you did now, add explanations or meanings to them that aren't there.

In general I don't understand why people so commonly seem to think they have it all figured out if they find just one connection. "Why is he complaining about combined division? Oh, he lost rating in a recent one, that must be it!" That explanation would certainly explain it, so it is probably true, right? $$$B, A \to B \vdash A$$$?

I have complained about combined division rounds many times in the past. Here is a short list. This compilation should at least show that it is not an opinion that forms after performing badly only. Rating change wise, I have never performed as badly as the last combined round, yet I have had the same opinion previously all the same.

The next idea someone might get is that I might dislike combined rounds because I usually get a rating drop there. But this is not the case. Here is an image of my recent combined division rounds. I removed the Div. 1 only rounds. We see some ups and some downs, in general there seems to be no reason to believe that I perform worse on combined division. So this also doesn't hold up.

I don't know what else to say, but I think it might just be plausible that I simply don't like combined division rounds and there is no self-deceptive reason behind that? After all, I haven't claimed that they are somehow objectively bad; I haven't claimed that their "format is wrong". I think I have made it clear every time that my dislike of combined round is subjective and just a feeling, not a claim that they are objectively wrong.

→ Reply

steadyEffort

3 years ago, # ^ |

→ Reply

3 years ago, # |

Why is the round combined division?

Personally, I hate combined division rounds with a passion. Even if they are very nice, I find that adding two easy problems to Div. 1 makes the round less enjoyable, at least for me. What is more, I find it horrifying that every scheduled, rated for Div. 1 contest until the end of the year is combined division. I can sort of understand why Global round is combined division, and I suppose that it is somehow traditional that the Good Bye round is combined division (especially if it is sponsored and therefore may have prizes) but what is the reason for this round? Just that it is a copy of some other contest?

→ Reply

dCoding

3 years ago, # ^ |

-21

Why though?
From what I understand (admittedly having never been in div 1), shouldn't combined rounds ideally be, for div 1 participants, a 30 mins or so speedtyping contest and after that a normal div 1 round?

→ Reply

3 years ago, # ^ |

+44

Do you find a 30 min speedtyping contest fun?

Further, getting stuck on one of the easy problems is the worst feeling in the world and is a major tilting factor for me.

→ Reply

dCoding

3 years ago, # ^ |

Yeah, understandable. Separate div 1 and div 2 rounds seem much better then for div 1 participants, since they take away the speed-typing part of it.

→ Reply

Gary2005

3 years ago, # ^ |

+60

Agree, when I solved A,B and saw over 1000+ people have passed,the feeling is really bad :(

→ Reply

tfg

3 years ago, # ^ |

+17

Good thing this contest was just a regular div1 with an extra easier problem :clown:

→ Reply

asfd221

3 years ago, # ^ |

This is a tangent. If I face trouble solving a problem, I don't call it easy. Actually I try to refrain from labeling problems "easy" and observations "obvious". I don't like people doing that either, NGL. By calling something "easy" we undermine the observations which were required to solve it whether we meant it that way or not. Not at all saying its right or wrong, just felt this viewpoint should be out there.

→ Reply

WeakestTopology

3 years ago, # ^ |

+88

Normally, I wouldn't worry too much about 30 mins of speedtyping, but the fact that this combined round is just 2 hours long makes me nervous, since it leaves only 1.5 hours for Div 1 problems. That is, if we do not fuck up and waste more time on the easy ones...

→ Reply

ivan100sic

3 years ago, # ^ |

+138

Combined rounds and easy problems are the reason why I'm at 2800 and not 2500 and I'm not very proud of this

→ Reply

flashmt

3 years ago, # ^ |

+51

A 2 hour combined round sounds really scary to me. Div 2 people tend to like combined rounds because they can gain a lot of ratings with a good performance. It sucks for us but we are the minority after all.

→ Reply

endless_summer

3 years ago, # ^ |

is it true div2 people can gain more rating in combined rounds? based on my experience the gains are exactly same as div2 rounds

→ Reply

flashmt

3 years ago, # ^ |

If you over performs and beats some Div 1 participants you're not supposed to, you will gain more than you do in a normal Div 2 round (because you won't get a chance to beat them under this circumstance). This of course only applies to very few people each round but it does generate a mental effect for a lot of people.

→ Reply

jimm89

3 years ago, # ^ |

← Rev. 4 →

There is a benefit to combined rounds, though. In many Div 1 only contests, if people don’t like the look of problem A they just bail out to stay unrated, which means that those who actually try are penalised for it. There was a very recent example of this in round 745 Div 1 — problem A was hard so over half the registered competitors submitted nothing. I think having a problem A and B doable very quickly kind of forces your hand — you’re either in or you’re out, you don’t have time to play the system.

This is not to say that you don’t make many valid points; just to point out one benefit which I actually consider quite significant.

→ Reply

3 years ago, # ^ |

Frankly I think that in every contest the problem A should be easy for all intended participants, partly because of what you said but also for other (mostly, psychological) reasons.

→ Reply

StArChAn

3 years ago, # |

-34

Imagine not upvoting this blog.

→ Reply

Salmon1

3 years ago, # |

-7

Nice

→ Reply

TuHoangAnh

3 years ago, # ^ |

+14

hi :D

→ Reply

Salmon1

3 years ago, # ^ |

+14

Hi you

→ Reply

FlowingCloud

3 years ago, # |

-8

lol

→ Reply

_lowerBound

3 years ago, # |

+13

So, my plan is to solve as many problems till 13:00 and then instead of despairing at the last 3-4 problems, I'll switch towards ABC contest to keep up that sense of achievement. #ICheatMyself

→ Reply

Riblji_Keksic

3 years ago, # |

+13

the best round because it's written by the best programmer

→ Reply

P_Key26dec

3 years ago, # ^ |

the reason newbies are bloody scared lol..

→ Reply

mindFlayer

3 years ago, # |

+20

No testers are begging for contributions (specially 1-gon) XD.

→ Reply

3 years ago, # ^ |

+97

Idk maybe ill just rant about testers commenting in blogs here since the round is over. Why is it normal that testers are commenting things such as "I loved problems", "Problems are beautiful". Why is everyone fine with people saying that? Would people be fine if I commented "I didn't enjoy the problems, they were boring"? Should we normalize testers saying "I hated the problems" in future contests now?

I honestly find it hard to believe that the guy who only solved ABC in VC and didnt upsolve anything else commented "I loved problems" because he genuinely loved the problems. You really looked at ABC and went "I love these problems"?

Can we as a community just stop pandering these types of testers, please. Make testing be a job of ensuring contest quality, not a contribution farmer for those with the right connections.

Thank you for listening to my TED talk.

→ Reply

oolimry

3 years ago, # ^ |

+16

There really is nothing wrong with testers saying "I loved problems", "Problems are beautiful" as a tester if you really enjoyed the contest. In fact, I think its a good way to encourage others to take part in a round that you believe they will enjoy, as well as a public compliment to the setters

But of course if you recommend the contest and people didn't like it otherwise, then you're at fault for misleading the participants who hoped for a good contest, and also making future "I loved problems" recommendations by testers less credible for actually good rounds. If they're an outlier who thinks it's good while others thinks it's bad then whatever, but outliers are rare (and should know when their opinions aren't aligned with what others think)

Anyways, if no tester comments anything, it probably says more about the round than if testers are commenting if they enjoy testing

→ Reply

Indians_cheating

3 years ago, # |

+11

if any of you are interested in cheating, send a message to nitin_05 or ashokesen02. they both became experts in codeforces by buying solutions and adding many comments in the codes.

→ Reply

StArChAn

3 years ago, # ^ |

Don't increase the interest. The situation already sucks as it is.

→ Reply

ajeet_1606

3 years ago, # |

-34

What may be the difficulty level for the problems?? If I could know, I could decide whether to participate or not as I only can solve up to 1200 difficulty level, anyone please have idea??

→ Reply

JEE_MAIN_LOOSER

3 years ago, # ^ |

← Rev. 4 →

-24

A - [800,900] (Greedy or some basic maths)

B - [1000,1200] (Implementation or Greedy)

C - [1300,1400] (Bs, prefix sum Greedy, two-pointers)

D - [1500- 1700] (some data strcture, dp, maths ,even greedy

Beyond This i dont know Clearly coz i havent solve any :_:

→ Reply

M_bolshakov

3 years ago, # ^ |

I think even C will be about maths, not to mention any further problems

→ Reply

turzo_sawroop

3 years ago, # ^ |

If you have this mentality, you will never improve

→ Reply

turzo_sawroop

3 years ago, # |

I have a gut feeling we are going to face problems of Byteland

→ Reply

P_Key26dec

3 years ago, # |

contestfull day it is...

→ Reply

binary_vijay01

3 years ago, # |

-12

Give me some delta ...

→ Reply

binary_vijay01

3 years ago, # ^ |

Looks like I forgot to mention "positive". So much of negativity out here (:

→ Reply

aknov711

3 years ago, # |

← Rev. 3 →

-32

Hope to gain some non-negative delta!

→ Reply

Omja

3 years ago, # |

+20

The difficulty gap between C and D

→ Reply

mon0pole

3 years ago, # ^ |

I guess they wanted people to switch to ABC 231 xD

→ Reply

P___

3 years ago, # ^ |

+10

The difficulty gap between C and B...

→ Reply

destroyer_a

3 years ago, # |

Before starting of the round : "I am gonna try to get to 1100 this time" After implementing problem B : "Ahh !! Shit, Here we go again"

→ Reply

uzzal_rahman

3 years ago, # |

+31

Thank you very much for a disgusting round.

→ Reply

ljuba

3 years ago, # |

-19

Me after rating changes.

→ Reply

Jhin

3 years ago, # |

Hmm this is weird my solution for C is n*Log(n) but it's TLE I can't see what did I do wrong

→ Reply

azureboy

3 years ago, # |

It was so difficult that I sat down in two minutes

→ Reply

MijPeter

3 years ago, # |

+13

I'm gonna have nightmares about B. Daaamn it took me so long to to get it.

→ Reply

uzzal_rahman

3 years ago, # ^ |

how to solve it?

→ Reply

MijPeter

3 years ago, # ^ |

← Rev. 2 →

please I dont want to talk about this problem anymore.

But basically if abs(a — b) > 1 then you can't construct it.

→ Reply

MrOtter

3 years ago, # ^ |

← Rev. 2 →

also you can't construct it if a + b > n — 2

→ Reply

Neketman

3 years ago, # ^ |

← Rev. 2 →

If a + b = n - 2, you actually can in some cases construct a valid solution.

Example: n = 4, a = 1, b = 1

Answer (one of): 4 1 3 2

Edit: the previous commenter changed >= to >

→ Reply

MrOtter

3 years ago, # ^ |

I meant > of course, changed previous message

→ Reply

srikaran_p

3 years ago, # ^ |

← Rev. 2 →

You can take the starting value to be (a+b+1). Then, store the remaining values in a deque in increasing order. If you have to put a minima, take the least value from the deque and put it in the array. If you to put a maxima, take the greatest value from the deque and put it in the array. When you run out of the required maximas and minimas, you can put the remaining values in increasing order (if the previous value was a minima) or decreasing order (if the previous value was a maxima).

And, do not forget about the edge case when a = 0 and b = 0.

I hope this helps.

→ Reply

Furukawa

3 years ago, # |

← Rev. 2 →

+111

thank you for the worst contest i've ever seen , and f**k problem B

→ Reply

Furukawa

3 years ago, # ^ |

← Rev. 2 →

We should vote down this contest. B isn't the only reason why I felt awful. Otherwise there will be more contests like this contest.

→ Reply

CoderAnshu

3 years ago, # |

My solution to E is nlogn*24, was it intended to fail? I have used ordered_sets which could have been avoided using fenwick but didn't have time to implement.

→ Reply

3 years ago, # ^ |

With $$$n = 10^5$$$, it should be very hard to fail on CF machines. My solution also uses those super slow multisets and runs in 1.2s on the worst of these 60 pretests.

Speaking of which, 60 pretests is excessive. This isn't some kind of wild random problem where no solution is guaranteed to be 100% AC.

→ Reply

CoderAnshu

3 years ago, # ^ |

I saw other submissions too and they have used ordered sets and seem identical to my approach, but why I failed T-T.

→ Reply

3 years ago, # ^ |

Actually, I submitted > 30 times, spent > 5 hours to optimize it, couldn't...

→ Reply

CoderAnshu

3 years ago, # ^ |

Then what's the intended complexity?

→ Reply

3 years ago, # ^ |

-10

It's the same, and is indeed way faster than mine.

→ Reply

3 years ago, # ^ |

138774185

As straightforward as it gets for time complexity, 2*2*2*3*2*2 times we sort and gradually insert/remove $$$N/3$$$ elements. Multiset gives 1400 ms, heap 700 ms.

→ Reply

3 years ago, # ^ |

Yeah, but still there are many reasonable ways to implement it which has way worse multiplier. Mine had > 500 I guess. However it could barely pass TL with the new constraints.

→ Reply

Restricted

3 years ago, # |

Why did problem C have 1sec time limit instead of 2?

→ Reply

thunder_strike

3 years ago, # |

+34

What the fuck was problem B

→ Reply

_Vanilla_

3 years ago, # ^ |

cancer

→ Reply

rajatm2136

3 years ago, # |

Hint for B?:(

→ Reply

SouLPegasiuuuS

3 years ago, # ^ |

Spoiler

→ Reply

usernameson

3 years ago, # ^ |

← Rev. 2 →

Spoiler

→ Reply

ac1701054

3 years ago, # ^ |

we can use two pointer approach to avoid lenghi implementation

→ Reply

usernameson

3 years ago, # ^ |

I constructed it using a deque. I thought about 2 pointers but I didn't want to have to deal with the case when n is odd and the left and right pointer meet at the same point.

→ Reply

LYC_music

3 years ago, # |

+37

Why only 2 hours???

→ Reply

TaawraaT

3 years ago, # |

What an unbalanced problemset!

→ Reply

dostigator

3 years ago, # |

+22

worst contest I've ever competed in

→ Reply

3 years ago, # |

← Rev. 2 →

+75

Fst'd C because I didn't clear the adj2(graph) in each test.Pretests are very weak

→ Reply

3 years ago, # ^ |

-8

In C's pretest the answer is always everyone wins or exactly 1 person wins.A code in my room only had these cases and it passed.

→ Reply

3 years ago, # ^ |

Were pretests generated completely randomly?I am not sure how the above linked code passed pretests

→ Reply

Jhin

3 years ago, # |

Why would that TLE in C I'm not looking at any number twice right ?

Code

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

using pi =pair<int,int>;

#define f first

#define s second

# define be(v) (v).begin(),(v).end()

#define eb(v)  (v).begin(),(v).end(),greater<int>()




ll t,m,n,x,y,z,k,mn=1e9,mx,ans,cnt,a[500003],b[500003],sum;



string s;

bool yes;



int main()
{

 ios_base::sync_with_stdio(false);





        cin>>t;
        while(t--)
        {
            cin>>n;
            for(int i=0;i<n;i++)
            {
                cin>>a[i];
            }
            for(int i=0;i<n;i++)
            {
                cin>>b[i];
            }
            vector<pi>mp1,mp2;
            for(int i=0;i<n;i++)
            {
                mp1.push_back({a[i],b[i]});
                mp2.push_back({b[i],a[i]});
            }
            sort(be(mp1));
            sort(be(mp2));
            set<int>wn1,wn2;
            auto it=--mp1.end();
               auto it2=--mp2.end();
                pi tmp1=*it;
                pi tmp2=*it2;
                wn1.insert(tmp2.second);
                wn2.insert(tmp1.second);
                int tmp=*wn1.begin();
                pi se={tmp,0};
                it=lower_bound(mp2.begin(),mp2.end(),se);
               for(;it!=mp2.end();it++)
               {
                   pi cur=*it;
                   wn2.insert(cur.second);
               }
               tmp=*wn2.begin();
               se={tmp,0};
               it2=lower_bound(mp1.begin(),mp1.end(),se);
               for(;it2!=mp1.end();it2++)
               {
                   pi cur=*it2;
                   wn1.insert(cur.second);
               }
                int si1=1,si2=1;
            while(1)
            {
                int olsi1=si1,olsi2=si2;
               int tmp=*wn1.begin();
               pi se={tmp,0};
                auto itt=lower_bound(mp2.begin(),mp2.end(),se);
               for(;itt!=it;itt++)
               {
                   pi cur=*itt;
                   wn2.insert(cur.second);
               }
               tmp=*wn2.begin();
               se={tmp,0};
               auto itt2=lower_bound(mp1.begin(),mp1.end(),se);
               for(;itt2!=it2;itt2++)
               {
                   pi cur=*itt2;
                   wn1.insert(cur.second);
               }
               it=itt;it2=itt2;
                si1=wn1.size(),si2=wn2.size();
                if(si1==olsi1&&si2==olsi2)break;


            }
            char anstr[n];
            for(int i=0;i<n;i++)anstr[i]='0';
            for(int i=0;i<n;i++)
            {
                auto it=wn2.lower_bound(a[i]);
                if(a[i]==*it)anstr[i]='1';
                it=wn1.lower_bound(b[i]);
                if(b[i]==*it)anstr[i]='1';
                cout<<anstr[i];
            }
            cout<<endl;


        }




    return 0;
}

→ Reply

jimm89

3 years ago, # ^ |

When using sets you appear to use (correctly) set::lower_bound, but with maps you use std::lower_bound instead of std::map::lower_bound. If you fix this does it solve your problem?

→ Reply

Jhin

3 years ago, # ^ |

← Rev. 2 →

i called them mp1,mp2 as a reference that they represent the two maps in problem C but they're vectors I should write the code clearly there're several stupid things but i didn't waste time during contest to make the code better but that's not the TLE reason though or can i use that sort on vectors ? Or you mean i should use maps I'm confused

→ Reply

_manvirag

3 years ago, # |

lots of people getting wrong on test case 21 on problem C. :( me also

→ Reply

Sigh

3 years ago, # |

-8

Ideas for problem D?

I think it might be Qpow+NTT, but 10^5 seems to be a bit big for that...

→ Reply

3 years ago, # ^ |

It's easy to see that the coloring is valid only when the number of 'BB' and 'WW' is the same,except for when there is only 'BW' and 'WB'. The first case can be calculated by using generating functions.(Hint: $$$[x^k](1+x)^n=\dbinom{n}{k}$$$ ) The second case is quite trivial, then the complexity is just $$$O(n)$$$ or $$$O(n\log n)$$$ if you calculate the reciprocal using quickpow.

→ Reply

Kofta

3 years ago, # |

Any hints for Problem D?

→ Reply

3 years ago, # ^ |

← Rev. 2 →

Spoiler

→ Reply

3 years ago, # ^ |

← Rev. 2 →

+16

Spoiler

→ Reply

3 years ago, # ^ |

Here's another one, which might contain more important spoiler.

Spoiler

→ Reply

Kofta

3 years ago, # ^ |

Sure there isn't any invalid case.

→ Reply

nexoxogoc ouhtek robot_bobot ybgbsydvh

3 years ago, # ^ |

+10

Ok That's it. I think you almost reached to the answer. Count all the cases and subtract the number of invalid cases.

→ Reply

P___

3 years ago, # ^ |

Spoiler's spoiler: Don't prove it, just submit.

→ Reply

Indians_cheating

3 years ago, # |

look at their submissions.

→ Reply

taogehtsilalos

3 years ago, # ^ |

How did you find them ?

→ Reply

yituodabian

3 years ago, # |

← Rev. 2 →

→ Reply

3 years ago, # |

-8

What is the non-convolution solution for D?

→ Reply

3 years ago, # ^ |

Well, you are convuluting terms of $$$x^a (1+x)^b$$$. It clearly becomes a single binomial coefficient.

→ Reply

3 years ago, # ^ |

← Rev. 3 →

Can you elaborate? my idea is that the number of $$$WW$$$ should equal the number of $$$BB$$$, But I think your approach is different.

→ Reply

3 years ago, # ^ |

+21

Yes that was my idea too.

We want the ogf where BB is $$$x^{-1}$$$ and WW $$$x^1$$$. So after convolution we find the coefficient of $$$x^0$$$.

Now we state the polynomials for each string (i will ignore BW and WB for obvious reasons).

BB: $$$x^{-1}$$$
WW: $$$x^1$$$
?B/B?: $$$x^{-1}+1$$$
?W/W?: $$$1+x^1$$$
??: $$$x^{-1}+2+x^1$$$

We want to multiply all these terms but actually it they are all of the form $$$x^a (1+x)^b$$$.

Now, we want to find $$$[x^0] x^a (1+x)^b$$$. But this just $$$\binom{b}{-a}$$$

→ Reply

Sigh

3 years ago, # ^ |

Aww I didn't realize (1+2x+x^2)=(1+x)^2 and was thinking to use NTT... How stupid!

Thanks for the explanation!

→ Reply

3 years ago, # ^ |

← Rev. 2 →

Why can't we use NTT

We can just convolute everything in $$$O(N \log^2 N)$$$ using NTT and it passes in half the TL (which I submitted during testing because $$$N=10^5$$$ lol). 138776423

Alternatively, we can do it in $$$O(N \log N)$$$. We convert all $$$5$$$ polynomials to their point coordinate form using NTT then do the multiplication there and do the inverse NTT. 138777576

There is an alternate way to do it in $$$O(N \log N)$$$ by taking the logarithms of the polynomial.

→ Reply

Sigh

3 years ago, # ^ |

← Rev. 3 →

+10

Yes we definitely can, and that's what I attempted during the contest.

I'm just feeling idiotic for not realizing the trivial simplification.

→ Reply

3 years ago, # ^ |

→ Reply

3 years ago, # ^ |

lol, that was my initial idea which I brushed off? good to know how idiotic I was.

→ Reply

3 years ago, # ^ |

Lovely, thanks for explaining it.

→ Reply

czhang2718

3 years ago, # ^ |

← Rev. 2 →

The necessary and sufficient condition is #[WW] = #[BB] (except for if there's none, you must have all WB or BW). If you naively assign B's and W's to ?'s so there's an equal count of each, this forces the above condition. The only invalid assignments we may have counted are sequences with only WB and BW's, and a nonzero amount of each. We can easily subtract this overcounted value.

→ Reply

Code: https://codeforces.net/contest/1608/submission/138771080

3 years ago, # ^ |

how are you going to handle strings equal to $$$??$$$.

→ Reply

insert_cool_handle

3 years ago, # ^ |

Replace $$$x$$$ by $$$x^2$$$, then it'll be $$$(1/x^2+2+x^2) = (1/x + x)^2$$$

→ Reply

czhang2718

3 years ago, # ^ |

Sorry if I wasn't clear- instead of $$$n$$$ pairs, we view it as $$$2n$$$ characters (and then adjust for the corner case).

→ Reply

insert_cool_handle

3 years ago, # ^ |

Also, you can see that the condition is equivalent to # of $$$A$$$ = # of $$$B$$$, so consider each character individually.

→ Reply

DitaMirika

3 years ago, # |

-29

Even this code could pass the pretests of C:

#include<bits/stdc++.h>
//#define int ll
#define pb push_back
#define mp make_pair
#define sec second
#define fir first
#define pii pair<int,int>
#define piii pair<int,pair<int,int> >
using namespace std;
typedef long long ll;
const int N=300005;
const int inf=1<<30;
const ll inff=1ll<<60;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}
int n,o[N];
pair<int,pii>a[N];
int main(){int tests=1;tests=read();
while(tests--){
	n=read();
	for(int i=1;i<=n;i++)a[i].fir=read();
	for(int i=1;i<=n;i++)a[i].sec.fir=read(),a[i].sec.sec=i;
	sort(a+1,a+n+1);int mx=0;
	for(int i=1;i<n;i++){
		if(a[i].sec.fir > a[n].sec.fir) mx=1;
	}
	if(mx)for(int i=1;i<=n;i++)printf("%d",1);
	else for(int i=1;i<=n;i++){
		if(i == a[n].sec.sec) printf("1");
		else putchar('0');
	} puts("");
}	return 0;
}

So crazy. I cannot understand.

→ Reply

MirioTogata

3 years ago, # |

Main Test 21 on C killed a lot of us :(

→ Reply

3 years ago, # ^ |

In fact it's the first test that the answer isn't all '1' or only one '1'.

→ Reply

T1duS

3 years ago, # |

+83

Didn't expect problems like B and E in an anton contest.

→ Reply

3 years ago, # |

← Rev. 2 →

wow I can't believe it!

→ Reply

xsap

3 years ago, # |

C is the worst problem I've ever seen.Weak sample,weak pretest and stupid problem

→ Reply

LoboLobo

3 years ago, # ^ |

← Rev. 2 →

+72

I think C is a good problem but with weak pretests

→ Reply

feecIe6418

3 years ago, # |

+23

Why is there no obvious corner cases in D's pretests?

→ Reply

minhcool

3 years ago, # |

+64

~700 system test fail on C. Nice pretests you got there.

→ Reply

3 years ago, # |

+40

C has a lot of failed system tests because of weak pretests.

This actually made me realize something. It is for sure an unpopular opinion, but I think weak pretests can be a good thing.

C is exactly the type of problem that a lot of people solve by guessing: there are a lot of feasible-looking greedy-strategies, people implement one of them without knowing whether it actually works, get AC and move on to the next problem.

Weak pretests disincentivize guessing and make contestants more careful. It puts more weight to mathematical thinking and less to just quickly implementing something that might be correct.

The bad thing is that people expect "pretests passed" to mean "accepted" and get frustrated when they fail the system test. But if weak pretests were more common, people wouldn't have such an expectation and would be more careful from the start.

→ Reply

T1duS

3 years ago, # ^ |

+40

If you value the 'proving' of solutions more, why not just increase the penalty?

→ Reply

3 years ago, # ^ |

-8

That's also an option.

However in my ideal world that I made up just now, pretests should include edge cases but not necessarily counterexamples to typical guesses. In that case:

not noticing edge cases gets a small penalty;
guessing and submitting an unproven idea gets a big penalty.

→ Reply

3 years ago, # ^ |

However the edge cases are different for different (wrong) solutions, which makes it difficult to decide which should get a small penalty.

→ Reply

3 years ago, # ^ |

Well I think in C many genuine solutions also failed.The pretests were so weak that the number of winning contestants was always 1 or n.I heard from a tester that the testcases were generated today

→ Reply

3 years ago, # ^ |

-7

How does a genuine solution fail?

Tests being generated today would certainly explain something.

→ Reply

3 years ago, # ^ |

In my solution I cleared adjacency list of original graph but missed doing that for the reverse graph and it failed.By genuine I meant correct idea of solution.my solution was to add an edge from index of the (i+1)smallest number to the index of the ith smallest number in the both the arrays.The winning set is the 1st SCC.

→ Reply

mon0pole

3 years ago, # ^ |

Well my solution was correct but only because I by mistake took sorted indices instead of original indices, it FSTed.
WA
AC
Just think how weak were pretests, that it passed with even wrong indices marked as '1' & '0'
Even a trivial test case where sorted indices and original indices didn't match should be added in the pretests (or even sample).

→ Reply

mango_lassi

3 years ago, # ^ |

+24

I very much disagree. If pretests were made weaker in problems where people just guess, people would still guess and now get FST instead of WA on pretests, which makes the results of the contest way more random and less skill-based, and the contest less fun for everyone.

I think the only way to fix this would be to require a proof of your solution in your submissions, which is obviously infeasible (but would be fun).

→ Reply

3 years ago, # ^ |

+19

If you guess wrong, you should get FST instead of WA on pretests. I guessed and got lucky to get WA on pretests, that shouldn't happen.

→ Reply

thabumi

3 years ago, # ^ |

Pretests is too weak, i sorted the array and forgot to put the answers back to those correct indexes, and that solution still passed pretests. If pretests were made to avoid guessing, it still need to be stronger to keep the genuine solution/idea AC.

→ Reply

3 years ago, # ^ |

-8

That's fair.

→ Reply

usernameson

3 years ago, # ^ |

It would also make hacking a bigger part of contests. I don't know if that is a desirable outcome. On the one hand it might make contests more interesting. On the other hand it makes your performance more dependent on the other contestants assigned to the same room.

→ Reply