Anadi's blog

By Anadi, history, 5 months ago, In English

1466A - Bovine Dilemma

Tutorial
Solution 1
Solution 2
Challenge

1466B - Last minute enhancements

Tutorial
Solution 1
Solution 2
Challenge

1466C - Canine poetry

Tutorial
Solution 1
Solution 2
Challenge

1466D - 13th Labour of Heracles

Tutorial
Solution

1466E - Apollo versus Pan

Tutorial
Solution

1466F - Euclid's nightmare

Tutorial
Solution

1466G - Song of the Sirens

Tutorial
Solution

1466H - Finding satisfactory solutions

Tutorial
Solution

1466I - The Riddle of the Sphinx

Tutorial
Solution

I am really interested in solving this task using fewer queries or proving that $$$3 \cdot (n + b)$$$ is optimal. Does anyone have any idea how to answer these questions?

UPD: There are challenges added to some tasks.

Tutorial of Good Bye 2020
 
 
 
 
  • Vote: I like it
  • +316
  • Vote: I do not like it

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

Thanks for the fast editorial! Loved the round btw. :)

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

Happy New Year)

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

Happy New year :)

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

some telegram pages leak solution please check plagiarism

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

Ending 2020 on a high note, really awesome problems!

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

Wow, publishing solutions, great materials to learn.

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

B was bit tricky. Nice problemset though and fast editorial

»
5 months ago, # |
  Vote: I like it -25 Vote: I do not like it

B was a bit tricky. Nice problemset though and fast editorial.

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

Thanks for fast editorial!!

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

A nice round to end the year :)

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

Happy New Year! Nice contest to end this year

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

My $$$O(60*N)$$$ Java solution for E got TLE 2 Sec was a tight limit

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

    Limits were tight for Java. 26*26*N solution for C doesn't pass :(

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

    A trick for the future:

    If you're adding a + b and (a < mod and b < mod), then (a+b) % mod is equivalent to

    int c = a + b;
    if  (c >= mod) c -= mod;
    

    Given the slow nature of mod and java this will really help you squeeze under time limit

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

      You forgot to include the equality too i guess if(c>=mod)

      Am i wrong?

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

      isn't it if(c >= mod) c -= mod?

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

      Wow, I discovered exactly the same bug in my Modular class in library, which I was (successfully!!!) using during around 1.5 years and around 20 AC submits...
      Thank you so much!!!

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

      wdf are u making wierd faces ...lmao

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

Hope 2021 is not the same as 2020 : ) Happy New Year!

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

CODE why is this getting RE ?

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

Amazing problems as well as amazing editorials. Kudos to the setter :))

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

A very good problem set loved it!

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

It's probably $$$\mathcal{O}(n + q \cdot | \Sigma | + S)$$$ in G. Or it's possible to completely get rid of the alphabet size?

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

    If you solve it offline, it is possible to solve it in linear time (assuming that the alphabet is $$$\mathcal{O}(n)$$$).

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

      Ah yeah, it's kinda contained in $$$S$$$ part. Isn't it possible to solve it online: SA for occurrences in the short parts and KMP for the long parts? The only problem is the prefix sums cuz we get an extra $$$\log n$$$ don't see how "offline-ness" helps in any way.

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

        I was thinking about something like having for each letter memorized its value (prefix sum) and last occurrence. I think it should be enough to recover the answer in $$$\mathcal{O}(1)$$$ for a fixed letter.

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

Nice problem set, but problem statements were not short (which is not cool).

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

    They weren't long either? Just enough length to make it have fun theme I thought.

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

    I think the statements were just right. One could skip reading the story and other embellishments fairly easily. I personally enjoyed reading the story part; Makes the problem not-so-forgettable. Though, this is just my opinion.

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

    yeah, it's a little hard for me to understand the statement, maybe my English is so pool.

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

In solution 1 of problem A, N is not defined.

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

If anyone has some alternate approach for C ..then share ..Tx in advance

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

    This one passed the pretests (for now) and is not a dp solution but what i basically thought was that the palindrome of length 2 or 3 should not exist, so basically

    s[i] != s[i+1] || s[i] != s[i+2]

    If it does happen then I change the values of s[i+1] or s[i+2] to # sign. The reason being that im considering # to hold a value that is not equal to its i+2 or i+1. So if i ever encounter # sign i skip it knowing that if s[j] = # then theres no need to check s[j+1] || s[j+2] because it will not be ever equal. Hence the answer is just the number of # signs in the resulting string! Code (I used # here because the dollar sign was converting my text to latex)

»
5 months ago, # |
  Vote: I like it -14 Vote: I do not like it
The comment removed because of Codeforces rules violation
»
5 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Good bye, orange :'(

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

For problem E, even in C++, my O(60*N) solution got TLE, what could be the reason my solution

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

    A lot of %mod and fastio is missing. Not sure.

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

    Probably fast io, I did something similar with fastio and got 1500ms and then resubmitted with c++17(64bit) by precomputing powers of 2 by mod and got 500ms

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

      Will a solution which got accepted in g++ 17 will also get accepted in 64 bit always ? I might be wrong but in initial days (when 64 bit was launched) i got WA but same got accepted in g++ 17.

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

        tbh thats the same reason I stopped using 64 bit back then, one of the contests it gave wa whereas the same code gave ac in g++14 or 17. Now I only use 64bit for problems with tight TL since its twice as fast if using along long long.

        If anyone knows the reason to this please reply

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

    Jus precalculate all powers of 2 modulo 1e9+7. But don't use them for bitwise operations. Use left shift operator for them.

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

    My O(60*N) solution failed too :( I guess fastio will help

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

    You are reading around $$$500\,000$$$ numbers with cin without ios_base::sync_with_stdio(false).

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

I hoped for an explanation what 1466F - Кошмар Евклида asks for, and how we can interpret the input. What is the meaning ok k? (that value that is 1 or 2)

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

    It tells number of positions in the vector where 1 is present . maximum number of 1 in the vector can be 2 . For example in 1100000 , k=2 . Isn't that obvious from samples ?

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

      For me it is not obvious, no. Why is the maximum number of 1s in the vector 2. Is this by definition, or is this some basic property of the vectors?

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

        ok . It was mentioned in the question that "at most 2 coordinates equal 1" . Thus it was defined in the question , it's not property of vectors .

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

          There is a defintion of "Consider sets A and B such that..." What is this good for? I cant relate that to the other parts of the statement.

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

            For explaining "lexicographically smaller" .You need to output lexicographically smallest subset in case of same size.

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

O($$$n$$$ * 26 2 ) dp gave MLE in problem $$$C$$$.
but

We can notice that we are not interested in the last 2 characters' exact values.

that's a nice observation, i wish i had observed it.

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

    It actually shouldn't you have an extra dimension of length in your dp array in the way you have implemented it, just make it dp[26][26]. Here is my iterative O(n*(26^2)) dp 102865773.

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

Can someone explain me how to solve F?

PS: I am newbie in Linear Algebra.

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

My solution to 1466F - Кошмар Евклида

We can use DSU to solve this problem in one pass. A key point here is to create a virtual node $$$m$$$ (we use 0-index here, so we have $$$0\dots m-1$$$ as actual nodes) and connect all single nodes to it.

For each vector:

  • If it has only one number $$$u$$$, we check if $$$u$$$ is already connected to $$$m$$$. If it is not connected to $$$m$$$, we connect it and add this vector to the answer.
  • If it has two numbers $$$u$$$ and $$$v$$$, we check if $$$u$$$ and $$$v$$$ are connected. If they are not connected, we connect them and add this vector to the answer.

Now that we already have $$$|S'|$$$ and the final selection, we need to calculate $$$T$$$, which is actually as simple as:

$$$\prod 2^{size[i]-1}$$$

Where $$$size[i]$$$ means the size of the $$$i$$$-th connected component.

The time complexity is thus $$$\mathcal{O}(n+m)$$$ (here we neglect the $$$\alpha(n)$$$ part).

Explanation:

  • We call a bit "free" if it can be set to either $$$0$$$ or $$$1$$$ regardless of how other bits are set. Obviously, a vector with a single number can make a free bit. Since the vectors have at most two numbers, if one of the numbers is free, then the other is free, too, because we can combine the free bit with the current vector to get another free bit. We then observe that the "freeness" is transitive, and that's why DSU can be used.
  • If in a connected component, there are no free bits, then we can only make vectors with an even number of set bits with this connected component since each addition will add either $$$2$$$ or $$$0$$$ set bits. This is where $$$2^{size[i]-1}$$$ comes from.
  • To generalize the processing of 1-number vectors and 2-number vectors, we make the virtual node $$$m$$$ so that all the free bits are now in a connected component.
  • By choosing every disconnected edge, we are actually making MSTs for every connected component. And it can be shown that there is no better strategy (meaning we can get the lexicographically smallest subset whose size is also the smallest possible).
Code
  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks a lot for the explanation of T calculation. I didn't understand from editorial why it should be 2^{s'}.

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

      My thought is that for each vector in the answer, you can either use or not use it, so this gives $$$2^{|S'|}$$$

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

    In a very similar idea (maybe same idea), you can just use path compression and run the algorithm that generates a xor basis that is in this blog. Basically we have n vector's with at most 2 active bits and $$$f(\vec{v_i}) = min(x_1, x_2)$$$ (or just $$$x_1$$$ if $$$k = 1$$$) where $$$f(\vec{v_i})$$$ is simply the first active bit of the vector $$$i$$$ and $$$f_2(\vec{v_i}) = max(x_1, x_2)$$$ (or $$$-1$$$ if $$$k = 1$$$) where $$$f_2(\vec{v_i})$$$ is the second bit active in $$$v_i$$$.

    If the basis doesn't contain $$$f(\vec{v_i})$$$, you add this vector to the basis and you create an edge from $$$f(\vec{v_i})$$$ to $$$f_2(\vec{v_i})$$$. What this means is if you arrive at this bit in some point while checking if a vector $$$j$$$ is represented by the basis, it means you will remove $$$f(\vec{v_j})$$$ from it and add $$$f_2(\vec{v_i})$$$ (while doing the operation $$$\vec{v_j} = \vec{v_j} - \vec{v_i}$$$). So to finish it up, you do the same to the second bit of vector $$$j$$$, if you get that they are the same value (or they are equal to $$$-1$$$), it means they cancel eachother out and the vector $$$j$$$ is represented by the basis. Otherwise you have a valid new bit that currently can't be represented by the basis.

    The only downside is the complexity which is something like $$$O((n+m)log(m))$$$.

    Submission

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

    It's a really good explanation, but can you tell me what do you mean by "since each addition will add either 2 or 0 set bits"?

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

      Suppose we have {1,2}, {2,3}, {3,4}. Obviously, there is no free bit, while all bits are in a connected component.

      Starting from {1,2}, if we add {2,3}, then 2 is erased while 3 is added, so set bits remain unchanged. If we add {3,4}, then set bits increase by 2.

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

    Would you consider this case, please?

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

    Can you recommend other problems like this one to practice? I still unable to figure out how to reduce this kind of problem to a graph problem and then to DSU or MST. Thanks

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

I gave my first contest today. attempted the first A level question in python and after the contest, I check my rating it is still zero and in the submission section, it is written queue under verdict, can anyone guide me on what is queue meaning in the submission section, and is it the reason my rating didn't changed?

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

    It needs some time, just be patient.

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

    Your solution was checked on some pre tests during the contest

    After contest is over, all solutions go through a series of system tests. If your solution passes the system tests you will get the ratings after it.

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

    During the contest your solution was tested only on some tests (called pretests) and now it's waiting to be judged on full testset (and looking at current state of the queue: https://codeforces.com/contest/1466/status I fear it might wait for a while). After all submissions are judged the final standings will be available, everyone's rating will update several hours later. You can install this plugin: chrome://extensions/?id=ocfloejijfhhkkdmheodbaanephbnfhn (at least in Chrome, idk if there's anything like this for other browsers) to see immediately approximate rating change you will get.

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

What should I change in this submission to not receive compilation error?

https://codeforces.com/contest/1466/submission/102855965

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

    ce_test.cpp:75:29: required from here /usr/include/c++/9/bits/stl_tree.h:780:8: error: static assertion failed: comparison object must be invocable as const 780 | is_invocable_v<const _Compare&, const _Key&, const _Key&>, | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    The reason is multiset<pi, cmp> will keep some constant object of type cmp and will call operator() on it So instead of this

    bool operator()(const pi &lhs, const pi &rhs) {
      //...
    }
    

    you should use

    bool operator()(const pi &lhs, const pi &rhs) const {
      //...
    }
    

    this const means the method can be called on a const object

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

Are there any solutions for F which do not require MST?

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

    We can solve it with DSU only. You can refer to my comment above.

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

    If you know about the rank-nullity theorem and that the rank of matrix equals the rank of its transpose, the problem becomes: for each vector with a single non-zero entry $$$u$$$, mark vertex $$$u$$$, otherwise it has another non-zero entry $$$v$$$, so add an edge between $$$u$$$ and $$$v$$$, now count the number of connected components without a marked vertex (this equals the nullity of the $$$n$$$-by-$$$m$$$ matrix with rows equal to the vectors given in the problem). No need to create a virtual vertex.

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

    This solution does not require MST or creating a virtual node which is connected to the 1-bit vectors: https://codeforces.com/contest/1466/submission/103923589

    Disclaimer: code & its comments may be difficult to understand, since I didn't polish any of it for readability.

    General idea is that I have a data structure where where you can insert vectors one at a time into it. The data structure can determine whether an inserted vector is redundant with earlier added vectors. It uses ideas from the union-find data structure.

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

Who else have wasted a lot of time in D? Btw Happy New Year :) .

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

C can be solved by a greedy approach.
If ith character is same as I — 1 th or I — 2nd, replace by a third character (dummy), increment answer by 1.

Intuition: If any 2 consecutive characters are same, we need to replace one irrespective of other characters.

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

Is there any solution to solve A in O(n) time ?

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

yaay solved B , just still need to figure out how to solve C ,D ,E ,F and G to become grandmaster :3

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

Can somebody explain why in problem F doing this trick with increasing m by 1 and assigning m+1-th character to 1 in every vector with k=1 doesn't change the result?

»
5 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Problem statements were too long and bad. For understanding the problem i need to read notes. At least notes were good.

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

Can some tell me how to solve the challenge part of Problem A i.e., Try to solve it for n,xi≤10^5

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

    We need to get unique differences, you can do it using bitsets. You need to see what differences you can get. So the solution is -

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

    $$$~$$$
    $$$~$$$
    $$$~$$$
    $$$~$$$
    $$$\gets$$$

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

The editorial is very interesting with these challenges

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

.

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

    that's why I thought why these days I am unable to solve B and C quickly , while so many participants are solving B, C and D. :(

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

    unfortunate. needs some action

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

    That's why so many AC's today. Don’t feel upset, they just got some ratings, not skills.

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

    Something has to be done about it.

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

    cheating in problem D is dis heartening , MikeMirzayanov please use moss or some strong plagiarism checker

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

    This issue should be sorted out asap... !!

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

    In the end they could always create a new group. So just participate in contests the right way. You will get better unlike them.

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

    Well codeforces is not giving any type of prizes , there is not any perks for having good rank and definitely, your crush is not going to impress by seeing your rating rather than self satisfication....:) So why mass cheating??

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

      Such people even spoiled Codechef long challenges especially . Now most pepole do not keep faith in codechef rating untill you are 6 or 7 star.

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

    hope so !!!

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

    there is one person in our school,he almost can't solve any problem in our school test, but get Master(orange) in codeforces easy.

    In China, codeforces Round usually hold in night, in the next daytime, I ask the statement in Chinese of the problem he have passed, he couldn't answer any.

    Usually, he even don't know the problem's statement but get the right code.

    To protect him, I can't publish his codeforces Id.

    sorry for my poor English.

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

      give his id bruh ..their wont be any cas eagainst him and his lif ewill be fine so dont worry about that

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

    The reason why i don't give codechef long challenge. Now , they are doing this on codeforces too. These things are really disheartening. But ya don't get dishearten. Your skills >> Your rating.

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

    this is setup by other platforms to bring value of codeforces down

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

Thanks for releasing the editorial early.

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

Here are solutions in video format for A-F and my idea for G, although my G probably sucks or something since it failed

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

I think that there is an easier way to think about H. I don't know why the statement contains an information that for every preference profile there is an unique way to create the permutation, as it says something about the way how to solve the problem, but during the contest I had no idea how to prove it or even why is it true.

We just have to know that after reducing the cycles to single vertices the whole graph has to be acyclic. Calculating the number of labeled DAGs on $$$n$$$ vertices is a well known problem which is solvable in $$$O(n^3)$$$ and we can do a very similar thing here (but the vertices have some kind of weights, so we have to maintain the multiset).

EDIT: by graph I mean the following: if the $$$i$$$-th guy prefers $$$j$$$-th guy instead of the guy that he received the gift from, then let's draw an edge from the $$$i$$$-th to the $$$j$$$-th vertex.

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

No python solutions passed for E. lol.

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

    PyPy is 32 bit on CF, meaning it will use its big integers for any number that can't fit inside a signed int32. So in order to make PyPy run "fast" on that problem you need to somehow get away from directly working on numbers of size 2^60.

    at_f was super close to get AC 102859203 (during the contest) by avoiding big ints, but unfortunately he used a PyPy2 specific trick, and submitted his code in PyPy3. In order to make it work in PyPy3 he just needed to change int(...) to int(float(...)). He did that after the contest and he got AC 102862814.

    I did not participate in the round myself, but after the round I did try to solve problem E using PyPy. I've been able to make my solution run in $$$717$$$ ms in PyPy2 102882788. So while the problem is far from unsolvable in PyPy, it is not nice to solve using (32 bit) PyPy.

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

pog

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

I have a solution for F that might be more intuitive for people who are familiar with linear algebra.

It's clear that we are asked to find the lexicographically smallest vector basis of the given vectors. The general algorithm for finding the vector basis is to maintain the vector basis of the prefix $$$i$$$. Vector $$$i+1$$$ can be added iif it cannot already be created by some linear combination of the basis of the first $$$i$$$.

Because each vector has at most 2 1's, we only need to check whether we can create a pair or not. First consider the simpler case of $$$k=2$$$. Maintain the same graph as the editorial over each prefix $$$i$$$ vectors. Note that every pair of dimensions as one can be represented by some path between vertices i.e. $$$a$$$ to $$$b$$$. . . to $$$x$$$ represents a vector where only $$$a$$$ and $$$x$$$ are set. We only need to track connected components and and then check if $$$x_1$$$ and $$$x_2$$$ are in the same connected component before adding/ignoring vector $$$i+1$$$.

For the case $$$k=1$$$, note that any vertex in the same component can now become a vector with a single element, i.e. from the path ($$$a$$$ to $$$b$$$. . . to $$$x$$$ then adding $$$x$$$ again to create a vector with only $$$a$$$ set). Any component with one of these vertexes can be merged with any other vertex in any other component with another $$$k=1$$$ vertex. The solution is to maintain one component $$$g$$$ (initially -1) containing all vertexes with $$$k=1$$$.

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

    Can you please explain why we're finding the basis here? The span of the basis will give us $$$T$$$, but how do we know that we only need $$$1$$$s and $$$0$$$s as coefficients while taking linear combinations (to obtain $$$T$$$)?

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

      We're considering the all the operations mod 2 so any coefficient >= 2 will reduce to one < 2.

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

Nice round to end a terrible year. Happy New Year and high rating to everybody :)

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

Can anyone help me with the challenge of the first question? I have no idea how to proceed.

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

Why greedy solution for C works? Can anyone prove it?
Obviously we will get a palindrome-less string, but how do we now it is optimal?

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

    Without loss of generality suppose palindrome substring is of form $$$aa$$$ then we need to change either first $$$a$$$ or second $$$a$$$.Why changing second $$$a$$$ is optimal ? Because we can also break "future palindromes in that way",for example in $$$aaba$$$ changing to $$$azba$$$ is better than changing to $$$zaba$$$ .

    Now suppose substring is of form $$$aba$$$, the we have to change atleast one $$$a$$$ in it for sure . Changing second $$$a$$$ here also is optimal because we will avoid future palindromes (for example if string was $$$abaa$$$ , then changing second $$$a$$$ to $$$z$$$ will make $$$abza$$$ which will break 2 palindromes in single operation unlike changing the first $$$a$$$ to $$$z$$$ which will make $$$zbaa$$$ ).

    Also while changing a character we can always make it different from 4 neighboring characters as mentioned in editorial (because there are 26 characters). So in the end there we won't have any palindrome of size 2 or 3 and thus it's impossible to have palindrome of bigger sizes.

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

Can anyone explain this dp bitmask solution for C? Submission

Many of the top rated contestant I checked, used this way to solve it.

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

    The bitmask is based on the idea dp[i][j][k] where j, and k denote the whether the (i+1)th, (i+2)th character were changed or not(0 means changed, 1 means not changed or vice versa). Since, we have 26 possibilities and a character can at maximum match with 2, the status is what matters really rather than the value of the character.

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

Alternate approach for problem H :

Consider a digraph with $$$n$$$ vertices, where $$$i\to j$$$ iff $$$j$$$ appears before $$$A_i$$$ in $$$i$$$'s list, or $$$j=A_i$$$, then it's good iff $$$i\to A_i\to A_{A_i}\to \cdots$$$ are the only cycles in the digraph. i.e. consider a cycle in the input as a big vertex, then it's a DAG. This can be solved using a DP which is almost the same as counting DAG. (The state is the number of cycles of each length. For each state, iterator all its subsets as sources and use inclusion-exclusion.)

The complexity will be $$$O(S(n)\cdot n)$$$, where $$$S(n)$$$ is the maximum sum of numbers of subsets of all states, $$$S(40)=29400$$$.

Submission : 102862180

Of course, this can be "optimized" to exactly the same complexity as the intended solution, but due to the extra $$$n$$$ factors, it's not as pratical as the previous one.

»
4 months ago, # |
  Vote: I like it -24 Vote: I do not like it

Thanks for such an amazing round with such interesting problems (though I screwed C totally :P). But I just had one complaint regarding the stories in the problem statement, It would be great if you could add a divider or something like that which separates the stories, formal definitions, and other redundant stuff from the problem-statement next time :) . Screenshot-2020-12-31-014303

:P

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

Editorial this fast makes my day :))

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

Could some kind soul tell me why me solution for E did not pass? I believe my time complexity was O(60n) as well and do not see where my program is inefficient. My code

I tried pre-calculating some stuff but that too did not pass. (code)

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

    here: got rid of TLE

    however now it gets MLE on test 6, good luck with that :P

    1. memoized the part where you re-evaluate 2^x everytime.(it is expensive due to mod)
    2. added fast inp/output statement, lots of input.(also changed endl to '\n')
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a bunch! I will try to fix that and will remember these tricks for the future.

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

      I have implemented what you recommended (memoizing the 2^x part and fastio) and surprisingly that was enough for me (code) — a bit depressing that I couldn't find this in contest but thanks for helping and at least I will remember next time!

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

        You've submitted your code in C++14 (which on cf is 32 bit). Your code will run so much faster if you just submit to C++17 (64 bit)!

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

    Pre calculate the powers of 2 modulo M,(wont exceed 60), and try to remove some arrays like andv and orv, they are unnecessary. I think it will be enough.
    My O(60*n) java solution passed under the time limits (both during contest and multiple times after contest).
    A link here in case u want to see my solution.

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

    In your inner loop you are calling mod_pow(2,60-j-1) where

    long long mod_pow(long long a, long long b){
        long long ans = 1;
        for (int i=0;i<b;i++){
            ans = (ans*a)%MOD;
        }
        return (ans)%MOD;
    }
    

    This makes your solution 60 * 60 * n. In general you should never use this kind of mod_pow. Instead use

    long long mod_pow(long long a, long long b){
        long long ans = 1;
        long long apower = a;
        while (b){
            if (b & 1)
                ans = ans*apower % MOD;
            apower = apower*apower % MOD;
            b >>= 1;
        }
        return ans;
    }
    

    With this ^ your code will still not be a true 60 * n solution, but at least it will not be as insanely slow. To fix your TLE you should do three additional changes.

    1. Switch to faster IO (Just add cin.tie(0)->sync_with_stdio(0); first line in main)

    2. Submit in g++(64 bit) instead of the 32 bit version you are currently submitting in. 64 bit is pretty much always the better choice, especially for these kind of problems.

    3. Try to not call the mod_pow function in the inner loop at all to get a true 60 * N solution.

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

When is Hello 2021 going to be?

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

Thanks for the editorial just check for plagiarism.

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

Btw F is similar to SEERC 2017 D

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

    My team accepted this task, and by checking the code it looks like, I wrote it, and somehow I completely forgot about it :(

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

Does system testing use some kind of g++ optimization to make testing faster? I submitted 102853379 during contest which passed pretest 2 but now shows WA. Also it is passing now, but somehow only on my friend's account 102870632 but not mine 102870678

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

    Woah, really unfortunate. The same code passed in 3 out of 6 tries. But it could be UB, if so you can't really blame system for inconsistency.

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

    I guess it's line number 469 of your code. It should be dp[0][j] instead of dp[0][0]

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

      Yeah missed that completely, Thank you

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

In problem D can someone explain that why for k = 2 in this test case the answer is 7999, I believe it should be 7000.

test case

EDIT: Never mind I got my answer.

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

    Include the {1,2},{2,3},{2,4},{3,5},{3,6},{3,7} in the first color, giving the value 4000, and keep the rest of the edges in the second color giving value 3999. So total would be 7999

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

My solution for 1466I - Загадка сфинкса only uses $$$3n+2b$$$ queries, I think.

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

    I have a solution that uses $$$2n + 2b - 2$$$; you can read a writeup here.

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

had the worst contest ever lowest rating of my life

can anyone please tell me why my code is failing at test case 2 https://codeforces.com/contest/1466/submission/102857149

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

I think there is WA on problem D. 13th Labour of Heracles I mean wrong from the contest! so what if you make a non -conting graph with the same color? from example in first test case 4 3 5 4 6 2 1 3 1 4 3 when you have 2 colors you can color with color 1 the first edge(2 — 1) and the third (3 — 4) then you color with color 2 the second edge ( 3 — 1) so you have total of color1(3 + 5 + 4 + 6) + color2(4 + 3) = 25 > 22 I dont know if I am wrong the problem is that you DON'T take every time the biggest wieght of edge BUT you take the biggest of (the edge wieght minus (-) the wiegth of the vertex which are only adjective to the edge we select because we count this twice) and you can add more than one edge`s on each color so when you have 2 colors you can shade half color 1 half color 2 so more vertex wieght will count twice (or three or more times if you have more colors)

if the subgraphs must be connected sory, I am wrong if it is so but there is nothing like this on the problem

what it there is a linear graph 1 -> 10 -> 1 -> 9 -> 9 -> 1 then while you select color with the 2nd color the 10 -> or the 9->9 or both of them?

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

Happy New Year!

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

Here's a solution to 1466I - Загадка сфинкса which uses only $$$2N+2B-2$$$ queries, found by scott_wu.

The main idea is that we want to simultaneously bring down $$$B$$$ and $$$N$$$, so we'll maintain a "diagonal" of upper bounds on the input elements in a stack, similar to the editorial solution. We'll actually think of the stack as a sort of cyclic queue, because we'll repeatedly take the item with the highest upper bound and try to reduce it to the next item on the diagonal, so we'll actually phrase this as a deque. More specifically, we will maintain the following:

  • A current (inclusive) lower bound $$$lo$$$ of our maximum element, initialized to $$$0$$$.
  • A current bit index $$$b$$$, initialized to $$$B-1$$$. It is guaranteed that $$$lo$$$ is a multiple of $$$2^b$$$.
  • A deque of indices $$$d$$$, such that when 1-indexed, $$$lo \le a_{d[i]} < \operatorname{truncate}(lo, 2^{b+i}) + 2^{b+i}$$$, where $$$\operatorname{truncate}(a, b) = \lfloor a/b \rfloor \cdot b$$$. Equivalently, $$$lo \le a_{d[i]} \le lo \mid (2^{b+i}-1)$$$, where $$$\mid$$$ means bitwise or. Note that, if $$$lo$$$ has several one bits at bit $$$b$$$ and above, then several of these upper bounds may be equal; this is a feature! We could equivalently think of them as a run of elements with the same upper bound, but it's not necessary for the analysis. The deque is initialized to $$$1..n$$$, because all elements are at most $$$2^{b+1} = 2^B$$$.

Then, in each step, we will query $$$lo + 2^b - 1 \overset{?}{<} a_{d[-1]}$$$. Here, $$$d[-1]$$$ refers to the back of $$$d$$$; this is the element with the worst upper bound, and we'll try to reduce it as much as possible.

Intuitively, if we get "no", then we have a tighter upper bound on $$$a_{d[-1]}$$$, so we can cycle it to the front and decrement $$$b$$$. If we get "yes", then our lower bound increases to $$$lo + 2^b$$$, and if $$$lo$$$ increases past some upper bounds, we can eliminate many elements from the front of $$$d$$$ as too small to be the max. In particular, after our first "yes" answer, each following query will actually be querying $$$lo + 2^b = \operatorname{truncate}(lo, 2^{b+1}) + 2^{b+1}$$$, the upper bound of the front of the deque, so a subsequent "yes" will remove at least one item.

More formally,

  • If we receive "no", then $$$lo + 2^b - 1 \ge a_{d[-1]}$$$, which would be the correct upper bound for index $$$0$$$ of our deque, so we can set $$$d \gets d[-1] + d[1 \ldots -2]$$$ and $$$b \gets b-1$$$.
  • If we receive "yes", then $$$a_{d[-1]} \ge lo + 2^b$$$, so we can update our lower bound on the maximum to $$$lo + 2^b$$$. Furthermore, this presents an opportunity to cull away a run of items which are guaranteed to be to small. In particular, if $$$lo$$$ has trailing ones at bits $$$b$$$ through $$$b+i-1$$$, then $$$lo + 2^b = \operatorname{truncate}(lo, 2^{b+i}) + 2^{b+i}$$$, so we can chop off indices $$$1 \ldots i$$$ from our deque because they are guaranteed to be too small to be the maximum. More formally, assume there are $$$i$$$ one bits in $$$lo$$$ starting at index $$$b$$$ ($$$i \ge 0$$$). Then, we can do $$$d \gets d[i+1 \ldots -1]$$$, $$$b \gets b + i$$$ to compensate, and $$$lo \gets lo + 2^b = \operatorname{truncate}(lo, 2^{b+i}) + 2^{b+i}$$$.

We will actually continue this algorithm past $$$b < 0$$$ (all our math still works, we can just query $$$\lceil lo + 2^{b} \rceil - 1$$$). We can stop once $$$b + len(d) \le 0$$$, because then $$$lo \le a_{d[\cdot]} < \operatorname{truncate}(lo, 2^{b+len(d)}) + 2^{b+len(d)} \le lo + 1$$$, so we can output $$$lo$$$.

To analyze the runtime, note that each "no" query reduces $$$b + len(d)$$$ by 1, but each "yes" query doesn't change $$$b + len(d)$$$; we need some way to bound the number of "yes" queries. The best monovariant is the number of 0-bits in $$$lo / 2^b$$$, treated as a $$$(B-b)$$$-digit binary number. This increases by exactly $$$1$$$ for each "no" query, and decreases by exactly $$$1$$$ for each "yes" query. Thus, the quantity $$$2(b + len(d)) + \# 0$$$ decreases by exactly $$$1$$$ each query. It starts at $$$2(B-1 + N) + 1$$$, and ends at least $$$2 \cdot 0 + 1$$$ (there is at least $$$1$$$ 0-bit at the last step, since the last query must be a "no"), so we use at most $$$\boxed{2N+2B-2}$$$ queries.

Code: 102868071; this code takes a few implementation shortcuts. Instead of storing $$$lo$$$, we actually store $$$lo + 2^b - \epsilon$$$, i.e. the query string, and update it as we go. Also, $$$b$$$ and the deque are reversed versus this writeup.

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

    On the question of optimality: ksun48 wrote a brute force for $$$N = 2$$$ and the pattern was pretty nontrivial. In general, I think constant-factor optimizing worst case bounds is pretty messy and doesn't typically have a nice closed form, because you have to very carefully split your cases up along nontrivial boundaries. It's very hard to get nice lower bounds beyond the basic entropy arguments.

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

      It's not too hard to prove a lower bound of $$$n + b - 2$$$ (explained below). There's also a simple upper bound of $$$n + 2^b - 2$$$ (keep asking whether some $$$a_i$$$ is greater than $$$lo$$$; if "no" then we can throw away this $$$i$$$, and if "yes" then we can increase $$$lo$$$). So $$$n + b - 2$$$ is essentially sharp for fixed $$$b$$$ (we can't even hope to prove a lower bound of $$$1.001 n - 1000$$$ for all $$$n$$$, $$$b$$$, let alone $$$2n + 2b - 2$$$).

      Let's make explicit that this problem is equivalent to a simpler game. The state of this game is a multiset $$$P = [p_1, \ldots, p_n]$$$ of integers. There are two players X and Y. X wins when $$$\max P \le 1$$$, and Y wants to delay this as long as possible. In each turn, X picks some $$$i \in [1\ldots m]$$$ and $$$1 \le r < p_i$$$. Y then either caps $$$p_i \leftarrow r$$$, or subtracts $$$r$$$ from every element of $$$P$$$. Let's write $$$f(P)$$$ for the number of turns X needs to win.

      A state in the original problem determines a multiset $$$P$$$ where $$$p_i$$$ is (best known upper bound on $$$a_i$$$) — (global lower bound) + 1. Let's write $$$n \times [p]$$$ for the multiset consisting of $$$n$$$ copies of $$$p$$$, so that the answer to our problem is $$$f(n \times [2^b])$$$.

      Actually X can always take $$$i$$$ such that $$$p_i$$$ is maximal (as in your solution). To see this, suppose $$$p_i \ge p_j$$$ and X picks $$$(j, r)$$$. Then $$$(i, r)$$$ would also have been a valid play; we claim it's at least as good as $$$(j, r)$$$. If Y responds by subtracting, then this is clear, since it doesn't matter what index we picked. If Y responds by capping, then this is because $$$r, p_j$$$ are no bigger than $$$r, p_i$$$ (here we use the fact that $$$f(P) \le f(P')$$$ if $$$P \le P'$$$ pointwise in some order).

      So the problem of finding an optimal strategy reduces to finding the best $$$r$$$ for a given multiset $$$P$$$; this is where I am stuck. Taking $$$r$$$ big is problematic if B caps, and taking $$$r$$$ small is problematic if B subtracts. We probably want to take $$$r \approx \min P / 2$$$, except when $$$\min P$$$ is considerably smaller than the rest of $$$P$$$ in which case we should take $$$r$$$ a bit bigger. The solution you describe takes $$$r = 2^b$$$, but of course in general there is no reason to expect the optimal $$$r$$$ to be a power of two. If $$$P = n \times [p]$$$ then it seems to make sense to take $$$r$$$ a bit smaller than $$$p/2$$$.

      I ran calculations for small $$$n$$$ (where we can compute optimal strategies using some binary search and memoization). Here it seems like $$$f(n \times [p]) \approx c(n, p) \log_2 p$$$ where $$$c(n, p) \in (1, 2)$$$ decreases with $$$p$$$ and increases with $$$n$$$. (E.g. X needs 20 turns starting from $$$[61364, 61364]$$$, but only 19 starting from $$$[61363, 61363]$$$, and $$$19 \approx 1.22 \log_2 61363$$$.) My guess is that $$$\limsup_p c(n, p) < 2$$$ for any fixed $$$n$$$. In general I haven't found any counterexample to $$$f(n \times [p]) \stackrel{?}\le n + 1.5 \log_2 p$$$, but this is maybe a bit optimistic.

      As promised, let's prove $$$f(n \times [2^b]) \ge n + b - 2$$$ for $$$n, b \ge 1$$$. If $$$b = 1$$$, then this is clear, since X must take $$$r = 1$$$, and Y responds by capping just one $$$p_i$$$. If $$$b > 3$$$, then either $$$r \le 2^{b-1}$$$ or $$$r \ge 2^{b-1}$$$. In the first case, Y responds by subtracting, and the state of the game is no better than $$$n \times [2^{b-1}]$$$. In the second case, Y responds by capping, and again the state of the game is no better than $$$n \times [2^{b-1}]$$$.

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

    Nice solution

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

Where could I find the solution of the challenge portion solution!!!

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

.

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

My O(60∗N * log(N)) Java solution for E got TLE 3 Sec was a tight limit

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

Aha,Happy New Year Codeforce

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

Can anyone help me with the challenge problem of A which is mentioned above where n,x<=10e5? Any hints?

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

In problem E, Apollo vs Pan, Editorial distributed the sum formula from one combined version to bracketed version. Whats that particular topic in maths? I want to know the proof of that. Can anyone redirect me?

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

It's a nice contest. Participated in a contest after so many months. Iam glad I solved upto D but I was too slow. By the way did anyone have an update about hello 2021 contest.

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

what should i change in my solution C to get ac 102883253 , thank you and HAPPY NEW YEAR

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

    The issue with your solution is with something this string: abab

    There is about 0.1 probability that after 1st 2 operations it will become something like abYY which is high enough to have WA.

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

I don't think you should use O(..) to analyze a exact value in problem I.

»
4 months ago, # |
  Vote: I like it -34 Vote: I do not like it

Can someone tell me why my approach is wrong for question B

#include <bits/stdc++.h>
using namespace std;

#define IOS	 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long int
#define si(x) scanf("%d", &x)
#define sl(x) scanf("%lld", &x)
#define pi(x) printf("%d\n", x)
//for debugging
#define deb(x) cout << #x << " " << x << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define umii unordered_map<int, int>
#define mii map<int, int>
#define pqb priority_queue<int>					  /* Max heap*/
#define pqs priority_queue<int, vi, greater<int>> /* Min heap*/
#define setbits(x) _builtin_popcountll(x)		  //finding the no. of set bits
#define zrobits(x) _builtin_ctzll(x)			  //finding the no. of zeroes after the last one
#define mod 1000000007
#define inf 1e18
#define ps(x, y) fixed << setprecision(y) << x
#define mka(arr, n, type) type *arr = new type[n];

#define f(i, n) for (int i = 0; i < n;i++)
#define tr(it, a) for (auto it = a.begin(); it != a.end(); it++)
#define cd(x, y) int x, y; cin >> x >> y;
#define w(x)  int x;cin >> x;while(x--)
#define ws(x) int x;scanf("%d", &x);while(x--)

typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
const int MAX = 26;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //for shuffling of array
void av()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}
int gcd(int a, int b){
	if(a==0)
		return b;
	return gcd(b%a,a);
}
int LCM(int a, int b){ 
	int lcm = (a*b) / gcd(a,b);

	return lcm;
}

void solve(){
	int n;
	cin>>n;

	vi a;
	set<int> s;

	f(i,n){
		int in; cin>>in;
		a.pb(in);
		s.insert(a[i]);
	}

	if(n==1){
		cout<<1<<endl;
	}
	else{
	       if(a[n-1] != a[n-2]){
			a[n-1] = a[n-1] + 1;
			a[n-2] = a[n-2] + 1;
		}

		for(int i=0;i<n-1;i++){

			if(a[i] == a[i+1] && s.find(a[i] + 1) == s.end()){
				a[i]++;
				s.insert(a[i]);
			}		
		}
		s.clear();
		f(i,n){
				s.insert(a[i]);
		}

	        cout<<s.size()<<endl;
	}
}

int main()
{   
	IOS;
	av();
	w(t){
		solve();
	}
	return 0;
} 
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i did not get the logic behind your solution, can you explain.

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

Happy New Year In advance. At midnight of 31st December 2020 was asking me, So, tell me where shall I go? To the left ...? Where's nothing right Or to the right ...? Where nothing is left.

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

Can someone explain dp approach for problem C. Thanks in advance!

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

    See TMWilliamLin submission, maybe you will be able to understand that.

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

did anybody get the idea of B soln 1?

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

Can anyone explain what's the problem with my approach for problem B. code I think this would be approach for many newbie coders,understood the editorial but can't figure out what's the problem with this solution . PLEASE HELP

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

Why did this bit of code give me TLE? isn't if-else O(1)

		if (!used[t]) {
			used[t] = 1;
			ans++;
		} else {
			if (!used[t + 1]) {
				used[t + 1] = 1;
				ans++;
			}
		}

I was able to fix it but I wouldn't have guessed this was the issue

                if (!used[t]) {
			used[t] = 1;
			ans++;
		} else if (!used[t + 1]) {
			used[t + 1] = 1;
			ans++;
		}
  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    You got TLE not because this bit of code but because of vectorused(200005)

    It costs 200005 unit of operations in each of the T tests

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

      I don't know why but I was under the impression that initialization is also O(1). Thank you for clarifying

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

.

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

Great contest and nice editorial!!!!!

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

Hello everyone! I think I have a counterexample for problem 1466B - Улучшения в последнюю минуту. I too came across with this approach "we conclude that the result is the number of different elements in the input increased by the number of intervals containing at least one duplicate.", but the reason why I didn't implement it is because I came up with the following example "44566": The previous approach yields 5, since in the beginning there are 3 different numbers (4,5,6), and there are 2 duplicate intervals. However, the real maximum possible number of different notes is 4 (an example being "45676").

Also, I don't think I quite understood the approach of 1466D - Тринадцатый подвиг Геракла. Is it only choosing and edge per new colour?

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

    $$$[4, 4, 5, 6, 6]$$$ forms one interval "maximal contiguous intervals of values".

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

For problem C, how does one show that the greedy strategy is optimal (i.e. it requires minimum number of character changes)? The proof stated seems incomplete — it only shows that we can always change the positions to some character which is not the same as the four neighbours!

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

    how did you got LGM with rating of expert ...CF should look into this its like decepting people

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

      You can change your color and username at the end of each year.

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

I faced an issue when I submitted the solution of B. Same test case gave different answer on my terminal and on codeforces online judge. Here is my code: 102850117

output on my terminal: 5 2 6 1 3 // matches the correct output

output on online judge: 5 1 6 1 3 // 2 expected after 5

Could anyone guide me what is causing this abnormal behaviour ?

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

    vector<int> v(n); You're not initializing v. Just change it to vector<int> v(n, 0); and you'll be fine.

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

now 4th question was not clear ..like you should have clearly mentioned that k coloring means that we can use k colors to color the graph in anyway we want ..from examples I guessed that we r using 1 color to paint all edges and then every time we we use (n+1)th color then we use that color to paint any "1" edge in graph ...and now if that coloring(edge) is diving graph into 2 components then we have to consider max of 2 ....and in that case this proof will also not hold ...I could be under 3000 rank if you would have mentioned that

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

    Absolutely not. The question was clear.

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

    "from examples I guessed that we r using 1 color to paint all edges and then every time we we use (n+1)th color then we use that color to paint any "1" edge in graph" I don't understand what were you trying to say here at all but maybe next time try looking at the statement instead of guessing from examples.

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

Will Editorial be translated into Russian?

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

In final standings, we can see tourist finished A-H the problems in 1:47 but maroonrk finished A-H in 1:36 yet he was second!

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

Any hint for the challenge of problem C?

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

    Think of dp solution and segment tree.

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

VIDEO TUTORIAL LINKS FOR THE FIRST and the THIRD PROBLEMS OF THIS ROUND. I HAVE TRIED MY BEST TO EXPLAIN IN DETAIL. I HOPE YOU WILL ENJOY THE VIDEOS . Problem A https://www.youtube.com/watch?v=nPW5a8lP-XA&list=PLBOdZ5fF0sd5xAnNiIIxAclSw5UVYTslP

Problem C https://www.youtube.com/watch?v=sR4t4pnouQc&list=PLBOdZ5fF0sd5arflKINPPza-DBI_82OWt&index=3

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

I posted my post-contest stream (explaining A-G) on YouTube: https://youtu.be/KOvQUwtqDis

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

Editorial's solution to problem D gives WA. It prints too many times the sum.

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

    I also understood why the given solution works and it might be a sort of proof.

    The sum of degrees in the tree = 2n-2 (every edge adds 2). For each vertex v starting from the maximum weights, we add its weight deg(v)-1 times. It means that in total we change 2n-2-n = n-2 edges. And this is precisely the number of new colors we have to add (2,..,n-1). This means that every added color gets the maximum possible weight.

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

    Fixed. By an accident, I pasted a solution for the initial version of the problem.

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

Alternative Solution for G. Song of the Sirens
We can solve it in $$$O(\sum log_2({\sum}))$$$ along with other linear terms. We can see that $$$t_i$$$ is periodic with $$$2^{(ind-i-1)}$$$ where ind is the index of the song. With this observation, in some query string, we must have alternate $$$t_0$$$. Now, if we remove all alternates, we must have alternate $$$t_1$$$ and this goes on recursively till depth $$$log(\sum)$$$. Now, finally, we would be left with a single character always and we can find the number of occurrences by simply storing prefix sums. For help, This is my submission. The code is a bit messy, but it should help you.

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

    Thinking more about it, the concept can be generalized to be solved in linear time with some tricky optimization. The thing to note is this solution does not require KMP or any other such algorithm. Optimized code

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

      $$$S \cdot |s_0|$$$ doesn't look like a linear term.

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

I am trying to understand the solution for D, have gone through the editorial multiple times but still not able to. Can someone please explain their thought process as to how they arrived at the provided algorithm / solution ? Thanks !

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

    At first I understood that in optimal solution subgraphs of all colours must have only one connected component, because if we have two or more we use only one with the biggest weight and all other we can use in another colours. Then I decided to construct solution from 1 colour to n — 1 colour. When we add next colours we just pick a vertex and recolour all edges by the way of one of her edges. By this operation we only add to our sum weight written on picked vertex.(Because all that another vertices are still in one colour, but we incremented number of colours for our picked vertex.) And then it is obvious that if we want max result on every step we must pick the vertex with max weight. Notice that vertex can have one(in this case it cannot be picked) or more than two adjacent edges(in this case we can pick this vertex more than once).

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

Hi, everyone. Question of Task D.

Can you please explain me, why in this test we have for 2-color right answer 41 + 10 = 51? 1 7 4 5 5 4 8 5 10 1 2 2 7 7 3 3 4 7 5 5 6 What edge we can we draw in 2-color? I think in this situation we get 2 components of color-1 and must take only one of them.

Thank you very mush

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

For C, why can you only look at the length 3 ones?

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

    If palindromes length is $$$2n + 1$$$, for some $$$n > 0$$$, then the middle three characters form a palindrome. For example, ab**cac**ba.

    If palindrome length is $$$2n$$$, then the middle two characters form a palindrome. For example, bcc**bb**ccb.

    Thus, if we remove all palindromes of length $$$2$$$ and $$$3$$$, we won't have any palindromes of greater length.

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

Awesome editorial, such detailed discussion and approach to the solutions.

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

In problem D:

in definition of k-coloring: "Let us define its k-coloring as an assignment of k colors to the edges so that each edge has exactly one color assigned to it. Note that you don't have to use all k colors."

Constant mapping of all the edges to the color 1 would not contradict the definition. Would it? :-)

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

Could anyone explain me the DP approach for problem C, I have solved it using greedy by myself but didn't grasp the ideal of DP solution. Thanks

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

For problem E , i have used the same method which is given in this Editorial but still i am getting TLE in 2nd TC..

Here is my Python 3 solution. Can anyone please help!

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

    If we calculate the number of operations, it's $$$n$$$ (outer loop) * $$$60$$$ (inner loop) * $$$\log(10^9+7) \approx 30$$$ (the pow()'s), which is about $$$1800 \cdot 5 \cdot 10^5 \approx 0.9 \cdot 10^9$$$, which is too much for python to handle. Even some Java solutions were TLE'ing, and C++ solutions without fast input/output

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

Can anyone more reference material , as which is given in Qn 'E'

i.e. more on bitmasking and bitwise operators , like the formulas used in the solution .

Any help is apprecited .

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

[deleted]

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

Hi, In problem E — Apollo versus Pan. my solution is wrong because the modular arithmetic. (1) s_and[i] = (s_and[i] + (sbit[j] * (1<<j)%mod) % mod) % mod; (2) s_and[i] += (1LL << j) % mod * sbit[j]; (tutorial code)

Expression (1) is wrong and (2) is correct. Why?

I have replaced 1<<j by 1LL<<j and was correct test 1. But, it generates overflow in another test cases.

Thanks.

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

Can someone explain how to solve challenge of problem B?

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

    Sort numbers by $$$x_i + k_i$$$, then when analyzing the sequence, change $$$x_i$$$ to the smallest value $$$y_i$$$, such that $$$y_i$$$ hasn't occurred yet, and $$$x_i \leq y_i \leq x_i + k_i$$$. This can be done in $$$\mathcal{O}(n \log n)$$$ with lower_bound on set.

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

      Why sort by xi+ki?

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

        $$$x_i + k_i$$$ is an upper bound of what we can achieve. As we keep replacing $$$x_i$$$ with the smallest possible option, it is intuitive to analyze the elements in this order (because while replacing in some sense, we are not taking what the next elements could take).

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

Can someone explain how to solve challenge of problem A?

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

Question for the example in problem C: Why for this string bbbbbbb, the answer is 4? I guess babcbdb is a valid answer; and the number of letters is 3?

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

pragma GCC optimize("Ofast")

include <bits/stdc++.h>

define ll long long

define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cerr.tie(NULL);

using namespace std; void solve(string s,int n){ for(int i=0;i<=4;i++){ if(s.substr(0,i)+s.substr(n-4+i,4-i)=="2020"){ cout<<"YES\n"; return; } } cout<<"NO\n";

} int main() { fastio int t; cin>>t; while(t--){ int n; cin>>n; set s;

int a[n];
for(int i=0;i<n;i++){
    cin>>a[i];
}
int res=0;
for(int i=1;i<n;i++){
    if(a[i]==a[i-1])
        a[i]+=1;
    cout<<a[i]<<endl;
}
set<int> s;
for(int i=0;i<n;i++)
    s.insert(a[i]);

cout<<s.size()<<endl;

}

return 0;

}

What is wrong with my solution of 1466B?

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

The solution 2 of the problem b is wrong.

The explanation says:

"where we analyze the elements in nondecreasing order"

But then the code doesn't actually sort the elements in nondecreasing order. Sample test case that gives wrong result:

1 3 5 6 5

Solution one gives correct result (3) solution two gives wrong result (2)