YouKn0wWho's blog

By YouKn0wWho, 2 months ago, In English

The problem names are based on my favorite characters out there. Yes, 1554E - You are my most favorite character UwU.

I have tried to make the editorials as interactive as possible. Enjoy.

Tutorial is loading...
Code(C++)
Code(Python)
Tutorial is loading...
Code(C++)
Code(Python)
Tutorial is loading...
Code(C++)
Code(Python)
Tutorial is loading...
Code(C++)
Code(Python)

If you are wondering(as you always do 。^‿^。) about the checker:

Checker
Tutorial is loading...
Code(C++)
 
 
 
 
  • Vote: I like it
  • +328
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Nice contest :)

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

    I laughed so hard when saw that B's statements were updated and the only update was replacement of 2 with a 1 at the end ;))

»
2 months ago, # |
  Vote: I like it -23 Vote: I do not like it

A < C < D < B < E

»
2 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Such thinkforces B

»
2 months ago, # |
  Vote: I like it +62 Vote: I do not like it

Kudos from India man. I really liked your problems. Looking forward to more Bangladeshi rounds.

»
2 months ago, # |
  Vote: I like it +66 Vote: I do not like it

Nice contest, solving every problem costs a lot of thinking and observation!

»
2 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Like these problems, but don't like the order of the problems.

»
2 months ago, # |
  Vote: I like it +23 Vote: I do not like it

It appears a lot of people misread E (I thought the order of operations mattered, and the total count would be n!). Did none of the testers get this confusion? I feel like different sequences should have been in bold.

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

Great contest Lots of appreciation for Conducting round Thanks...

»
2 months ago, # |
  Vote: I like it +123 Vote: I do not like it

Thanks for the nice problems and the quick editorial!

»
2 months ago, # |
  Vote: I like it +10 Vote: I do not like it

The contest was a BIT difficult

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

Observation forces

No doubt problems were very good.

»
2 months ago, # |
  Vote: I like it -26 Vote: I do not like it

Problems were very cool this contest!

»
2 months ago, # |
  Vote: I like it +39 Vote: I do not like it

The gap between D and E is a bit large.

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

Such a wonderful contest. Thank you so much.

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

Thanks for the round and the quite interactive (with the 'Think's especially lol) editorial :)

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

BIT-forces

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

Nice contest, I'm fool.

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Read the solution for B and wonder where is my brain ::.

»
2 months ago, # |
  Vote: I like it +160 Vote: I do not like it

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

    harry potter cries in WA, LogicLessNess and FST's

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

Really liked the problems. Thanks!

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

Very Nice Contest!

Spoiler
»
2 months ago, # |
  Vote: I like it +12 Vote: I do not like it

I cannot believe this solution passed system test 124170859 on problem D.

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

    Similar Solution: 124179999

    I don't think, it can be hacked, although I don't have a proof of upper-bound on no. of characters used is less than 27. (Worst case calculations give upperbound as 3*log3(n))

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

      I hacked both

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

        Wow, You hacked it.

        Thank God, you were not in my room.

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

Fast Editorial!

It's a great contest,I love it.

I thought the contest would exercise my mind, but E was too difficult for me ...... :(

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

Loved the problemset. But D was easier than both B and C. My solution: 124163494

i.m.o., the problem ordering should've been: A — D — B — C — E

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

My solution to B is not dependent on k. We have all the value of array less than or equal to n. With this can what can iterate x from 1 to ceil(log2(n)) and assume x= (Ai|Aj). For each x we will find top 2 index with greatest value such the Ai is a sub mask of x.

124158918

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

    How do we know if x exists as OR of ai , aj? And you're not checking every sub-masks?

    Could you please explain?

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

      "How do we know if x exists as OR of ai , aj?"

      you are correct. It will not exist for every x. But we have to maximize the answer. It may happen that we may end up calculating the candidate answer for certain x which does not exit. But since, we are going through every mask, we will calculate the answer for all submasks of x too. If that submask is actually possible for some (ai|aj) then it will override the answer as submask(x) < x.

      "And you're not checking every sub-masks?"

      I am checking every submask. The top 2 value I am picking are the maximum 2(if possible) index from all possible submasks. Let say mask y=101010. Then I have already calculated the top 2 value for all the value <y. When I process y I just check these masks (001010,100010,101000), Since these invidually conatins the best 2 indices of all their submask, I am able to get all best two from all submask of y. Also the mask =001000 will contribute to (001010,101000) therefore we may end up having a duplicate index. We have to take care of that.

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

        Thanks a lot, that helped.

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

Loved the tutorial. Well explained <3

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

Can't understand how binary search will apply for problem c

Help apricated

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

    Why do you need binary search for C??

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

      I have seen some solution with binary search

      just curious to know but unable to understand how binary search property makes sense

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

    I did it using Binary search. So just try to understand the monotonic behaviour.

    Let Count(n,m, mid) is the function, that can give you the count of numbers that are less than or equal to mid from set of [n^0, n^1, n^2 ... n^m]; if(count(n,m, mid)==mid+1) it simply means our mex can't be less than or equal to mid+1.

    Now the only thing is how to build count() optimally. so it's a kinda digit dp problem. for more insights. u can visit my solution. https://codeforces.com/contest/1554/submission/124189939

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

Can anyone please explain B in some easy way??

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

    Well, my solution is different from the one in the editorial (and I don’t really think it’s simple), but here it is:

    If you fix the Ai | Aj part (let’s call it x from now on), you have to find 2 biggest indices i and j such that Ai | Aj = x, and then the solution is i * j / (k * x). Notice that 0 <= x <= 2 * n because Ai <= n. So, you can go through all x’s, and for every x, find the 2 biggest indices such that the numbers (bitmasks) on those indices are subsets of x (you can just go through all the subsets, check if they appear in the array and modify the max indices accordingly). But, the complexity of that is about n^2 if you’re not careful with implementation, so you have to use an optimization from this blog (look at the Suboptimal solution part, that optimization reduces the time complexity to 3^(log2(n))). And, I know I’m terrible at explaining things, so I suggest you to take a look at my code.

    Also, did anyone else have a similar approach? All the codes I’ve seen have an approach like the one in the editorial.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      I also did it with SOS DP, ofcourse submitted after the contest so as to not drop rating even more becoz couldn't do A. :(

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

      Yes, I solved it using SOS DP in O(NlogN) but still got TLE in system testing. And the same code was accepted in CPP 11 after the contest. :(

      https://codeforces.com/blog/entry/93321?#comment-822763

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

      can u explain that we can be sure if x would present as Or of ai, aj. That is not any two subsets of x will give x on Bitwise Or.

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

        Yeah, that's true, but if we go through all possible x's, we'll definitely find the optimal solution, because, if some x is not present as an Or of Ai and Aj, then it's definitely not the best one (for some two numbers, their Or is the smallest number which contains them both as subsets, so all bigger numbers can be ignored). So, those x's won't affect the final solution.

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Any meaning to the problem names?

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

Thank you for the great contest.

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

for B I only checked all pairs for last K + 2 elements, instead of last 2K elements and still didn't FST. thanks

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

    Yeah, we can do it too. But we don't need to be precise, all we want is a good upper limit and AC.

»
2 months ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it
meme spoiler
»
2 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Hello I'm new to codeforces and also am a beginner I wrote this code for cherry problem but only pretests(2) are passed can someone explain me the reason?


#include <bits/stdc++.h> #define D 20 using namespace std; typedef long long int ll; int main() { ll T; cin>>T; while(T--) { ll n; cin>>n; ll a[n]; for(ll i=0;i<n;i++) cin>>a[i]; ll mx=INT_MIN; for(ll i=1;i<n;i++) mx=max(a[i]*a[i-1],mx); cout<<mx<<endl; } return 0; }
  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    In the contest time, only two test cases will be judged and after the contest, other test cases will be judged that's why you can see pretests(2) passed.

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

      ok thanks bro

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

        Hi akhilphenom

        provide code in spoiler so it takes lesser space.

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

    Its better to leave now, than later.

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

Pause_and_thinkforces

I had a hunch even before the contest that D was going to be relatively easy (didn't expect it to be this easy though). Only if I had believed in my instinct! Excellent (and a bit unusual) problemset.

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

Why for the minimum value we are taking pair (n — 1 , n) in problem B ?

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

B can be easily done with sum over submask SOS Dp

see my sol

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

Hey, can someone prove why this approach doesn't get TLEd? I'm not able to figure out.

Iterate on all the numbers in the array. Let's denote a number $$$a[i]$$$ special if there is no number $$$a[j]$$$ such that $$$j\gt i$$$ and $$$a[j]$$$ is a submask of $$$a[i]$$$. When reach and index $$$i$$$ in the array and $$$a[i]$$$ is special, we run a brute force for $$$j\lt i$$$. But we terminate the brute force loop when we find a number $$$a[j]$$$ such that $$$a[j]$$$ is a submask of $$$a[i]$$$ (but we do calculate $$$f(i,j)$$$ for this $$$j$$$).
Solution.

Or if someone could hack this solution :3.

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

It is one of the best editorial because when i read every line i can connect with the thought process of the author and it is also beginner friendly to understand the concept. Thank You YouKn0wWho.

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

Best contest I've ever participated. Problem statement was so clear and look like easy pessy but too much tricky.I wish I will solve at least two problem in the next contest in future by this author YouKn0wWho

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

My solution to Problem D which requires O(log(n)) different characters, which, unfortunately, does not enter(

Suppose we have a matching string s. Then the string s + x + s + y + s is also suitable, where x and y are symbols that have not been encountered before. After all, each substring in s occurs 3 * the past number, and a substring containing symbols x or y occurs 1 time. Also from s you can make a string from |s| + 1 characters just by adding x to the end. Thus, you can make an algorithm similar to fast exponentiation: Let gen (n) return a good string of n characters.

if n % 3 == 2 gen(n) = t + x + t + y + t, t = gen(n / 3) else gen(n) = gen(n — 1) + x

It can be seen that every 3 steps n will decrease at least 3 times, but this will require 4 new symbols. Therefore, you will need log_3(n) * 4 = 44 characters

P.S. I don't know English well and all the text was translated by google translate

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

    I wanted to elaborate on Your idea. Actually, I managed to pass the tests using recursive approach during contest 124173130. As You mentioned it would be convenient to think of the problem recursively. We want to make three copies (just two will not do) of the same string and then and then separate them, by some characters that not be use later in recursion. Each of those recursive string should also maintain task requirements. It is easy to see that if some substring of final solution is maintained entirely inside of one of these substrings then there are three copies of it.

    But we also have to be careful when it comes to substrings that are not entirely obtained in one of recursive areas. We aim for our separators to make them unique (or also have three copies).

    There three recursive cases. Let's $$$N$$$ be length of recursive call, and $$$A$$$ be the lowest character we are still able to use. Also lets name by $$$B$$$ second lowest character. We will show that it suffices only to use two characters for separation and then $$$2 \cdot \log_3{N} \le 26$$$ (which will allow us not to run out of letters)

    First case is $$$N \% 3 = 2$$$. This case is easy. If we mark recursive string of length $$$(N-2)/3$$$ by $$$R$$$, then we can create solution as follows:

    $$$S = R + A + R + B + R$$$

    Second case is a bit more tricky. We have $$$N\%3=0$$$. We are still able to create separators, but they will be lightly longer (also length of $$$R$$$ will now be $$$(N-6)/3$$$).

    $$$S = R + ABAA + R + BB + R$$$

    Last case was the most tricky one ($$$N\%3=1$$$). I used the following construction.

    $$$S = R + BA + R + B + R + B$$$

    Now we added something after the last recursive part, but it was necessary if we want to have total length of separators equal to 4 (7 is impossible, because one of the letters would be used even number of times, and 10 is quite long and I was not able to find any two separators that would solve this problem, and also we are not careful may run out of digits for base cases).

    The last thing is just to look at base cases of the recursion, but we can then use consecutive letters that are left (and there is at least 6 of them).

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

I was so upset because of my bad contest day but the first line melted my heart -

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

This is one of the rarest times, where I am loving the editorial so much. It's like not directly jumping to the solution but building up to it and working on the thought process.

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

As for me it isn't adequate to have at contest problems with rating: 800-1700-1800-1800-!2600!

Also I think, that order should be like A-D-B-C-E, or smth similar

But I really like each task separately, thnk u!

»
2 months ago, # |
  Vote: I like it +17 Vote: I do not like it

E can be solved in $$$O(n \log^2 n)$$$ time if the product $$$\prod_{i=1}^{k} (a_i + b_i x)$$$ can be calculated in $$$O(k \log k)$$$ time.

Basically, if we let $$$f(k)$$$ be the ways to construct $$$a$$$ such that gcd is $$$k$$$, then then the mobius transform of $$$f$$$ can be calculated using dp (and fast polynomial products to calculate the dp values). After that, we can take the inversion.

I submitted the simple dnc code to calculate the product, which adds another log, and it passed.

Anyway, I thought the easter egg in E's naming was You = u = $$$\mu$$$. Seems like the intended one is different :P

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

If $$$a_i \leq n$$$ and $$$a_j \leq n$$$, then $$$(a_i|a_j) \leq 2n$$$.
Can someone, give me an example when $$$(a_i|a_j)$$$ is equal to $$$2n$$$.

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

    It can be shown that this inequality is strict.

    Multypling by 2 is bit shift to the left by one, adding zero, so if most significant bit of $$$n$$$ is $$$i$$$-th bit, for $$$2n$$$ it is $$$i + 1$$$-th bit, but if $$$x \leqslant n$$$, $$$x$$$ can't have $$$i + 1$$$-th bit.

    But there's an example where $$$x \leqslant n, y \leqslant n$$$ and $$$x \mid y = (2n - 1)$$$.

    Consider $$$n = 2^k$$$, $$$x = 2^k$$$, $$$y = 2^k - 1$$$. $$$x \mid y$$$ is equal $$$2^{k + 1} - 1 = 2n - 1$$$

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

      Yes, but quoting the editorial of B

      "since $$$0≤a_i≤n$$$, the maximum possible of value any $$$ai|aj$$$ is $$$≤2n$$$."

      $$$a_i|a_j = 2n$$$ is not possible.
      So shouldn't the symbol be $$$<$$$ instead of $$$\leq$$$ , in the last part ?

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

        consider $$$2n=00...001....$$$, where first 1-bit is k-th bit.

        now let's look at $$$n$$$. $$$k$$$-th bit will be set to zero, because dividing by 2 is equal to right-shifting by one.

        one of $$$a_i$$$ or $$$a_j$$$ must have k-th bit set to 1 (because $$$2n$$$ has). but that means than one of them are greater than n, because $$$2^k > 2^{k-1} + 2^{k-2} + ...$$$. this is impossible, so $$$a_i|a_j$$$ cant be equal to 2n.

        you are right

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

Has anyone tried to solve B using SOS DP and got TLE in system testing, in C++ 17?

In the editorial it is mentioned that O(N*K) is allowed, so O(NlogN) shouldn't give TLE I guess, I mean K can be as large as 100 and logN cannot be more than 20.

What's more traumatic? The same code was accepted in C++ 11 after the contest. That too in 530 ms. Difference of few ms is fine but 470 ms is too much, if this is the case then there should be different time limits for C++17 and C++11, even 1.2 sec would have worked. :(

It would be great if someone can explain the reason behind this difference in time, and also if anyone can justify why O(N*K) works but O(NlogN) gives TLE. (Except advising for compiler optimizations, if it was so necessary then it should be mentioned in the announcements or in the problem statement, or at least a pretest should be there which fails without these optimizations. All I want to say is if O(NlogN) fails without these optimizations then O(N*K) shouldn't be accepted too. <;_;> )

Here are the submission links:

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

    I see this too many time ; sometimes it work when I change compiler but anther times if you change the structer you may get AC for example the arry is more fast than vector but for memset it with value may vectorv(n,0);

    is more fast than

    ll a[n]; memset(a,0,n);

    anyway you should talk with problemseter or post a blog

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

    Can you tell why changing the order of for loop is giving wrong answer? like this — rep(mask,0,N) rep(i,0,lg)

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

Can someone explain why k * (ai | aj) is O(100 n)? Wouldn't it still be n^2 because to compute (ai|aj) you need to cycle through every j for each i still

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

    I also had this confusion when I read it. It's not about time complexities, I don't know why they used $$$O$$$ notation. It's just talking about the order of the values. $$$i \cdot j$$$ could potentially go up to $$$n \cdot (n-1)$$$, while $$$k \cdot (a_i | a_j)$$$ can only go up to $$$100 \cdot (2n-1)$$$, which shows that $$$i \cdot j $$$ will be way bigger than $$$k \cdot (a_i | a_j)$$$ because of the constraint on $$$k$$$.

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

if anyone having trouble with problem B

lets find out how far back we must go from index i to find its pair index j with which value i⋅j−k⋅(a[i]|a[j]) will be calculated. first we have a pair with i and i-1 which gave us pair(i,i-1) = i*(i-1)-k*(a[i]|a[i-1]). now we want to find an index with maximum distance from i that can give us better value than pair(i,i-1). for worst case minimizing pair(i,i-1) lets say pair(i,i-1) gives i*(i-1)-k*n (because for any x,y (a[x]|a[y]) is always less than 2*n)

now we are hoping that an index j with distance = d from i will give us better value than pair(i,i-1).

so, i*(i-1)-k*n < i*(i-d)-k*(a[i]|a[j]) (for giving best chance for j lets say (a[i]|a[j]) = 0)

i*i-i-k*n<i*i-i*d

d<(k*n+i)/i

d<1e7/i

so we have to go at most min(i-1,1e7/i) index back from index i.

for n = 1e5 and k = 100, there are 3*1e7 operations which passes the time limit. this might not be a good solution because its quite slow.

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

Sombody plz explain C. I could not understand even after watching streams/reading editorial.

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

sad it was a bitmask contest !! ^_^

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

i love 3e5

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

Great prombles! ^ ^

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

I don't know how my solution for B is working. Can you please help me to understand why my solution worked or in which test case it will give wrong answer. https://codeforces.com/contest/1554/submission/124175957

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

    Your are taking a window of {i to i+k} and finding the ans,TC is N*K

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

    You had to start from the end of the array, but it's ok if you start from the front.

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

      But don't you think for the (n-2*k)th element they are calculating upto nth element.

      But in my solution i just checked upto (n-k)th element.

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

        mrclr did the same. Any idea why it works ?

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

          I got the idea why it worked.

          Actually for an element the function could give maximum value for just next k elements not more than that.

          lets take an example:

          consider two cases, - ith & (i+k+1)th element: i*(i+k+1)-k*(some OR)

          • (i+1)th*(i+k+1)th element: (i+1)*(i+k+1)-k*(some OR)

          clearly, (i+1)*(i+k+1) > i*(i+k+1)

          or (i+1)*(i+1) + (i+1)*k > i*(i+k+1)

          or i*i+ 2*i + 1 + i*k + k > i*i + i*k +i

          or i + 1 + k > 0

          So, for each element we will achieve, our maximized expression by just checking next k elements not more than that.

          I hope this will clear, why this worked.

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

Nice contest. Looking forward to more Bangladeshi rounds.

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

The problems are well-prepared, but I really wonder why the D is a constructive problem without any other algorithms. In my opinion, this one should be used as B(so I think swapping B and D is a good choice).

Although I know no one will vote for my comment, but I still want to say the suggestions as the writer may hold a round again in the near future.

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

interesting E ...... (but too difficult TAT)

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

Very short and nice statements. But when i see "mikasa", i expected some back story about author and this girl :)

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

In problem A, according to the editorial, if the array is 3 1 4, then the best of adjacent products(3*1 and 1*4) would be less than the actual answer 12. (I am completely new to this field. So pointing out where I went wrong would be really helpful)

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

    No. Actually ans will be max(3*1,1*4) why? Because in problem Statement say you should take arrary Between range[l,R]. So you are taking the hole array [0,2] so ans will be max(arr[l:r])*min(arr[l:r])

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

    If you consider the subarray{3,1,4} the max is 4 but the min is 1. so there product is 4,not 12 according to the problem statement.

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

i think the B is wonderful !!

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

In problem B, Code(C++), for the case n=6,k=1,a={0,0,0,0,100,100}, it returns -70. Isn't it exactly 12? but i forgot that a<=n. Sorry.

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

why we shoule do this (if (m >> k & 1) ans |= 1 << k, n |= 1 << k;)operation at Problem C?

»
2 months ago, # |
  Vote: I like it +71 Vote: I do not like it

Editorial for ABCD be like

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

I think the solution of D is so wonderful , because I have a complex and strange solution which I have to proof it doesn't exceed 26 distinct character.

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

    Yeah, D is brilliant and might be easier than B and C, but I liked all the problems!

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

Editorials are really good and problems were good.

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

YouKn0wWho

There is a typo in the editorial for C:

If $$$n_i = p_i$$$ then we can set $$$k_i = 0$$$ as $$$n_i \oplus 0 = n_i <= p_i$$$.

At the very end it should be $$$n_i >= p_i$$$.

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

problem B: Cobb , are you mean domnick cobb?

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

Can someone have a look at my code for problem B? The runtime should also be O(n-k), but it timed out on test case 2. It really doesn't make sense... The intuition is that f(i,j)>f(n,n-1) is only possible when i,j >= sqrt(f(n,n-1)), which is similar to what is given in the tutorial

Thanks!!!

#include <bits/stdc++.h>

using namespace std;

int64_t task(vector<int> &nums, int k)
{
    int n = nums.size();
    int64_t ans = n * (n - 1) - k * (nums[n - 1] | nums[n - 2]);

    int least_i = 0;
    if (ans > 0)
    {
        least_i = sqrtl(ans) - 1;
    }

    for (int i = least_i; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            ans = max(ans, (int64_t)(i + 1) * (j + 1) - (int64_t)k * (nums[i] | nums[j]));
        }
    }

    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n, k;
        cin >> n >> k;
        vector<int> nums(n);
        for (int i = 0; i < n; i++)
        {
            cin >> nums[i];
        }
        cout << task(nums, k) << '\n';
    }
}
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    int64_t ans = n * (n - 1) - k * (nums[n - 1] | nums[n - 2]);

    You're running into an overflow here. Even though ans is a 64-bit int, n is 32-bit, and when computing n * (n - 1) the value is stored temporarily in a 32-bit int which causes an overflow.

    Try typecasting any values to 64-bit integers when you run the risk of overflows, like so - int64_t ans = (int64_t)n * (n - 1) - (int64_t)k * (nums[n - 1] | nums[n - 2]);

    Also, you should ideally either link to your code, or enclose your code in

    spoiler tags

    .

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

I think the time complexity of problem B should be O(n + k^2) instead of O(k^2). Please correct me if I am wrong

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

Bit manipulation : I am bout to end this man's whole carrer.

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

Is there an approximate value of $$$σ_0$$$ represented by Big O notation less than $$$O(\sqrt{n})$$$?

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

    $$$\mathcal{O}{(\sqrt[3]{n})}$$$

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

      It is not proven fact(maybe it is wrong), but for all numbers less than $$$10^{12}$$$ it is barely true. But you shouldn't use this in asymptotics.

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

i was too close to B

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

B should have been a little easier or A should have been a little more difficult!

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

Hello, (in problem B) could someone explain why my this submission didn't pass while this similar solution does. Any effort will be appreciated.

Update: There was an integer overflow and it got accepted after fixing it. Accepted solution after fixing overflow. (Thanks)

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

An excellent contest which improve my understanding of the BIT problem, but the only pity is that I didn't attempt to have a look at the D I should have solved ,'casue I failed to solve the B and C.

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

i still not able to understand B(1554B — Cobb) Can anyone please explain B in some easier way

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

Ok so I overkilled B. But I have a very different solution for B. I used SOS dp for B, where the constraints on k does not matter at all. Just store for each mask the two highest indexes of its all submasks which can be easily calculated using SOS dp. Then just choose the maximum value among all masks.

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

I can't understand the calculation formula of Hk of problem E. Can someone explain it?

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

    Problem E — hk calculation :

    fk = number of sequences divisble by k => this will include all sequences that are also divisble by 2k, 3k, 4k, 5k and so on;

    So, to get the number of sequences where the gcd is k, you can subtract sequences where gcd is greater than k and which were counted in fk

    So h(k) = f(k) — h(2k) — h(3k) — h(4k) ......h(ik) ---- until ik becomes > n;

    h(k) needs to be calculated from higher to lower values ofc.

    Hope this helps you

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

      Your explaination is very helpful. Thank you.

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

Well, my solution for B, is for every 1 <= j <= n, search every i in max(1, j-k) <= i < j, and try to use f(i, j) to update the answer. I know it isn't a correct solution, but I passed the system test...

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

About Problem E,there is a similar solution with better Time Complexity.

Noticed that for any $$$k>1$$$,a sequence $$$a$$$ such that each $$$a_i$$$ is divisible by $$$k$$$,it can be proved that there will be at most one condition.

Then we can only check $$$x|n-1$$$ and $$$x$$$ is prime.And when we check whether a sequence $$$a$$$ such that each $$$a_i$$$ is divisible by $$$x$$$ can be build,we could find the exact gcd number at the same time.

It runs much faster than the code of Editorial.

The exact time complexity should be $$$\mathcal O(n\omega(n-1))$$$ while $$$\omega(x)$$$ is the number of prime number that can divide $$$x$$$.I think it is no more than $$$\mathcal O(n \log \log n)$$$

This is my code.

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

    When $$$n - 1$$$ is a primorial, $$$\omega(n - 1) \sim \frac{\log n}{\log \log n}$$$.

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

D is too overrated imao, but I'm glad that I read ALL PROBLEMS and quickly solved D. Wonderful contest!

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

Great editorial !!

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

Just Awesome

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

excuse me ,what does the problem E the last step h_k = f_k — \xi h_ik mean

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

Thanks for the great tutorial

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

Try to solve problem D if we consider subsequence instead of substring! It is an interesting problem.

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

Can someone explain problem E why two dfs with different roots can't form two different A sequences?

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

Such a beautifully written Editorial.

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

Looking back at B. The question does not seem too hard. The brute force is very easy to write but I never did think that we should just start from the last 100 elements.

So in the end it's just brute force + 1 extra line of code to ensure we only check 100 elements.

https://codeforces.com/contest/1554/submission/124263914

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

can anyone tell why i am getting tle here in D void solve() { ll n; cin>>n; ll i,k; string ans=""; if(n%2==0) { if(n==2) { cout<<"ab"<<endl; } else { k=(n-1)/2; for(i=0;i<=k;i++) { ans=ans+"a"; } ans=ans+"b"; for(i=0;i<k;i++) { ans=ans+"a"; } cout<<ans<<endl; } } else { if(n==1) { cout<<"a"<<endl; } else { k=(n-2)/2; for(i=0;i<=k;i++) { ans=ans+"a"; } ans=ans+"bc"; for(i=0;i<k;i++) { ans=ans+"a"; } cout<<ans<<endl; } } }

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

Well-written editorial!

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

Simple explanation of Problem A — Cherry

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

Thi is My approach For Problem C

we know the xor properties 0 xor 0 = 1 xor 1 = 0 1 xor 0 = 0 xor 1 = 1 so in this ques we have concluded the condition n^MEX>=(m+1)

we have to find MEX(as small as possible) so we will move from 31 st bit to 0th if we found ith bit of n and ith bit of (m+1) is same then will make ith bit of MEX is 0(keeping in mind that we r making MEX as small as possible)and if ith bit MEX is 0 and (m+1)'s ith bit is 1 then we will make ith of bit of MEX is 1 (if we take zero it becomes smaller than m+1) and finally if ith bit MEX is 1 and (m+1)'s ith bit is 0 then we can say thay MEX is already greater then will add zeroes in further position !

**MY CODE : **124203362

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

    Thank you

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

    why don't we start from 0-th bit instead of 30-th bit,since we want to find smallest k. starting from 0-th bit we can proceed as->for i-th bit from right we add 1<<i to temp(variable) and using another loop we add to temp every (1<<j) [∀j<i:n&(1<<j)==0].

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

      Beacuse n^mex >= m+1, so starting from zero might not result in this condition

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

The Python code for B in this editorial (YOUR OWN CODE) is giving TLE on test case 10. https://codeforces.com/contest/1554/submission/124273841

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

    This difference language should not be there..... if the algorithm implemented is same.

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

How in 2nd statement of problem B maximum possible of value any ai|aj is ≤2n

as ai<=n

so ai=aj=n;

n|n==n

but how n|n==2n ??

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

Can anyone explain the logic behind problem E observation 2 ?? Why will there be only 1 or no sequence for k>1??

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

    In observation 1 they describe an algorithm starting with: "Let's construct a sequence $$$a$$$ such that each $$$a_i$$$ is divisible by $$$k$$$."

    The idea is that by looking at the algorithm's steps, everything is essentially fixed. There's no place in the algorithm where you can choose from a variety of options. You can either complete the algorithm or you can't. If you can complete the algorithm for some k, then f(k) is 1. And if you can't, f(k) is 0.

    I would recommend you to take a couple of sample trees and trying out the algorithm by hand for constructing the sequence $$$a$$$ for a fixed $$$k$$$.

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

i have understood the problem C but can't code it. Any links to tutorial of bitmask. inorder to approach such prob.

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

E can be solved in $$$O(n \log \omega(n - 1))$$$ where $$$\omega(x)$$$ is the number of distinct prime divisors of $$$x$$$. There is a conclusion that $$$\omega(x) = O(\frac{\log x}{\log \log x})$$$, so the complexity can be written as $$$O(n \log \log n)$$$.

Code

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

Using

Spoiler

gave me 11 times wrong answer in 1554A - Cherry .Can anyone tell me the reason behind this?

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

    Assalamualaikum Brother, You can remove it and run the program.

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

      Wlaikumuslam brother.Yes,after removing it i got AC.I just wanted to know the reason so that in future i can handle this issue .

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

Can someone explain the 2nd observation in the Editorial of last question?? " f(k) for k>1 is either 0 or 1."

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

    In observation 1 they describe an algorithm starting with: "Let's construct a sequence $$$a$$$ such that each $$$a_i$$$ is divisible by $$$k$$$."

    The idea is that by looking at the algorithm's steps, everything is essentially fixed. There's no place in the algorithm where you can choose from a variety of options. You can either complete the algorithm or you can't. If you can complete the algorithm for some $$$k$$$, then $$$f(k)$$$ is 1. And if you can't, $$$f(k)$$$ is 0.

    I would recommend you to take a couple of sample trees and trying out the algorithm by hand for constructing the sequence $$$a$$$ for a fixed $$$k$$$.

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

I really like the editorials. Would love to see more such editorials for upcoming contests!

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

Can somebody explain why in problem E the formula of $$$h_k$$$ is $$$h_k = f_k - \sum\limits_{i=2}^{\left\lfloor\frac{n}{k}\right\rfloor} h_{i\cdot k}$$$, but not for example $$$h_k = f_k - (h_{2k} + h_{3k} + h_{5k} - h_{6k} + \ldots)$$$ (like the inclusion-exclusion formula)?

UPD: Ok, I understood. That's because $$$h_k$$$ is the number of sequences that have gcd equal to $$$k$$$ (not gcd divisible by $$$k$$$).

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

Really Great Editorial for B. Thank you, Sir.

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

Problem E is very nice! Masterpiece of small observations!

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

Hi, may I ask a question? Are there someone could explain the function of the words "n|=1<<k;" in Problem C? I'm sorry for my poor English.....QWQ Thanks!

»
7 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Awesome from problems to the turorial

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

Not sure if this is too obvious or has already been covered, but you don't really need dp. For each $$$k \gt 1$$$ you simply need to figure out if the tree can be split into stars with number of edges divisible by $$$k$$$. Instead of doing dp yourself, you can show by induction that this problem is equivalent to the following check. For each vertex, consider the sizes of its subtrees. If some are divisible by $$$k$$$, ignore them. For the rest, if there is one which is $$$\gt 1$$$ mod $$$k$$$, it is not possible. Otherwise count those which are 1 mod $$$k$$$, and their number should be divisible by $$$k$$$. This way you need to do only one dfs in the beginning to calculate subtree sizes. It seems more efficient overall...

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

the B is very nice,so beautiful problem!

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

The editorial is literally lucid

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

In problem B, It's when an−1|an is maximum. And, since 0≤ai≤n, the maximum possible of value any ai|aj is ≤2n I don't understand how?