AlFlen's blog

By AlFlen, history, 9 months ago, translation, In English

1393A - Rainbow Dash, Fluttershy and Chess Coloring

Idea: AlFlen

Tutorial
Solution (74TrAkToR)

1393B - Applejack and Storages

Idea: 74TrAkToR

Tutorial
Solution (74TrAkToR)

1393C - Pinkie Pie Eats Patty-cakes

Idea: 74TrAkToR и lapochka_queen

Tutorial
Solution (AlFlen)

1393D - Rarity and New Dress

Idea: 74TrAkToR

Tutorial
Solution (74TrAkToR)

1393E2 - Twilight and Ancient Scroll (harder version)

Idea: AlFlen

Tutorial
Solution (74TrAkToR)
 
 
 
 
  • Vote: I like it
  • -80
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it +64 Vote: I do not like it

Here is my unofficial editorial for A-D:

https://codeforces.com/blog/entry/81216

»
9 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Here are editorials for A-D in video format if anyone prefers that over text (sorry, no E, I'm not good enough to solve it): https://www.youtube.com/watch?v=oBYxcIjfoGM. Solution timestamps are in the description.

»
9 months ago, # |
Rev. 2   Vote: I like it +142 Vote: I do not like it

hate people that think if the contest was hard for them then it is bad I think that it was a nice contest. Thanks to the authors and testers. maybe just E1-E2 problem was a little bit hard for div 2

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Definitely. The problems were hard but interesting and I really enjoyed upsolving. Perhaps the editorial should have been uploaded earlier, but the contest itself was enjoyable.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +45 Vote: I do not like it

    Idk, a lot of people mainly got mad because reading the long problem statements was headache inducing.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Except that statements weren't that long

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Long is relative, they were definitely longer than they needed to be.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Though the editorial is late,it's an interesting contest.

»
9 months ago, # |
  Vote: I like it +101 Vote: I do not like it

![ ](WhatsApp-Image-2020-08-09-at-5.21.34-AM.jpg)

»
9 months ago, # |
  Vote: I like it +18 Vote: I do not like it

If you can read Chinese,I'd to recommend my blog

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why the answer is 3 when the $$$n$$$ is 4.

I think the answer is 2.

»
9 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Where am I......is this atcoder?

»
9 months ago, # |
  Vote: I like it +227 Vote: I do not like it

Why do so many people dislike editorial? If this is due to a delay in editorial, then we are just waiting for a good translation into English to make it clearer for you. I think we need to support AlFlen, as she tried a lot for the round and now she can get upset. This is our 1st round. Next time, we will pay attention to all the mistakes made in this round and make the round even better!

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    I think the round was great and hope to have more rounds of you guys, thanks!!!

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    I think, the problems were really good and interesting. I think ,many of us definitely have learnt something while solving the problems. But also, the problem statements were too lengthy and the delay of publishing the english editorial have disappointed the contestants.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    I hope this comment of mine makes you two feel better, since this is the only reason I'm writing the comment.

    In my opinion, the round was amazing (maybe not amazing but quite nice). Unfortunately, I should agree that problem statements were a bit long. I believe you can shorten them in the next round(s).

    I don't know whether the problem D was diverse or not but I loved the question. I brainstormed for quite long time and finally figured out one solution. It made me feel amazing and I learned a lot from the question.

    I don't think the reason why people are downvoting the editorial is the delay. Delay is understandable as its reason is clearly stated. The contest announcement was downvoted as well after the contest, because the upvotes were way higher before the contest, if I remember correct. The downvotes might be from the same people. Honestly, this hatred makes no sense.

    Please be aware of us: the people that loved both your contest and you two.

    We wish you good luck on your next preparations! (And stay safe)

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I'll hope to learn more when the editorial comes out, though as among lot of people,I didn't like sentence framing a little as it got confusing.(Little Understandable if I guess it isn't your first language either) But would look forward to your next round . Def it'll get more support with few corrections. I'm trying to get better at dp and 4th was a good exercise. Thanks. :)

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    its because pupils and newbies have no brains

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +15 Vote: I do not like it

    You kind of missed the deadline. People complained about the problemstatements and then had to wait for the tutorial. Downvotes is what you get if you upset people.

    Downvotes is not a quality measurement, it is a measurement of emotions.

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Unofficial Editorial for A in English, complete beginner friendly:Explaination

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

If the language of problems were formal and short than this round would have been great. BTW Thanks for the editorials.

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can Anyone explain me the "DFS and similar" way of solving Problem D?

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    The way I did it is mostly dp but use bfs to calculate.

    Let $$$dp[i][j]$$$ be the number of possible desired square that centered at $$$(i,j)$$$. It’s obvious that $$$dp[i][j] = min(dp[i-1][j],dp[i+1][j],dp[i][j-1],dp[i][j+1])+ 1$$$ as long as those four around is the same alphabet with the center. To calculate this, I simply find all square which $$$dp[i][j] = 1$$$ (which is easy to find) and use BFS from those square to calculate dp for all squares.

»
9 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Come on guys, the editorial is admittedly pretty late (and still incomplete) but that's not really a reason to downvote the blog to hell. I'm sure the authors are working hard to get it out. Although, I am still curious to why translating is taking a long time.

If it has to do with problem quality, I don't even know where to start. People can find something bad in everything.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    We entrusted the translation to more experienced people and now we are waiting for it to be ready

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Some One Plz Help Figure, What Could Have Been The Problem With Rectangular Field In The First Question

»
9 months ago, # |
Rev. 3   Vote: I like it +78 Vote: I do not like it

EDIT: Now, they have updated the English version.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally here!

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What will be the O(n) solution of C problem

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm not sure if the O(n) really existed. Personally I don't think O(n) exist in this one, except assuming Radix Sort is O(n) (which tbh, hell, why would you write radix anyway when you have std::sort that still pass the test)

    But for O(nlogn) there're some slight ideas I can give to you.

    First, you hash the amount of each type (2,2,1,3,1,4,4,2,4,5,6) will be A[1] = 2, A[2] = 3, A[3] = 1, A[4] = 3,...) (O(n))

    Then sort it (2,3,1,3,1,1) --> (1,1,1,2,3,3) O(nlogn)

    Max is 3. Amount of max(AmountMax) is 2.

    The idea of the calculation is that you put the type that has the maximum amount (in this case, 2 and 4) alternately first.

    --> 2,4,__,2,4,__,2,4 :: Distance from this will be Max-1.

    Then, you put the rest( in this case, 1,3,5,6) in the space between these 2,4 sets to increase the distance. Distance from this will be (Amount of non-max number (or 1+1+1+2=5) divided by amount of space (which is Max-1))

    So, the distance can be calculated in O(n).

    In case you want to see the real code, I have one in my submission. It's pretty hard to read though. If you have some questions, you can ask.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      well i guess i have easier code to understand: 89231819

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      You don’t need radix sort to make this algorithm run in O(n). The problem already said that $$$a_i <=n$$$ so simply run through the hash array, find the maximum, and run again to find the number of maximum. (It could also be done in one loop.)

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    int main()
    {
    	int t;
    	cin>>t;
    	for(int i = 0; i < t; i++)
    	{
    		int n;
    		cin>>n;
    		vector <int> A(n);
    		vector <int> count(n,0);
    		int mcount = 1;
    		for(int i = 0; i < n; i++){
    			cin>>A[i];
    			count[A[i]-1]++;
    			mcount = max(mcount, count[A[i]-1]);
    		}
    		int k = 0;
    		for(int i = 0; i < n; i++)
    		{
    			if(count[i] == mcount)k++;
    		}
    		int ans = (k-1) + (n - k*mcount)/(mcount-1);
    		cout<<ans<<endl;
    	}
    	return 0;
    }
    
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the Binary Search solution to the C Problem ? Please explain how to perform the check whether a given minimum found by Binary Search is valid or not?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Please explain here

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      yeah, there are lot of video editorials available as well, go through youtube if you don't find em.

      So I came across the binary search solution in this contest only. You are using the binary search to guess the largest number possible which can accomodate all numbers.

      Think like this, the largest difference between numbers is going to be n. (when all numbers are different). and it's gonna be 0 when all numbers are same.

      So what i do is i try with mid. (n-0)/2. If i can create a possible permutation in which all like numbers are atleast at a gap of n/2. then I'll search in between range of n/2 and n. and so on.(Basic logic of binary search).

      If n/2 fails then obviously I try with a shorter number. This helps coz. If i try iteratively it'll be O(n) but with this I can make it O(log(n)).

      How we check the possible arrangement is like scheduling of numbers.

      Take a map and store all frequencies of each number.So you have some key value pair.

      Where first value corresponts to key i.e number and value is it's frequency.

      Now I store this in reverse order in set . the frequency being the pair.first and number being pair.second. How this helps is to keep a sorted order with greater where number with highest frequency is always at the top after every updation. ( I guess like max_priority_queue.

      PROCESS.

      1) pick the number on top of set. and since I assumed the partition size to be let's say k with binary search I store it in a vector. and decrease the count from the set. and reinsert it after updation of frequency.

      2) The purpose of vector is , when the vector gets filled to size k. (this first element was used k-1 steps back in our sequence hence can be pushed again in our expected permutation and we continue the process.

      2.1) If frequency count of first element of vector becomes 0. We can no longer use it.

      I hope this helps , go through internet and you'll find a better explaination than this, I guess.

»
9 months ago, # |
  Vote: I like it +11 Vote: I do not like it

In B, condition should be sum4 >= 1 and not sum4 <= 1.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If anyone need detail explanation ( not a video tutorial ) for B & C

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me editorial of problem C?

  • »
    »
    9 months ago, # ^ |
    Rev. 8   Vote: I like it 0 Vote: I do not like it

    when maximum occurrence 1 time
    n = total array size
    m = maximum occurrence number
    result = ((n-1)/(m-1))-1

    n = 8
    1 1 4 6 4 6 4 7

    m = 3 (cz 4 total 3 times)
    so result = ((n-1)/(m-1))-1 = 2

    when maximum occurrence more than 1 time
    n = 7
    1 1 2 2 4 4 7
    m = 2
    but 1 two time 2 two time 4 two time
    so let i = 3
    result = ((n-i)/(m-1))-1 = 3

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Has anyone thought of a BFS solution for problem D? I did try to find a DP solution but could only think of BFS when I upsolved it the day after the contest.

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Your question does not really make sense, but I suppose you could think of dp only. So I'll post the bfs sol here: Let's call rhombus lvl 1 just one square. Rhombus lvl 2 is the cross etc...Now you need to realize this : if you have a connected component consisting of the same letters the borders of this component are going to be the middles of rhombi lvl 1. So you label every square which is rhombus lvl 1 as rhombus lvl 1. (these are easy to recognize, they have a different letter right next to them. ) Every unlabeled square is rhombus lvl > 1. Now you can already see, that all squares that are unlabeled and next to a rhombus lvl 1 will be rhombi lvl 2. You label them as lvl 2 and continue for next lvls... This is what gives you the multisrc bfs solution. The lvl of a rhombus will be the distance to the nearest lvl 1 square.

    code : https://codeforces.com/contest/1393/submission/89257765

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

3b1b style visualization of neal's clean code to problem B, originally posted on Announcement blog due to late editorial, linking here

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does this contest have so many downvotes? The problems are quite interesting.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain me the chess problem rule . how they are putting blocks one by one.

i am new ti competitive coding . kindly try to explain me in detail.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'll try to explain it as clearly as i can. Now first imagine a big value of n. Now, we know that the first player will color the border most i.e. if you think it is of a grid then the 1st player will try to fill row(1), row(n), col(1), col(n). Lets call this as frame1. Now we know that the goal is to color the grid as a chess board so the first player will color alternatively. Now, when the second player will start coloring frame1 will be fully colored as well as some of the blocks in frame2 will also be filled. Now notice that frame2 is row2, row(n-1), col(2), col(n-1). The size of frame2 is 2 less than frame1. Now, when the first player again starts coloring the frame2 gets fully colored along with half of frame3 (which is 2 less than frame2).

    Now, if you see a pattern that frame1 gets filled in 2 steps and consecutive frames in 1 step. So, the ans = number of frames + 1; number of frames = n/2 as for each frame n is decreased by 2.

    Hope that helps!!

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain problem c and also the role of the binary search

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

No editorial for E1? =(

»
9 months ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

Problem E1/E2 also has a O( L ) solution, but it is an implementation nightmare, and the constant overhead possibly makes it worse than the O( L*Log L ) solution. The idea is to consider the cases when deletions are from both the strings, and the first string deletion is to the left of second string deletion, when it is to the right of it, and finally when deletion happens in only either the first string or the second string — https://codeforces.com/contest/1393/submission/89457260

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your approach sounds interesting, and I'm yet to dive into your code, but perhaps we can kill off the third case by adding a 27th character, say %, to the end of each word.

    finally when deletion happens in only either the first string or the second string

    So, deleting nothing from the string == deleting the %.

»
9 months ago, # |
  Vote: I like it -14 Vote: I do not like it

Storyforces

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone please explain the meaning of "It allows you to use the binary search on the answer" in 3rd question in the editorial.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For 1393 A , if n=7 my answer is coming out to be 5 . Can someone explain how is it 4?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I will explain you my logic for A. Let's say we know answer for i and we want to find for (i+2)x(i+2)(Adding two rows and two columns at all four sides of (ixi) matrix ). Now, if let's say person A is the last one to finish square ixi then the person A will also complete the squares he is supposed to complete in (i+2)x(i+2). And then person B will finish the (i+2)x(i+2) squares he is supposed to colour. Hence we can conclude that to colour (i+2)x(i+2) matrix we need only one more turn as compared to ixi matrix. So for a particular nxn matrix we can divide the case where n is odd or even. For odd n, for 1x1 we need 1 turn, for 3x3 we need 2 turn, so for odd n, the answer is number of odd numbers from 1 to n which is (n+1)/2. For even n,number of turns for n=2 is 2. For n=4 is 3. So number of even numbers from 2 to n is n/2. But since initially we need 2 turns for n=2, we need to add 1 to the result. So for even n, we need n/2+1 turns. So for your question of n=7, for 1x1 we need 1 turn, for 3x3 we need 2 turn, for 5x5 we need 3 turns and for 7x7 we would need 4 turns.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What does it mean by "We can use binary search and hash to compare strings in O(logL)" in the editorial of Problem E2?

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    First you need to calculate the prefix hashes for strings $$$s_1$$$ and $$$s_2$$$. Let these be $$$hash_1[1...n]$$$ and $$$hash_2[1...m]$$$ respectively ($$$|s_1| = n$$$ and $$$|s_2| = m$$$), where $$$hash_1[i]$$$ is the hash for string $$$s_1[1...i]$$$.

    For a given $$$i$$$ that you're searching on, if $$$hash_1[i] = hash_2[i]$$$, then you know that $$$s_1[1...i] = s_2[1...i]$$$, so the different character would be in the right half. Otherwise, if $$$hash_1[i] \ne hash_2[i]$$$, then there must be some different character in $$$1...i$$$, so search the left half.

    The specific hash method (rolling hash) used in this problem allows you to calculate the hash for any substring by making $$$(hash[j] - hash[i-1]) \div k^{i-1} = \text{(hash of }s[i...j]\text{)}$$$. This can be used to get the hash of $$$s[1...i-1, i+1...n]$$$.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey,

Can someone explain the data structures solution for the Problem B?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sure maintain a set of all planks and their counts in a set ordered by the counts(decreasing). then simply check all the conditions ( for this you need only the first 3 plankcounts).Also, Deletion and updating in a set can be performed easily in O(logn) code-https://codeforces.com/gym/320771/submission/110894283

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain to me why my solution for D fails, or just point out a (small enough) case that does not produce the expected output? 89490717

»
9 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

is this the first editorial that got downvoted ?

Also, I'm a noob and i can't figure out what does this part in editorial for B do. Can anyone plz explain ?

cnt2 -= cnt[x] / 2;
cnt4 -= cnt[x] / 4;
cnt[x]++;
cnt2 += cnt[x] / 2;
cnt4 += cnt[x] / 4;
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here cnt2 and cnt4 stores the total number of pair of logs and total number of quadruplets of logs. And cnt(x) stores the number of logs of size x. Suppose cnt(x) is initially 7. Now it contributes 3 towards cnt2 (as it has 3 pair of logs) and 1 towards cnt4 (as it has 1 quadruple). Now after increasing the value of cnt(x) by 1 it becomes 8 which should contribute 4 towards cnt2 and 2 towards cnt4. So that's why we decrease the value of cnt2 and cnt4 before increasing cnt(x)

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope its not too late...can someone please tell me what is wrong with this 89254760. I tried to solve the queries online... I kept the count of how many groups of 8, 6 ,4, 2 are there after each query... If i am missing some case please tell as i could not figure it out all this while.... Thanks in advance!!

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

E is a really nice problem ! Thanks,AlFlen and 74TrAkToR!

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone please explain the Problem E editorial in detail. I'm not able to understand the following

"Let's use dynamic programming dp[i][j] the number of ways to form the non-decreasing subsequence on the strings 1..i, s.t. the delete character in string i is j. This works in O(L3)" : How do we calculate dp[i][j] from smaller values of dp

"For each string, sort all strings obtained by deleting at most one character from this string. You can do it in O(L2.logL) for all strings." , Could someone please give an example of this

  • »
    »
    9 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Q1: $$$dp[i][j] = sum(dp[i - 1][k], k = 0\rightarrow n \mid str[i - 1][k] \leq str[i][j])$$$, $$$str[i][j]$$$ represents the string generated by deleting the j-th (1-beginned index) character from string $$$i$$$. $$$str[i][0]$$$ represents string $$$i$$$ itself.

    Q2: "For each string, sort all strings obtained by deleting at most one character from this string." Let's take 'abcd' as one of "each string". Then "all strings obtained by deleting at most one character from this string" represents the list ['abcd', 'bcd', 'acd', 'abd', 'abc']. Then sort them, we get the list ['abc', 'abcd', 'abd', 'acd', 'bcd']. For each string of length $$$l$$$, it takes $$$O(l^2\log l)$$$ to do that, because the list is $$$(l+1)$$$ long, and each time of comparing costs $$$O(l)$$$, too. But does $$$O(l^2\log l)$$$ sums up at $$$O(L^2\log L)$$$? I don't really understand, too. Waiting for better answers.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For the first question, how is it ensured in the dp that that the different strings are in non-decreasing order. If possible could you please give a short example ?

  • »
    »
    9 months ago, # ^ |
    Rev. 3   Vote: I like it +7 Vote: I do not like it

    Consider all the possible strings for the first case (from here is called $$$sub$$$):

       1       2       3
    1  bcd     aza     taka
    2  acd     zza     aaka
    3  abd     zaa     atak
    4  abc     zaz     ataa
    5  abcd    zaza    atka
    6                  ataka
    

    $$$dp[i][j]$$$ the number of ways to form the non-decreasing subsequence on the strings $$$1...i$$$ s.t. the delete character in string $$$i$$$ is $$$j$$$.

    In the above example, $$$dp[3][4]$$$ would be the number of sequences of the form $$$[sub[1][i_1], sub[2][i_2], sub[3][4]] = [sub[1][i_1], sub[2][i_2], ataa]$$$.

    This works in $$$O(L^3)$$$.

    To (naively) move from $$$i-1$$$ to $$$i$$$, for each $$$j$$$, count the number of modified strings in $$$sub[i-1]$$$ that are $$$\le sub[i][j]$$$. $$$dp[i][j] = \sum dp[i-1][k]$$$ for every string $$$sub[i-1][k]$$$.

    For each string, sort all strings obtained by deleting at most one character from this string. You can do it in $$$O(L^2 * \log L)$$$ for all strings.

    You can generate each $$$sub[i]$$$ in $$$O(|s[i]|^2)$$$ time and sort in $$$O(|s[i]|^2 \log |s[i]|)$$$ time. This overall comes out to $$$O(L^2 \log L)$$$ worst case (one giant string of length $$$L$$$).

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, $$$a^2+b^2\leq(a+b)^2$$$, I forgot that! Thx! Now I'm sure it's an $$$O(L^2\log L)$$$ algotithm!

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very sad to see dislikes for this beautiful problemset. Dislikes maybe because of long english statements (i did not find statements long , many past rounds contain more than this english) , late editorial, hard E . Problems are so tricky. The problems are really beautiful I have learnt other methods to solve B,C,D. Thank you so much.

»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Actually, although I've never solved the E/F problem in any div2 contests(and I didn't solve the problem D in this contest too, shamed), I don't think the problem E1 & E2 is so hard that it should be blamed of and the contest editorial should get a -119 voting. Anyway, if you just want to solve it in your mind rather than coding it and get an AC in the 2h contest time, it's able to do that. I thought these problems after the contest and got my solution, it is close to the NlogN solution, although I didn't do the hash and I got a wrong complexibility. I believe I can't solve the problem in the contest, but it's because of my insufficient capability, not the problem itself. I'm not saying that I can solve this problem and making a show of myself expressing that "Hey, I can solve this problem, you can't!", but I just want to say that the problem is not unsolvable and the -119 voting is unbelievable. It's not a problem that the problem contributor don't want you to solve, and it tests your mind and your way of thinking rather than your knowledge of uncommon algorithms. Every problem of this contest is doing so, and that's really cool. I think E1&E2 is a good problem, and the Round #662 is a good contest, from the bottom of my heart. Thanks to the problem contributor. Thanks for your reading. Sorry for my poor English.

»
9 months ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

Another Editorial for Problem D:

Let's enumerate on the bottom cell of a cloth. Define dp[i][j] as: the number of clothes that use the cell[i][j] as it's bottom cell. dp[i][j] are initially 1 for all $$$(i, j)$$$, now let's translate them. We can find that if dp[i][j] == X, then each of (dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1] and dp[i - 2][j]) should be at least $$$(X - 1)$$$, and all of these positions are filled with the same letter. So it comes:

if(cell[i][j] == cell[i - 1][j - 1]
&& cell[i][j] == cell[i - 1][j]
&& cell[i][j] == cell[i - 1][j + 1]
&& cell[i][j] == cell[i - 2][j])
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1], dp[i - 2][j]) + 1;

Finally, $$$ans = \sum_{i=1}^{n}\sum_{j=1}^{n}dp[i][j]$$$.

Great problem, and simple solution, thanks to Angavid. I told him a wrong dp solution (with a wrong complexibility), and he worked out this beautiful solution in 5 min.(He solved this problem in a totally different way(even not dp!) in the contest, and I don't understand it until now) Thanks to him. ydyyds!

»
9 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

For DIV2 D, a cell is the center cell of a pattern of size k if and only if the neighbouring cells are patterns of size k-1, I thought about this approach but couldn't formulate a solution in the specified complexity, did anyone follow the same?

UPDATE : Thanks to LUL____SEPLED1305 I understood, we have to figure out cells with value 1, all it's unvisited neighbours should have value 2, it can't be 1 because we already figured out those cells, it can't be 3 because it's neighbour is 1, we can use induction to extend this.

Submission : 89601502

»
9 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

nice contest

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you think it's okay to cut off $$$O(n \log n)$$$ solutions to E2 with a decent constant? Because I don't think it is. There's no reason to put such a strict time limit there.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please explain why in problem 2,we need atleast 4 pairs for making rectangle,it should be 2 pairs since we only need 2 pairs to make rectangle,we already made a square when we have 4 planks of some length

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

1393 B PLEASE HELP ME IN THE SOLUTION ,NOT GETTING WHICH CASE IS NOT CONSIDER

include<bits/stdc++.h>

define int long long

define rep(i,a,n) for(int i=a;i<n;i++)

using namespace std; void func() { int n;cin>>n; int a[n],b[100002]={0}; rep(i,0,n) { cin>>a[i]; b[a[i]]++; }
int p2=0,p4=0,p6=0,p8=0; rep(i,0,n) { if(b[i]>=8)
p8++;
else if(b[i]>=6) p6++; else if(b[i]>=4) p4++; else if(b[i]>=2) p2++;
} int q;cin>>q; while(q--) { char c; int k; cin>>c>>k;
if(c=='+') { if(b[k]==7) { p6--; p8++; } if(b[k]==5) { p4--; p6++; } if(b[k]==3) { p2--; p4++; } if(b[k]==1) p2++; b[k]++;
} if(c=='-') { if(b[k]==8) { p8--; p6++; } if(b[k]==6) { p6--; p4++; } if(b[k]==4) { p4--; p2++; } if(b[k]==2) p2--; b[k]--; } if((p8>=1)||(p6>=2)||(p6==1&&p4>=1)||(p6==1&&p2>=1)||(p4>=2)||(p4>=1&&p2>=2)) cout<<"YES\n"; else cout<<"NO\n"; } } signed main() { func(); }

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

AlFlen I can't understand how check function is working in Problem C solution. Can you explain? How do we make sure that x will satisfy the constraints?