Codeforces Round 921 (Div. 1 , Div. 2)

10 месяцев назад, # |

Was lazy segtree expected on E ? I got tle on pretest 32...243653603

→ Ответить

Giga_Cronos

10 месяцев назад, # ^ |

I used ABI and got 823ms. I really hope authors have a good solution, and not this ugly implementation that almost everybody did

→ Ответить

10 месяцев назад, # ^ |

My code got ac after submitting in C++ 64 bits :/

I think they have an "easier" solution that is to store the sum between each pair of harbors and handle manually the harbors on the side but I think it's less convenient

→ Ответить

TrendBattles

10 месяцев назад, # ^ |

← Rev. 2 →

I eventually used 2 lazy segment trees for E but still less than a second man (C++ 17 7.3.0)....

→ Ответить

M_bolshakov

10 месяцев назад, # |

+148

div1B is disgusting

→ Ответить

pacha2880

10 месяцев назад, # ^ |

-45

disgusting == I couldn't solve it ?

→ Ответить

M_bolshakov

10 месяцев назад, # ^ |

← Rev. 2 →

+65

no, disgusting == simple idea but solution very hard to implement correctly

→ Ответить

bigSchrodinger

10 месяцев назад, # ^ |

+42

no. idea is obvious, just implementation + data structures. nothing interesting.

→ Ответить

10 месяцев назад, # |

← Rev. 3 →

+133

Thanks for the round! Feedback on the problems:

A: Good problem, appropriate difficulty for its position.

B: Not my favorite problem (unless there's a better solution than just killing it with a segtree / a set?); all the ideas involved felt standard, but because DS was involved it still took a decent chunk of the round to implement. (Also, implementation would have been mildly less annoying if the array X was sorted; I also would have found it easier if the input was passed as (X, V) pairs and not as an array X followed by an array V.)

C: I strongly disliked this problem. It felt basically like a pattern guessing test--maybe some people had the visualization skills to solve the problem rigorously, but I basically guessed a pattern that seemed reasonable, checked that it works for small cases, and then got AC.

D: Realizing that the problem reduces to "find the number of sequences of A balanced bracket sequences with total length B" was pretty nice. The rest of the problem was damaged by the constraints in one of two ways. After thinking of smart ways to count these sequences since the mod suggested FFT was unintended, I ended up just throwing in the KACTL FFT with arbitrary modulus template, which got AC, though running somewhat close to TL (800ms, not slow enough that I was worried about FST but definitely slow enough to TLE FFT templates with bad constant factors).

I don't know whether this solution was intended or not. I suspect not because of the choice of mod, but if this was intended, then I strongly dislike the choice not to use 998244353 as the modulus, and I also don't like the TL (I would have set something like 3s if FFT/NTT was intended).

Assuming this solution was not intended, it's a tougher situation, especially if the intended solution takes O(n^2) memory or O(n^2 log n) time. If one of these is the case, I honestly might have just let FFT pass anyway (and set a more friendly modulus and TL) since I think it'd be really hard to cut FFT cleanly and the first observation is nice enough to justify the existence of the problem. If there was room, though, I would definitely have set n = 5000. As is, I think "FFT works, but you have to use a slightly unconventional template and it runs close to TL" is a very bad state for the problem.

E: Probably my favorite problem of the round (though I'm biased in favor of EV problems). Not hard enough for its position or point valuation imo.

F: Interesting problem, I had no nontrivial ideas. I think the story got in the way of the statement, and you could state the problem more formally in a shorter and more readable way. I think something to the effect of "there exists a hidden integer x from 1 to n, you can query ranges and judge will output 1 if x is in the range and 0 otherwise, judge is guaranteed not to tell the truth or lie three times in a row" would work, without all the flavor text about the students or explicitly enumerating the four cases.

→ Ответить

R2M

10 месяцев назад, # ^ |

← Rev. 14 →

-10

Will You stream solutions? How did you do C?

→ Ответить

10 месяцев назад, # ^ |

+14

I don't plan to do a stream. This solution seems likely to TLE, as with x = 1e8 and n = 1, your solution loops through 1e8 values per test case, which will TLE when t = 1000.

→ Ответить

Bipul70701

10 месяцев назад, # ^ |

-9

Bro Can you explain C

→ Ответить

10 месяцев назад, # ^ |

2C: We construct the shortest string T that is not a subsequence of S as follows. Iterate through the characters of S and maintain the list of characters we've seen so far. Once we've seen all k characters, add the last character we reached to T and reset the list of characters we've seen. Once we finish going through S, add any character we haven't seen yet to T. Any shorter string can be found in S (we can find the first character of such a string in S before the first character of T, the second character of the string before the second character of T, and so on); I'll leave it as a (simple) exercise to prove that T cannot be found in S.

If T has length at most n, add additional characters until it has length n and output it as our answer. Otherwise, no answer exists.

→ Ответить

10 месяцев назад, # ^ |

During contest I submitted this just as a pure guesswork, totally no clue why we should add last char from each T. Now after some thinking it's a becoming slightly more evident, but still very vague. Something like if it wasn't the last char that is missing, then it should've finished T earlier.

→ Ответить

AvaraKedavra

10 месяцев назад, # ^ |

Thanks for the explanation. Very helpful.

→ Ответить

Andyvanh1

10 месяцев назад, # ^ |

+10

I think D might just be https://en.wikipedia.org/wiki/Catalan%27s_triangle. I just checked some smaller cases and didn't prove though.

→ Ответить

10 месяцев назад, # ^ |

← Rev. 2 →

+20

Hi, Thanks for the feedback!

Intended soln of D :)

int fun(int n, int m,int k){
      if(k >= max(n, m))return C(n+m,m);
      return C(n+m,k);
}
void solve() {
        ll n,m,k;cin>>n>>m>>k;
        cout<<fun(n,m,k)-fun(n,m,k-1);
}
// C(n, r) is no. of ways to choose r objects from n distinct objects.

→ Ответить

10 месяцев назад, # ^ |

+13

Nice, figured there was likely something like that :) In this case, I would have just set n, m up to 1e6, which clearly passes your solution but fails FFT and other such nonsense.

→ Ответить

10 месяцев назад, # ^ |

+43

Yeah, it was a trade-off we did to make the solution less guessable. I initially proposed it as div2D but the testers feedback made us feel that it's harder.

→ Ответить

HexShift

10 месяцев назад, # ^ |

the only good thing about D2F/D1C is the fact that you can play with origami paper while solving it :D (still, definitely an annoying problem lol)

→ Ответить

JaySharma1048576

10 месяцев назад, # ^ |

← Rev. 2 →

+23

The model solution of Div. 1F does require some non-trivial ideas. I will release the detailed editorial shortly but till then, here is one of the ideas that you may have missed.

Hint

Thanks for the feedback. From next time, I will try to keep the statement concise.

→ Ответить

10 месяцев назад, # ^ |

Thanks for sharing! I'll give it a bit more thought :)

→ Ответить

Benq

10 месяцев назад, # ^ |

← Rev. 4 →

+15

Improving Number of Queries

→ Ответить

Fork512Hz

10 месяцев назад, # ^ |

← Rev. 2 →

On Div2D I figured out the correct fraction quickly but wasted the second half of the contest on figuring out WHAT IS A FRACTION MODULO 1e9+7. Also on trying __int128 or Python, because the unreduced denominator can reach 10^20 and goes beyond the long long limit. Could you please tell if this is avoidable?

→ Ответить

10 месяцев назад, # ^ |

← Rev. 2 →

+10

Store all numbers $$$p/q$$$ in the form $$$p \cdot q^{-1}$$$ mod 10^9 + 7. It can be shown that addition, subtraction, multiplication, and division (where $$$a / b$$$ is computed as $$$ab^{-1}$$$) all work normally under this representation of fractions. Since all numbers are less than 10^9 + 7, the arithmetic operations can be performed using long longs.

→ Ответить

Fork512Hz

10 месяцев назад, # ^ |

Thank you for the clarification!

→ Ответить

ko_osaga

10 месяцев назад, # ^ |

+26

I googled this explicit formula for the convolution of Catalan numbers: https://codeforces.net/blog/entry/87585

→ Ответить

Giga_Cronos

10 месяцев назад, # ^ |

+13

I have a solution for C, based on capes of paper, once you fold the paper once there are the same number of capes upward and downward(this mean that all steps before that increments both values equally) so you have V=M + 2*sqrt(2). So in every steps the number of capes get multiplied by two, while the perimiter of the square is multiplied by 1/sqrt(2) then you have a geometric progression.

→ Ответить

07nikhilraj

10 месяцев назад, # |

Too curious to know where I failed on C. T_T

→ Ответить

CallmeSourav

10 месяцев назад, # ^ |

m v bhai, curious and angry at same time

→ Ответить

10 месяцев назад, # ^ |

abcccabab ?

→ Ответить

CallmeSourav

10 месяцев назад, # ^ |

how did you came across this test case ?

→ Ответить

10 месяцев назад, # ^ |

By solving Div2A

→ Ответить

tinca_matei

10 месяцев назад, # |

For d1C, was anyone able to reproduce N = 7 irl? The most I could get is N = 4.

→ Ответить

bananasaur

10 месяцев назад, # ^ |

You might find this interesting: https://www.wtamu.edu/~cbaird/sq/2012/12/07/what-stops-a-piece-of-paper-from-being-folded-more-than-seven-times/

Paper gets hard to fold very fast due to the thickness exponentially growing.

→ Ответить

rohitsatpute480

10 месяцев назад, # |

Was submitting C in last 30 seconds, but Checking if the site connection is secure take a minute

→ Ответить

wyrqwq

10 месяцев назад, # |

← Rev. 4 →

+158

Is it the problem setter of d1B in a loss of loved ones that he doesn't even guarantee $$$x_i$$$ is in an ascending order but doesn't even show it in the sample either?

btw, i don't understand what the data range is for for d1D.

→ Ответить

leshless

10 месяцев назад, # |

← Rev. 3 →

How the hell to mod a rational number? I've managed to get a working solution for d, getting nominator and denominator, but i still don't have an idea how to convert them into valid answer...

→ Ответить

aviralarpan3301

10 месяцев назад, # ^ |

check this

→ Ответить

leshless

10 месяцев назад, # ^ |

← Rev. 2 →

Damn, I shoud've learn this earlier... Thanks.

→ Ответить

Termii

10 месяцев назад, # ^ |

took me 20min to find the solution exactly there. For those still confused:

fraction: 1 / 7
numerator: 1
denominator: 7

typedef long long ll;
const ll mod = 1e9+7;
ll inv(ll a) {return a <= 1 ? a : mod - (ll)(mod/a) * inv(mod % a) % mod;}

void solve(ll numerator, ll denominator){
    cout << (inv(denominator)%mod * (numerator%mod))%mod << "\n";
}

→ Ответить

10 месяцев назад, # ^ |

For me it took 20 minutes just to read the problem statement.

→ Ответить

Caffeinus

10 месяцев назад, # ^ |

when p is a prime number, inv(a) can be calculated by a^(p — 2) mod p. (^ means power, not bitwise xor)

→ Ответить

pb_messi

10 месяцев назад, # ^ |

Link

→ Ответить

AR69420

10 месяцев назад, # |

← Rev. 2 →

Div2D was so nice.

For every excursion, our answer increases by (total sum of friendship values)/(# of pairs) on average, and the total sum of friendship values increases by (# of non-zero friendship values)/(# of pairs) on average.

This hand-wavy "average" logic works because of the linearity of expectation.

→ Ответить

10 месяцев назад, # ^ |

+10

I find it hard to call problem nice when 60% of input is not even used.

→ Ответить

nonrice

10 месяцев назад, # ^ |

I suppose writers originally had this as a much harder problem, then realize they need something for d2d, so they just go fkk it and repurpose it without removing the now reduntant part

If you consider the problem without the useless information it's not bad.

→ Ответить

10 месяцев назад, # ^ |

Agree, overall it's a nice intro to modular arithmetic

→ Ответить

liyishui_2003

10 месяцев назад, # ^ |

Can you please show me your code?

→ Ответить

Ormlis

10 месяцев назад, # |

+79

mathforces...

→ Ответить

hxu10

10 месяцев назад, # |

+18

Anyone thought the position of harbour in div1B/div2E is sorted and keep getting WA at pretest 5?

→ Ответить

tickbird

10 месяцев назад, # |

couldn't solve Div2C(Div1A) in 100 minutes

I'm such a brainlet

→ Ответить

OgataShumaHiroyuki

10 месяцев назад, # |

why does binary search not work in B?

→ Ответить

devansh_27

10 месяцев назад, # ^ |

it'll work, first stores all the divisors in array , then sort it , now find out that what can be the average difficulty for each sub problem , now we know that our max difficulty won't exceed this average, so use lower_bound on the array of divisors

→ Ответить

HliasBoss

10 месяцев назад, # |

C was definitely one of the problems ever.

→ Ответить

arash.

10 месяцев назад, # |

+11

Too much implementation for a div1 B ...

→ Ответить

AvaraKedavra

10 месяцев назад, # |

← Rev. 2 →

My rating gonna drop due to C. Fuck C

→ Ответить

robertlewantest

10 месяцев назад, # |

C anyone?

→ Ответить

10 месяцев назад, # ^ |

I think the point was to check for all intervals of length n if every one of the k letters are in it, if not then the answer is no. Again I'm not sure but if that premise is right you can easily think of a way to construct a string that is not possible.

→ Ответить

TheNameMeansBlue

10 месяцев назад, # ^ |

I thought of that too but there's some flaw in the logic. Take for instance the case when the string's length is greater than n * k. This gives you some 'buffer' characters to play around with, which means that the interval of length n may not necessarily hold all the characters.

→ Ответить

https://codeforces.net/blog/entry/125112?#comment-1110782

10 месяцев назад, # ^ |

Yeah, you're right

→ Ответить

Rakesh_898

10 месяцев назад, # ^ |

1 3 3 11 aabbccabac

test case where you can fail.

→ Ответить

D3VPAND3Y

10 месяцев назад, # ^ |

void solve() {
    int n,k,m;
    cin>>n>>k>>m;
    string S;
    cin>>S;
    vector<int> count(k,0);
    map<char,vector<int>> mpp;
    for(int i=0;i<m;i++){
        count[S[i]-'a']++;
        mpp[S[i]].pb(i);
    }
    string ans="";
    for(int itr=0;itr<k;itr++){
        if(count[itr]<n){
            char ch = itr+'a';
            for(int i=0;i<n;i++){
                ans+=ch;
            }
            cout<<"NO"<<endl;
            cout<<ans<<endl;
            return;
        }
    }
    for(int itr=0;itr<k;itr++){
        char ch = itr+'a';
        vector<int> v = mpp[ch];
        for(int i=n-1;i>=1;i--){
            int index = v[i-1];
            int occurence = n-i;
            string ans="";
            map<char,int> temp;
            for(int j=index;j<m;j++){
                temp[S[j]]++;
            }
            for(int p=0;p<k;p++){
                char check = 'a'+p;
                if(check==ch){
                    continue;
                }
                if(temp[check]<occurence){
                    cout<<"NO"<<endl;
                    for(int hehe=0;hehe<i;hehe++){
                        ans+=ch;
                    }
                    for(int hehe=0;hehe<occurence;hehe++){
                        ans+=check;
                    }
                    cout<<ans<<endl;
                    return;
                }
            }
        }
    }
    cout<<"YES"<<endl;
}

Can you tell where does this code fail??

→ Ответить

Rakesh_898

10 месяцев назад, # ^ |

1 3 3 11

aabbcccabba

→ Ответить

balalaika

10 месяцев назад, # ^ |

← Rev. 2 →

Straight DP:

Find first position of all k letters. It would base for len = 1.
Then for each i = 2..n you must have all k letters after all k letters positions for i - 1. If you keep it properly with reverse link, then construct answer should be easy.

→ Ответить

Astroflexx

10 месяцев назад, # ^ |

→ Ответить

10 месяцев назад, # |

+66

WTF I didn't submit 1D just because of this 'Just a moment' thing!!!

→ Ответить

10 месяцев назад, # ^ |

+46

How can I get rid of it?

→ Ответить

iiand

10 месяцев назад, # |

← Rev. 2 →

Task C is a very funny task. 10 sheets were damaged

→ Ответить

Igor_Parfenov

10 месяцев назад, # |

I tried to solve problem B using segment tree. But I couldn't do it in integers, because I was required to combine several multiplications; and I couldn't also pass it using floats. How to pass segment tree?

→ Ответить

10 месяцев назад, # ^ |

I used Segment Tree and I passed. You store the answer of each position, and operation 1 is range equal to zero and range add an Arithmetic sequence.

→ Ответить

10 месяцев назад, # ^ |

My code

→ Ответить

Igor_Parfenov

10 месяцев назад, # ^ |

Ough, I did other quieries. When I'm adding a harbour $$$p$$$, there are closest to the left harbour $$$l$$$, and closest to the right $$$r$$$. Then I add to segment $$$[x_{l+1}, x_{p-1}]$$$ value $$$-(x_{r}-x_{p})*v_{l}$$$ and multiply to segment $$$[x_{p+1}, x_{r-1}]$$$ value $$$\frac{v_{p}}{v_{l}}$$$

→ Ответить

pacha2880

10 месяцев назад, # ^ |

I used lazy segment tree, but instead of multiplying when pushing y just maintained a vector of push's, bit it gave WA on test 8 :(

→ Ответить

liyishui_2003

10 месяцев назад, # |

how D?

→ Ответить

scorfield

10 месяцев назад, # |

That C..

→ Ответить

__NO__NAME__

10 месяцев назад, # |

why am i so dumb

→ Ответить

beyondpluto

10 месяцев назад, # |

+11

I felt statement of Div2D to be ambiguous and misunderstood several times. I initially thought once a pair is picked, then its value keep on increasing by one for every next excursion irrespective of what pair is chosen next.

→ Ответить

kne3lb4m3

10 месяцев назад, # ^ |

Exactly I wasted a lot of time figuring out the logic for the misunderstood problem, they could have atleast explained a normal test case.

→ Ответить

10 месяцев назад, # |

← Rev. 3 →

I was so close to solving Div2C or at least I hope I was T.T

Edit: nope, not even close

→ Ответить

AJAY9

10 месяцев назад, # |

too much server problem, but overall good contest and good questions.

→ Ответить

longqt321

10 месяцев назад, # |

Hope I will become green this contest.

→ Ответить

hos.lyric

10 месяцев назад, # |

+85

I somehow liked Div1C and Div1E, disliked Div1B, but anyway: Please polish the problem statement before the round (Div1B: "next harbour" concept is strange, Div1D&Div1E: two variables are interchanged, etc.) and please check it carefully for the clarification (I got two wrong responses in this round...).

→ Ответить

10 месяцев назад, # ^ |

+26

Sorry about that, will take extra care in future.

→ Ответить

Sert

10 месяцев назад, # ^ |

Maybe consider sacrificing some pieces of paper in favor of making round even more ideal? :-)

→ Ответить

Md-Merazul-Islam

10 месяцев назад, # |

← Rev. 2 →

+11

I solved 3 problems, I am enjoyed this contest. Thank You

→ Ответить

ANTH4RAX

10 месяцев назад, # |

i was so exited to participate since this is my first contest lmao , until i spent all the time in the first problem and couldnt solve it lmao , any tips so i can improve ??

→ Ответить

Omkar2003

10 месяцев назад, # |

Can we use binary search to solve Div2 B ? i was trying it at first but i didn't understood where its failing here is my submission 243579415, then i just used linear approach.

→ Ответить

longqt321

10 месяцев назад, # ^ |

I don't think binary search could solve Div2B. Because if K is the answer so every number that smaller than K should be all satisfied. However, if x = 10, n = 2 then all subsets we have are 1-9, 2-8, 3-7, 4-6, 5-5 => gcd of them are 1,2,1,2,5 respectively. So there is no way to split 10 into 2 numbers that have gcd equal to 3 or 4.

→ Ответить

Omkar2003

10 месяцев назад, # ^ |

← Rev. 2 →

Thanks man ,I'm an idiot who forgot how binary search works

→ Ответить

why_needed

10 месяцев назад, # |

why CF doesn't let us submit code to check after contest ends :( Just missed submitting E by few seconds and now waiting to see if my solution is correct. Pretty frustrating to wait more.

→ Ответить

10 месяцев назад, # ^ |

It's because of system testing

→ Ответить

why_needed

10 месяцев назад, # ^ |

They aren't even started yet... :(

→ Ответить

mahendraakshansh

10 месяцев назад, # |

I had fun in this contest. The D reminded me of JEE days. Thank you for fun contest.

→ Ответить

digestra

10 месяцев назад, # |

what is wrong in my solution for question C. My Submission

what I was doing to divide string s into a complete chunk of k alphabets and if someone is missing in last chunk I take this character to form a valid subsequence not present in s.

→ Ответить

laala

10 месяцев назад, # ^ |

counter_eg: 2 3 6 aabcbc

→ Ответить

10 месяцев назад, # ^ |

Why is it counter to the described idea?

2 chunks: aabc bc

a is missing in last one, so ca is final answer.

I submitted exactly the same idea and it passed pre-tests.

→ Ответить

laala

10 месяцев назад, # ^ |

consider 3 chunks and according to your approach, it will give NO, and output "aa" but "aa" is present in the string

→ Ответить

10 месяцев назад, # ^ |

I've posted the link to my submission, hack it if you are sure about your counter. To me it seems you misunderstood the proposed idea

→ Ответить

laala

10 месяцев назад, # ^ |

You can check the above submission, you will get your answer.

→ Ответить

comingsoon.cpp

10 месяцев назад, # |

← Rev. 2 →

+24

Cloudflare is horrible

→ Ответить

joi_

10 месяцев назад, # |

div2B O(n^0.5) with n = 1e8 timed out in python :(

→ Ответить

longqt321

10 месяцев назад, # |

+17

What is "orz" btw?, I saw some people saying that?

→ Ответить

subcrip

10 месяцев назад, # ^ |

+10

this

→ Ответить

TosakaUCW

10 месяцев назад, # |

Waiting for tutorial :)

How to know when it will be released?

→ Ответить

the_coder_8297

10 месяцев назад, # |

The test cases are very weak for Problem Div2 B. some solution of complexity 1e10 also passed

→ Ответить

SuperMo

10 месяцев назад, # ^ |

yes my solution passed with the same problem I'm sure it will TLE now I should have iterated till sqrt(x)

→ Ответить

Sert

10 месяцев назад, # |

+28

Lol, spent last 33 minutes of the round debugging Div.1B, only to understand after the round that coordinates are not guaranteed to be sorted.

In my opinion, such problems problems should contain coordinates already in adequate order.

Div.1B/Div2.D should check participant's ability to invent and implement solution, not ability to carefully read problem statement...

Otherwise, problem is quite nice

→ Ответить

MridulAhi

10 месяцев назад, # ^ |

+11

wtf i spent 90 mins on B and still didn't figure this out :ded:

→ Ответить

plAtEaUpUs

10 месяцев назад, # ^ |

Happened to me as well. Noticed after the contest (;-;) hurts

→ Ответить

Vampire

10 месяцев назад, # |

← Rev. 2 →

-8

Weak pretests on B, need n = 1 case

C is the opposite, yet another brutal pretest

→ Ответить

brave-kid

10 месяцев назад, # |

← Rev. 2 →

speed forces yet bricked

→ Ответить

henshin

10 месяцев назад, # |

DM, how to solve C of div 2?

→ Ответить

Arijit15

10 месяцев назад, # ^ |

u just need to count the number of times all the alpha occurs

→ Ответить

Arijit15

10 месяцев назад, # |

← Rev. 3 →

-8

sry for the misconception i realised the error but how can i del this comment

→ Ответить

agentORW

10 месяцев назад, # |

Welp... i did 1 problem at least. I didnt know that the contest was delayed by 10 mins, so I was confused and thought it was starting on the end time. I ended up starting like 1 hour into the contest, and did problem A at least. A lot learned! Hoping to be at the next competition as well

→ Ответить

nor

10 месяцев назад, # |

+61

I might be risking losing all my testing privileges here, but I would like to point out that div1A (or div2C), as well as div2A, were pointed out by me during testing to be very close to a certain CSES problem. According to the judgment of the coordinator, "D2A can be not really new," so I kind of assumed they'd be removing the div2C (it was A2 earlier) but not the div2A (which was A1).

My question is — is this expected by contestants? My perception is that it is not, and I feel there should definitely be some more originality in problems that are supposed to be around D2C in difficulty (D2A being unoriginal is probably arguable, so I won't comment on that).

→ Ответить

rolandpetrean

10 месяцев назад, # ^ |

This problemsetting trick is also well known in Romania.

→ Ответить

brave-kid

10 месяцев назад, # ^ |

-12

I don't think they are very close

→ Ответить

SuperMo

10 месяцев назад, # ^ |

-9

I think this is a good thing for newbies like me

→ Ответить

ScarletS

10 месяцев назад, # ^ |

Meh, I think it's different enough.

→ Ответить

nor

10 месяцев назад, # ^ |

+19

It took me changing only a couple of lines in my submission to the CSES problem, so it was pretty similar for me.

→ Ответить

Astroflexx

10 месяцев назад, # |

-18

Really good contest! Very nice and fun to solve these problems. Thanks for the round JaySharma1048576 mexomerf yash_daga and all testers!

Solution for Div2C (if anyone needs):

-> After solving Div2A, you can see that to get all possible strings of length n using first k characters, the string s should have n groups of the first k characters.

Eg: if n = 5, k = 3 (a, b, c) then s = "abc abc abc abc abc"

-> so in the given string s, traverse from left to right and form such groups of first k characters and find how many such groups you can make (call it cnt)

-> if cnt >= n, ans is YES

-> else, take the last character of each group and combine it with the missing character of the missing group, this newly formed string will definitely not be a subsequence of s, because theres only one such character in each group and we combine it with the missing character.

Eg: if s = "aabbccabab":

the groups are "abc" "cab" "ab"

so taking last character of every group and missing character, we get "cbc" which is the answer

Submission for reference

→ Ответить

digestra

10 месяцев назад, # ^ |

← Rev. 3 →

Hey can you explain the intuition more clearly about this line "because theres only one such character in each group and we combine it with the missing character."

what I can get from solution is that since we are making blocks as soon as we get first entry of last remaining element that element will always be single. So it is deemed to be remain unique in pattern as opposed to elements who are repeating more than one time.

also I am thinking that any single element will also be sufficient for concatenating answer but for sake of simplicity we taking last element which automatically will be single because after that we are terminating that block.

→ Ответить

AVdovin

10 месяцев назад, # |

← Rev. 4 →

+12

A: It is easy to find out, that size of our answer is $$$nk$$$ (at least because it must contain all $$$aa...aa$$$, $$$bb...bb$$$, etc). So, we can just break our answer into $$$n$$$ blocks of length $$$k$$$. Each block will contain all first $$$k$$$ letters of the alphabet. So, our answer is $$$"abc...$$$($$$k$$$-th letter) $$$"$$$ repeated $$$n$$$ times. $$$O(nk)$$$ per test.

B: Basically, we need to find such array $$$a$$$, that $$$a_1 + a_2 + ... + a_n = x$$$ and $$$gcd(a_1, a_2, ..., a_n)$$$ is maximum ($$$a_i > 0$$$). If $$$gcd(a_1, a_2, ..., a_n)$$$ is equal to some $$$k$$$, that means, that each $$$a_i$$$ can be represented as $$$k * \frac{a_i}{k}$$$, so our sum will be $$$k * (\frac{a_1}{k} + \frac{a_2}{k} + ... + \frac{a_n}{k}) = x$$$. From here we can see, that $$$k$$$ will be divisor of $$$x$$$, so we can iterate over all divisor of $$$x$$$ (let it be $$$d$$$) and check if $$$\frac{x}{d} \ge n$$$, as we want to make each $$$a_i > 0$$$. $$$O(\sqrt{x})$$$ per test.

C: We can do a greedy approach to find such string, that doesn't occur as a subsequence. The algorithm is basically the same as when we solve "Does string $$$t$$$ occurs in $$$s$$$ as subsequence?", but we want to shift our pointer as further as possible. So, we will pick the furthest first occurrence of some letter starting from our current position, after that we will shift our position to the right of that picked one and remember letter on chosen position. If we didn't lack any letter during $$$k$$$ iterations answer is $$$YES$$$, otherwise we can construct answer as follows: we write remembered letters one by one, after that we add letter, that we lack and until size of our answer $$$< k$$$ we will add letter $$$a$$$ to the end of it. $$$O(nk)$$$ per test.

P.S: Funny, that C is a checker for A.

→ Ответить

Fork512Hz

10 месяцев назад, # |

After solving D2A D2B I thought D2D would be easy and got the right answer within O(1), but THIS IS THE FIRST TIME I come across fraction representation like "Calculate p⋅q^−1 mod(10^9+7)" and didn't know how. Also the unreduced denominator can be n^4 which is 10^20 and goes beyond the long long limit. That left me stuck trying python or __int128

→ Ответить

arvindf232

10 месяцев назад, # |

+38

Problem E basically have the same solution with this atcoder problem ARC114E.

Atcoder

Though it seems this did not affect the standings, as I did not found many others solving this lightning fast. (Not that this particularly affected me as I solved this problem pretty quickly when practicing)

→ Ответить

10 месяцев назад, # ^ |

+23

Hi, I thought of the problem after solving the atcoder one and mentioned in the round proposal that my problem is inspired from this one.

According to me, my solution is very different from the solution of that problem. Only the concept of linearity of expectation is common.

→ Ответить

arvindf232

10 месяцев назад, # ^ |

← Rev. 2 →

To me, there are two key components of the solutions, aside from linearity of expectation.

Solution

With these two key concepts the rest of solution should be basic calculations.

But by far, the first part is hardest one and take the longest to come up with. Unless the intended solution is very far from what I described then I can see your reasonings.

→ Ответить

10 месяцев назад, # ^ |

+15

Yeah my solution is slightly ugly and doesn't use the first concept mentioned by you.

Informal solution

Basic Concept Needed: Expected number of cuts for any case is the same as the sum of probabilities of being cut for every line.

First we handle the cases where we complete our objective with the help of only one type of cut(horizontal or vertical).

1)i)Only Vertical Cuts:

Let the largest integer y for which (n*y)<k be reqv. The probability of achieving the goal using only vertical cuts is (reqv/(reqv+n-1)) since one of the reqv lines needs to be cut before all the horizontal lines. Now we will multiply this with the sum of conditional probabilities for each of the vertical line. Sum of conditional probabilities of being cut for all lines from 1 to reqv is exactly 1, since for area to be smaller than k one of them needs to be cut and as soon as one is cut the area becomes less than k so no further cuts are required. Now for the lines from reqv+1 to m-1 their conditional probabilities will form the following harmonic progression:

1/(n+reqv) + 1/(n+reqv+1) + .... + 1/(n+m-2)

This is due to the fact that for a line to be cut it needs to come before all horizontal lines and all vertical lines smaller than it.

1)ii)Case with only horizontal cuts can be handled similarly.

2)i)Case when the overall last cut is a horizontal one and there is at least one vertical cut:

For this we iterate over the last cut among all the vertical cuts. Let the last vertical cut be x. We now find the largest y such that (y*x)<k. Let this value be reqh. The objective can be achieved using this case if the vertical line x comes before all the horizontal lines from 1 to reqh and all the vertical lines from 1 to x-1, and after that any one of the horizontal line from 1 to reqh comes before all the vertical lines from 1 to x-1. The probability of this happening is (1/(x+reqh))*(reqh/(reqh+x-1)).

Now we just add the the conditional probabilities of being cut for every line and multiply this with the above probability to find the contribution of this case to the final answer

2)i)a)Firstly the conditional probability of the vertical line x being cut is 1. 2)i)b)The sum of conditional probabilities for horizontal lines 1 to reqh is also 1.

The order of the first x vertical cuts and the first reqh horizontal cuts for the given case would look like:

x_v, y1_h, ((x-1) vertical lines and (reqh-1) horizontal lines in any relative ordering) [Total x+reqh elements in the sequence] x_v denotes the x-th vertical cut y1_h denotes the horizontal cut which comes first among all the first reqh horizontal cuts.

2)i)c)Vertical cuts from x+1 to m-1: For the (x+1)-th cut we can look at this like it needs to come before the x-th vertical cut (or it has one gap in the sequence to choose from a total of (x+reqh+1) gaps) So the probability is 1/(x+reqh+1) For the (x+2)-th cut we can first place the (x+2)-th cut with probability 1/(x+reqh+1) now we need to place the (x+1)-th cut after of this which will happen with the probability of (x+reqh+1)/(x+reqh+2) So the overall probability is the product ie. 1/(x+reqh+2) Similarly, the probability for (x+i)-th cut is 1/(x+reqh+i)

The sum of this HP can be computed in O(1) using pre computation.

2)i)d)Horizontal cuts from reqh+1 to n-1 (Trickiest Case imo) Let us see the case for the (reqh+1)-th cut -> It has 2 optimal gaps (before x_v and the gap between x_v and y1_h) so the probability is 2/(x+reqh+1)

Now for finding the probability for (reqh+i)-th cut we first place this cut into one of the 2 gaps and handle both cases separately.

Gap before x_v: this case is similar to 2)i)c) and the answer is just 1/(x+reqh+i)

Gap between x_v and y1_h Here we again have to ensure that all lines from reqh+1 to reqh+i-1 come after reqh+i so we multiply (reqh+x)/(reqh+x+2) * (reqs+x+1)/(reqh+x+3).... since after we place the (reqh+i)-th cut we have (reqh+x) good gaps among a total of (reqh+x+2) and so on for all the other lines we place (Their relative ordering does not matter since we are only concerned with (reqh+i)-th cut) The final term for (reqh+i)-th cut comes out to be: ((x+reqh)/((x+reqh+i)*(x+reqh+i-1)) This forms a quadratic HP the sum of which can be computed in O(1) using precomputation.

2)ii)Case when the overall last cut is a vertical one and there is at least one horizontal cut:

This case can be handled in a similar way as the previous case.

O((n+m)log(n+m)) Code: https://ideone.com/V2vGBp

→ Ответить

yael97

10 месяцев назад, # |

div2D was one of the easiest problems I've aeen in a while, and yet i spent four tries, first because i summed without modulo, then because i divided by 2 and not multiplied by 2^-1. i should really get a modulo template

→ Ответить

majdoor

10 месяцев назад, # ^ |

what was your approach for div2 D?

→ Ответить

yael97

10 месяцев назад, # ^ |

well the base expected value is just sum(f_i)/(n choose 2), and then there is exactly m/(n choose 2) probability to add 1, so in expectation it adds 1 * m/(n choose 2), and that's true for all the stages, and it carries over to the rest. so it's ((k-1) + (k-2) + ... + 1) times that m/(n choose 2).

→ Ответить

10 месяцев назад, # |

← Rev. 2 →

Here is my advice about the problems (Div 2):

Anyway, kudos to the authors of the round, it was still an overall good contest

→ Ответить

619

10 месяцев назад, # ^ |

Implementation of C felt easy to me, you can check my solution, My logic was to check if i can make n or more continuous substrings of the strings or not with every substring satisfying the condition that it contains all the characters from 'a' to 'a'+ k at least once

→ Ответить