flamestorm's blog

By flamestorm, 8 months ago, In English

We hope you enjoyed the contest!

1950A - Stair, Peak, or Neither?

Idea: SlavicG

Tutorial
Solution

1950B - Upscaling

Idea: flamestorm

Tutorial
Solution

1950C - Clock Conversion

Idea: mesanu

Tutorial
Solution

1950D - Product of Binary Decimals

Idea: flamestorm

Tutorial
Solution

1950E - Nearly Shortest Repeating Substring

Idea: mesanu

Tutorial
Solution

1950F - 0, 1, 2, Tree!

Idea: flamestorm

Tutorial
Solution

1950G - Shuffling Songs

Idea: SlavicG

Tutorial
Solution
  • Vote: I like it
  • +28
  • Vote: I do not like it

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

thanks for the fast editorial

although they are all empty :(

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

    They are updated now with solutions

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

      still waiting for G.

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

      in problem E why we are checking strings of length l from either prefix or suffix why it cannot be any substring with length l from middle or anywhere else in the string ?? can someone please answer this

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

        notice this, there can be atmost 1 difference since we can just check both prefix and suffix, we already have two choices, if first doesnt work then check second, if both doesnt work then a high lenght of the string is required

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

A fun little exercise for G: Shuffling Songs. Consider this code that finds the longest hamiltonian path of a subset of vertices. What is the time complexity of this code? Is it $$$O(N^3 \cdot 2^N)$$$ or $$$O(N^2 \cdot 2^N)$$$ or $$$O(N \cdot 2^N)$$$? (With proper proof/arguments).

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

    It's O(2^n*n^2) because for each bit mask you iterate every possibile pair of songs.

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

Problems were very challenging .. liked them even though not solved them but they were good .. + lightning fast editorial

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

F can be solved in O(1), so why a + b + c <= 3*10^5??

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

    Do you mean O(log(a)) cause I can't figure out an O(1)

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

      Depends on what you count as a primitive operation, but here's an example of a solution that can be interpreted as O(1): 253827308

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

        can you correct the logic in this one , for 14641 i couldn't get the code right for 14641 so i edited it , though it still failed 253823896

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

        __builtin_popcount(n) has a complexity of log(n). As you are calculating __builtin_popcount(a), your code should be considered as O(log(a))

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

          First of all, my code calls clz, not popcount. Secondly, it can be misleading to think of it as $$$O(\log)$$$. Explicitly looping over the bits is substantially slower because modern processors have special instructions for both clz and popcount.

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

            sorry for the confusion with clz. Interesting, learnt something new, ty

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

        can you please explain what's the logic behind Padding variable ?

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

          I first build a complete binary tree out of nodes of degrees 0 and 2. The last level may be partially filled, and padding denotes how many nodes of degree 1 can be inserted immediately above leaves without increasing levels. After that, the second phase begins where every c insertions of nodes of degree 1 immediately above leaves increase the number of levels by 1.

          UPD: I thought of this variable name because padding usually comes between content (nodes of degree 2) and border (nodes of degree 0).

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

            but after subtracting padding, what does increase of (c-1)/c mean b/c i understand that it is 1 degree nodes ,can u please explain ??

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

              It's a common way to round the division result up.

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

    I know it existed, but I didn't find the optimization from $$$\mathcal{O}(a+b+c)$$$ to $$$\mathcal{O}(\log(a))$$$ (or $$$\mathcal{O}(1)$$$) very interesting, and the core idea is the same.

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

    'cause it is div4 :)

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

    For this constraint, queue solution is also accepted. Queue Solution (AC)

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

thanks you for the quick editorial and good round!

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

Hello I am gokula kannan siva ji

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

Hey! I am solving G using DFS to find the component of largest size. Why is it giving WA on test 5. Please look at my Submission

Detailed approach:

create a graph with vertices as songs from 1 to n. Two vertices are connected if they have a common artist or genre. Using dfs, find the largest component. Is my approach Wrong??

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

    Consider

        a
        |
    b-c-d-e-f-g
      |___|
    

    Is this graph connected? Can you find a way to arrange all vertices in order?

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

      so how to approach this? i read about hamiltonian path! but i didnt get it! please explain

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

        [EDIT: This solution is incorrect, check end of this comment]

        I also did with DFS and DSUs. The trick is do DFS from a node and find the length of the longest "path" from each of them. You can do this by returning (max path length + 1) at each node.

        ll dfs(ll node, vector<vll> &nb) {
            dfsvis[node] = true;
            ll plen = 0; 
            for (auto &n : nb[node]) {
                if (dfsvis[n]) continue;
                plen = max(plen, dfs(n, nb));
            }
            dfsvis[node] = false;
            return plen+1;
        }
        

        You will notice that I'm setting dfsvis[node] = false; while exiting the node. This ensures that every path is tried and non-optimal results aren't returned. (Think what if a node that is part of the longest path is visited before we can check for it, that's why we unvisit it)

        However only this solution will give a TLE when all 16 songs have same genre and writer coz you check every possible path. To counter this, I checked if the max length that I'm getting is the max possible. If it is no point in keeping checking.

        Now what is the max possible length? The size of the connected component! I found it using DSU, you can use other methods. To check, at each branch, I add the max length of that branch and the number of visited node and see its it's equal to the size of the connected component.

        Submission: 253849577 [HACKED]

        EDIT: This submission has been hacked and I discovered that my code has n! worst case time complexity.

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

      Let's suppose vertex a and b both have first string(genre) same as first string of c then we can arrange like a-b-c-d-e-f-g.

      consider other case like a,d both have second string(writer) same as second string of c then we can arrange like b-c-a-d-e-f-g.

      so trying all possible case i guess we always find some arrangement

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

        You don't need to suppose anything. The graph I shared explicitly means that there is nothing common between vertex $$$a$$$ and any other vertex except vertex $$$d$$$. How would you find an arrangement then? Hint : It's not possible.

        But if you stick to your strategy of finding maximal connected component size, you'd get an incorrect answer.

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

      This isn't a good counter-example since this graph cannot exist (a must have an edge with at least one of c/e, or c must have an edge to e). Add an edge between c and e, and that suffices for a graph with no Hamiltonian path under the constraints of this problem.

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

        Fair enough. The OP had an impression that their algorithm must be true for general graphs as well, hence I randomly constructed a counter example.

        But you're correct, given the context of this problem, there should be an edge between c and e. Fixed.

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

what would be the rating for problem E? just wondering

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

thanks for the solutions!

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

I loved the problem G. The constraints were a subtle hint already but I tried to build a graph between connected components (an edge between song $$$i$$$ and $$$j$$$ iff genre or artist is same). After looking at the graph, it was pretty evident it is a Hamiltonian Path bitmask DP. Figuring it out was very fun! Great problemset overall for Div4 users.

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

why is my submission for E wrong tho i tested them all? ;-; here's my submission: 253815920

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

Can anyone explain the reasoning behind the Time complexity Anaylsis given for D? I didnt get the idea or how those cubic/quantic equations got formed.

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

can someone explain solution to problem E

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

    brute force check for every factor of n

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

    Notice that the answer can only be a divisor of n, so we have to calculate all the divisors.

    Now Try to form a new string (formed by concatenation of a prefix of s), Example s= "abba" and divisor d= 2; prefix = "ab". The new formed string will be "abab". (do the same thing with suffix ="ba") Now compare the 2 formed strings with s, if we find more than 1 difference we move on to the next divisor, else, d is our answer.

    Hope this helps.

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

      thanks got it now

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

      why do we only need to consider concatenation of a prefix or suffix?

      why do we ignore a potential substring in the center?

      sorry! i just started CF

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

        u can take whatever 2 substrings you want but they should not be overlapping

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

          No. (let d be a divisor of n) The strings must start from an index divisible by d and with length d .

          this comment explains in more detail

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

            i supposed that the lenght of substring is a divisor of n

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

    One straightforward optimization can be that once i crosses n/2, you can be sure that the answer is n.

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

I was a little disappointed with the pretest in task G. It was clearly my fault for underestimating the problem. But I was disappointed that out of 38 pretests, not a single one made simple DFS got Time Limit Exceeded in a task where you intended dp using bitfield as the correct answer.

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

    253766687 << Yes, here are my code with dumb approach, and it passed during competition, and hacked immediately I showed this code to other ones.

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

Explain why it is impossible to find a component in G with the maximum number of vertices. Essentially, vertices have two types of edges, those connected by author and those connected by genre. If there are > 2 edges at a vertex, then some vertices will form a cycle, where the order is no longer important.

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

For problem D why cant we just factorize the given number and if the prime factorization contains any digit which are not binary decimal then we will multiply them together lets call it as Product and the numbers which are binary decimal we will leave them as it is. Now if the Product is binary decimal then answer is yes else no ?

if the number is already a binary decimal we will simply return yes

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

    Consider $$$12321 = 3^2\cdot 37^2$$$.

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

      Yeah, it quickly becomes slow if n is bigger than 10^5

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

    I've also done it like that. First prime factorization, and if some primes are not "binary" ones then just brute force it to check if there is a way to multiply them to obtain the binary number. Prime factorization is O(sqrt(n)) and there are at most 6 primes to brute force under 100000.

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

Can someone please try and hack my E solution. Submission Link

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

My solutions to problems A

code

My solutions to problems B

code

My solutions to problems C

code

My solutions to problems D

code

My solutions to problems E

code

F sadly I didn’t solve it, but I had the logic for creating a binary tree, I just didn’t have time to implement it))

My solutions to problems G

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

How can this solution for D have tle,its constant time

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

253803810 Can someone help me why this code for F doesn't work.. My logic was that if c=a+1, then answer is possible... So first try to find the minimum height of the binary tree that could be made with a : it will turn out to be ceil(log2(a))+(ceil(log2(a))==floor(log2(a))). Now to maintain the same no of leaf nodes c, for each of the leaf node in the above binary tree formed with a add a single child to each of the leaf...so basically for every leaf node filled at the ith level of height, the next addition will increase the height by one after all leaf in that level is given a child...

this seems to be right but why doesnt my solution work? please help me

edit i solved it...it was just a small issue...instead of dividing it by no of leaf node for this tree, i divided it by no of leaf node of a complete graph... answer (O(1) solution): 253841056

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

can someone explain me this approach for problem d ? 253830700

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

    bitset<5>(i).to_string() is equivilant to bin(i)[2:] in python

    it returns the binary of i as a string then we use stoi (string to integer) to turn it back to an integer so we can divide with it. i used something like that in my code 253793921

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

In solution of E why are we only checking for prefix or sufix of length l and not and string of length from the middlee?

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

    because atmost 1 char can be different, so if the string is valid we can clearly see that the repeating substring completely matches with the characters of S in either a prefix or suffix or both

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

F can be solved in O(1) if you know the property of complete binary trees (number of nodes at each level increases by a factor of 2) and a little bit of maths.

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

253824980

WHY IS THIS WRONG QUES 4

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

thanks for very fast editorial.

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

Why didnt Dp worked for the solution D. Its shows TLE. Here is my solution : https://codeforces.me/contest/1950/submission/253751070. PLEASE HELP

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

after knowing that c == a+1 in F the problem became very easy and solved it in 3 lines submission. the leaves are what bothered me when solving it in the first place

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

253841056

My solution in O(1) using maths...

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

I believe on question E, instead of trying for all n, we can first compute the divisors in O(sqrt(n)) with the following: go until i * i <= n and, if n % i == 0, add to the divisors array not only i, but also n / i.

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

2nd question was very bad question.I hate such type of questions

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

How can we solve G using DSU, basically find size of largest component ?

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

Can anyone share the solution for D by DP?

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

Thank you so much for answering my question fast during the contest (I indeed am very bad at reading) and for providing very high quality problems (I only did C D F but they were insanely interesting).

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

Another weak pretests day? What is it with codeforces and weak pretests.... (problem E)

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

Prb-E, Can someone tell time complexity of my solution, my understanding says it's same as author(All numbers at most 10^5 have at most 128 divisors, so this will take ∼128⋅10^5operations, which is fast enough), but I am missing something, https://codeforces.me/contest/1950/submission/253828002

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

nvm, my assumption was wrong

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

.

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

Adding my live coding + commentary here: https://www.youtube.com/watch?v=kQOWiTvgah0&ab_channel=DecipherAlgorithmswithSaptarshi

I'd be glad if somebody finds it beneficial!

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

Hi, all why my solution G will WA 5? https://codeforces.me/contest/1950/submission/253786544 it also uses bitmask, and I think the order doesn't matter. Thanks for your help!

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

    Oh, I find a example for WA 5: 7 a b c b c d c e f e f g z d

    answer should be 1 not 0

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

Is it possible to solve the problem D using sieve? I'm trying to factorize the primes and then check if I can make some pairs decimal digits

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

    Here is a simpler solution for D : https://codeforces.me/contest/1950/submission/253868766 I thought all possible combinations of 0 & 1 less than 1e5 from which dividing the number and checking if it is divisible by these numbers the answer is okay or not. Also I divided in descending order other wise number like 1001 will cause problem as it will be divided by 11 and leave some number which is not 1. I hope it helps.

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

i just want to know that for e question,i submitted my code in c++17 and it got wrong answer on test2,then after contest i checked that test and it was giving right answer on my visualstudiocode compiler and then i submitted that same code in c++20 and it got accepted,now i want to know why is it so and am i responsible for this mistake of choosing compiler or is it a error from codeforces;s side

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

Here is a simpler solution for D : https://codeforces.me/contest/1950/submission/253868766 I thought all possible combinations of 0 & 1 less than 1e5 from which dividing the number and checking if it is divisible by these numbers the answer is okay or not. Also I divided in descending order other wise number like 1001 will cause problem as it will be divided by 11 and leave some number which is not 1. I hope it helps.

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

Problem G was great

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

tourist getting WA1 on A is really funny to me for some reason

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

Wrote G for 80 minutes, 3KB of non-template code, only to find I went in the wrong direction. I tried to build a bipartite,one side is Genre and the other is Writer, and check for a Euler path, but it doesn't work on example 4 When can I AK Div4......

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

I am newbie to competitive programming. I appeared for this contest and solved 3 problems (yay, albeit with a lot of trial error). In the contest announcement page, it showed that it was rated for participants with ratings <= 1400, so it should have been rated for me. But I don't see that being reflected on my profile page under contests. I don't know what happened. I would be glad if anyone could clear up my confusion.

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

    It would be updated once the open hacking phase ends.

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

    After every contest there is an open hacking phase where participants try and hack each other. Only after that the system will start updating ratings . In general it takes 24 hours to update ratings . But for div 4 rounds it might take more than that

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

(found)

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

Is my intuition for G correct, because i am getting wrong answer in test 5, testcase 168. approach is to create a graph, and each category of artists and genre represent an edge between two adjacent nodes, ie.if two nodes have same genre or same artist then there will be edge between them. so after we create a graph we can just find the size of largest connected component and print n-c.(n is total number of nodes)

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

    No, being connected doesn't mean that you can make a simple path that visits all nodes.

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

      can you explain why that might be the case?.Because what i am thinking is, there will always exist a valid simple path in which we can arrange the elements of that particular cc.

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

        This is the simplest counterexample I can think of:

        which can be created with this input: https://ideone.com/Lvl1xi

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

          thank you very much.:)

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

          how did you solve this question?

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

            Bitmask DP is probably the simplest, for example if you do top-down DP then you can set $$$dp[i][bitmask]$$$ = maximum length of the path you can further advance when you visited vertices in $$$bitmask$$$ and you're currently at vertex $$$i$$$, then it is $$$max(dp[j][bitmask | (1 \lt \lt j)])+1$$$ where $$$i$$$ and $$$j$$$ are connected by an edge.

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

          really nice explination. I worked this problem for a long time, but got wrong for the same reason

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

    It is not necessary that if a component is connected , then you can get an ordering for each vertex in that component following the rule for adjacent songs.

    So, instead of size of component , we need to find the longest path in each component.
    That gives TLE

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

Can anybody help me in figuring out where my solution is wrong for "1950D — Product of Binary Decimals"

https://codeforces.me/contest/1950/submission/253812424

it would be great help!! thanks

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

    I just read through your code, consider trying to get the case 1210 = 11*11*10 to return print YES correctly.

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

name of problem D was a hint about its tag.

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

Ive seen many solutions for G problem using dp + bitmask. Could someone explain why only using bitmask and trying to take all the vertices you can doesnt work? Here my solution . I just used bitmask + bfs but got wa on test 5

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

    How do you find the optimal way to reorder the elements?

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

when i don't add the condition (c ==a+1), can anyone tell me the testcase where this code fails?

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

Can anybody explain how this code gets AC? https://codeforces.me/contest/1950/submission/253676853

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

    He did a brute force and store all the binary decimals till 10^5 size, its genius, I would have never thought of it...

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

      I mean, why is it correct? Is it possible to prove that this solution is correct?

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

        find all the binary decimals till 10^5 is easy, you jut have to do the combination of 0 and 1 , and then just check with the number to see if it is divisible by our stored numbers ,

        TC should be, (O(len(stored) + (n//10)),
        
        and len(stored) is 30 ,so O(30+ N) 
        
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I've done something similar 253775386.

        Binary Decimal is a number with only $$$1$$$ or $$$0$$$ in its decimal notation.

        So, it is quite intuitive think about all possible binary decimals.

        For length $$$1$$$ -> $$$1$$$ $$$\newline$$$ For length $$$2$$$ -> $$$10, 01$$$ $$$\newline$$$ For length $$$3$$$ -> $$$100, 101, 110, 111$$$ $$$\newline$$$ For length $$$4$$$ -> $$$1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111$$$ $$$\newline$$$ For length $$$5$$$ -> $$$10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111,$$$ $$$\newline$$$ $$$11000, 11001, 11010, 11011, 11100, 11101, 11110, 11111$$$ $$$\newline$$$ For length $$$6$$$ -> $$$100000$$$ since $$$n \leq 10^5$$$ $$$\newline$$$

        Now, for a given $$$n$$$ to be product of binary decimals, either it is one of the above mentioned numbers or it is a product of $$$2$$$ or more above mentioned binary decimal numbers.

        So, we can just recursively check whether it is divisible by any of these above mentioned numbers very easily.

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

        Guys, they wanted a proof, not a step-by-step implementation guidance meant for a toddler...

        For the OP: At least until $$$10^5$$$ size, I am observing that for every two distinct coprime binary decimals, their sets of prime divisors also don't intersect. I believe that to cause an unexpected division to fail this kind of solutions, the former condition must not hold.

        (This is by far just my observation and intuition, so take it with a grain of salt)

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

      you only need 10, 11, 100, 101, 110, 111 — all the factors below the sqrt(10^5)

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

    Suppose you can write $$$n$$$ as a product of binary decimals, say $$$a_1, a_2 \cdots a_n$$$ (in increasing order). Now when you delete $$$a_n$$$, the rest are still guaranteed to be binary decimals. However, if you follow another strategy, say like dividing by a smaller number first, some $$$a_i$$$ may no longer be a binary decimal

    Edit: nvm, this isn't good enough

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

      Okay, I believe I found a counterexample, suppose we have

      $$$1001 \times 1001$$$, now the submission would first delete $$$11 * 1001$$$ = $$$11011$$$, and the remaining factor would be $$$91$$$, so it would be $$$NO$$$ instead of $$$YES$$$, the counterexample is $$$1002001$$$, and I can't really find a smaller one

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

        WOW thanks! I suppose there was a reason I couldn't prove that solution for 2 hours.

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

Waiting for the tutorial of G...

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

I want to use DSU to solve G but failed ,who could tell me why,I want to find the biggest set f[k] and return n-size[k] thank you

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

    A test like this would fail you:

    1
    7
    a x
    a y
    b y
    b z
    c z
    d y
    d t
    

    It's clear that this graph is connected, but the answer would be 1 rather than 0.

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

      I also got help from the graph, but I was looking for the length of the longest path in it Can you tell me the reason for WA 3 of this code: https://codeforces.me/contest/1950/submission/253975967

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

        You are doing the DFS wrong if you want to find the longest path: vis[a] must be unset at the end of dfs() function, otherwise it would skip a lot of paths, possibly the longest included.

        Despite the approach of finding longest path was correct, however, a naive/exhaustive DFS will be inefficient with $$$n \le 16$$$ — as the complexity for the number of any paths in a graph would be $$$\mathcal{O}(n!)$$$, so even at the most optimistic scenario, you would encounter failure at test #44 anyway.

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

      thanku bro

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

Can anybody tell what's wrong with (G)this submission, I am getting WA on test case 3 , can't find the mistake

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

A better solution: Was 2 min late for the submission in the contest...


O(log(a)) TC [submission:253825565]

import sys input = sys.stdin.buffer.readline read = sys.stdin.buffer.read from math import log2 as l for _ in range(int(input())): a,b,c=map(int,input().split()) if a>0: h=int(l(a))+1 f=a+1 cf=b t=pow(2,h-1)-(((2*a+1)-(pow(2,h)-1))//2) b=int(max(b-t,0)) h=h+((b+(f-1)))//f if a+1==c : print(h) else: print(-1) else: h=b if c!=1: print(-1) else: print(h)
»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

O(logn) solution for problem f

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

Can anyone help me with this solution, how is this different from the one in tutorial?

https://codeforces.me/contest/1950/submission/253833340

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

    why did you assume it's a monotonic function you have too check for all factors and choose the min one

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

can't g be solved by optimizing the code for finding the longest path in a graph problem

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

    The length that can be filled does not satisfy monotonic conditions, so binary search cannot be used

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

      yeah but i meant can we add some conditions in the dfs code only so that we don't get tle in tc 33

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

        oh sorry, i reply wrong place, by the way i encountered the same problem as you in the competition, and the maximum complexity of dfs is n! And 16!>= 2e11

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

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

thanks for super duper fast editorial MikeMirzayanov !

thanks for the greatest platform ever Codeforces and also Polygon <33

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

    What's wrong with you bro? Are you expressing your gratitude or making fun of him?

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

    What's going on here, please don't fill comment section like that.

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

Can any kind soul please explain all types of solutions with time complexities $$$O(a+b+c)$$$, $$$O(log(a+b+c))$$$, $$$O(1)$$$ for 1950F - 0, 1, 2, Tree! clearly and intuitively :(

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

I have a question. yesterday I sent in and was accepted for four problems in the Division 4 contest while now it turns out that I only sent in one. Why?

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

    Be patient, system testing is currently in progress. Your three others are in the line for rejudging.

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

      thank you for your reply

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

      what do you mean by rejudging? sorry i am new here

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

        Normally in a Codeforces contest, in-contest submissions are judged by a preliminary testset (or more commonly called pretests) to reduce server load. After the contest ends (and with an extra delay for preparation and such), all AC submissions will be rejudged in a phase called "system test" with the full testset available.

        For Div.3, Div.4 and Educational however, the in-contest testset is complete, yet after the contest ends, a 12-hour open hacking phase is presented for community to hack any AC submissions they felt incorrect but the original testset missed. After the hacking phase, those hacks are added to the testset, and after some more delay for preparation, system test will kick in.

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

Please help this suffering guy. In Problem E: Why only prefix and suffix of length of divisors of n is taken, I took all possible substring of the length of divisors of n instead of only prefix and suffix, and it will sure give TLE.

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

    same question, got TLE by taking all possible substrings

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

    Because it can be proven that if the prefix and suffix of some substring length c both don't pass that means that there must be more than 1 character for which the K-string is different than the original. You don't use any substrings in between because it is not optimal and doesn't make any sense to concatenate those substrings together some number of times to where the length of the entire string is equal to the original string because you are introducing offsetting character's to the original string from the get go. So, you don't even check those cases in the first place because anyway once you do that you are introducing wrong characters and your going in the wrong direction.

    for example in a string abcabcabc it makes absolutely no sense to ever check the substring "bca" because no matter how many times you concatonate this string together, the characters just offset. because "abc" != "bca".

    it's possible that you may have just overlooked that you compare the strings head on.

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

      Wow, nice explanation thanks for your help. I really appreciate it. Codeforces community is really good.

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

    Let's consider Problem E without the "1 mistake rule".

    If that were the case, it would be enough to check all of the divisors of n (let d be a divisor of n) and only test the prefix of length d.

    However, with the "1 mistake allowed", it's not guaranteed that the prefix is the correct pattern (perhaps the only mistake is within it). That's why we need another string to act as our pattern. You can use the next string starting from d of length d s[d:2*d] or the suffix s[n-d:]. it might be easier to spot in this test case :

    8
    hshahaha
    

    In the contest, I implemented this idea without proving it. It was based on intuition.

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

Thanks for the complexity analysis in D. Note that most of the 30 numbers are IGNORED so the complexity is far lower than n^0.587.

If you do precomputation then its about $$$O(N^{1.4})$$$ (not a tight bound just a bigger bound than $$$O(N^{1+(log(2)/log(10))}$$$)).

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

Sorry, can anyone tell me where the problem is with this code? https://codeforces.me/contest/1950/submission/253805652 I made a graph and put an equal edge between both songs with at least one component, so the answer is equal to the longest path in the final graph.

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

why 2 segments are sufficient for problem E

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

    hope this helps

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

    Because the string after being divided into k parts has only maximum of 1 outlier. If you get a outlier in the 1st segment (hshahaha) then the 2nd segment musn't be an outlier, so it is enough.

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

Is G NP-complete? G can be reduced into a longest path problem, but there are additional constraints.

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

Problem D: My Solution

Given: A number num(let)

We have to Check: Whether num is product of decimal numbers which contain 0's and 1's (binary) as their digits.

Explanation: ---- Below i have used binary word. It is denoting the decimal number having digit as 0 and 1.

--if num = (binary1)^p1 * (binary2)^p2 * ......(binaryk)^p then answer is yes. 
 other wise no.

---- Can we generate all decimal number having binary digits?

--Yes, we can because 1<=n<=10^5.

  --As 10^5 has 6 digits, (_ _ _ _ _ _) => (2*2*2*2*2*2)=> 2^6 => 64 (All possible different 
    decimal numbers having binary as digit.)

  --So all possible binary decimals will be binary of numbers from 1 to 63 (000001 to 111111).

----- Iterate over these decimal(containing binary as digits) numbers and reduce n by the power of this number contained in n.

----- if atlast n=1 then answer is yes otherwise no.

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

Can Anyone explain the concept of 5th Question

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

A brute solution for D

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

in Ques. E, why do we need to iterate in reverse also?

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

    "**acabab**"

    look at the above testcase: Possible length of subarray is 1,2,3 or 6.

    If we only consider the subarray starting from beginning, then the answer would have been 6.

    But considering from last, we can achieve an optimal answer of 2, where we concatenate ab 3 times to get ababab which satisfies the given condition.

    This condition wouldn't have satisfied if we had considered it from the beginning where we would have got acacac which differs from the given string in 2 places and won't be considered for solution. Hope that u have gotten my point.

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

      thanks, got it. so it doesn't work if we increase the mistake count to 2 or above. how do we solve the general case?

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

    It doesn't have to be reverse it can be the string starting from d with length d(d is a divisor of n). The key point it's another string starting from an index divisible by d and with length d. We did this because we assumed that there is a mistake in the first string of length d

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

Sometimes, i feel that i don't think correct to solve the problems like D.Product of Binary Decimals, i didn't think correct and i don't know DP to think about the solution to this problem. How can i fix this problem?

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

    I think in term's of solution what are the different solutions can different solution have same pattern solution. Are there are finite solutions in terms of 'N' -> can this solution be pre-computerd

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

    I managed to solve D without DP or precomputation. Although I was unsure about getting hacked.

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

      can you tell me the proof of your solution and tell me why it works ? You basically checked for any factor i of n , i and n/i should both be binary ?

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

        I can't proof but can feel the intuition. The constraint is not so big. Had the constraint be 1e6 and my solution would definitely fail.

        Number of terms multiplied together to get N will not be very big.

        11^3 * 10^2 >= N [ two factors is enough to check ]

        11^2 * 11^2 * 10^1 >= N [ Three factors but you can first divide by 10 to get rid of 1 term, therefore left with two terms to check ]

        11 * 101 * (11 or 10 at max) [ So it's easy to check. first divide by 10 then divide by 11, check if that's binary. If not look for it's two factors ]

        I hope you get the idea.

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

      My issue is not to solve with DP or any topic, but i want to learn how to think right to solve problems like this problem

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

    During the contest i didn't get D from the first try and that's ok . I actually wrote three different codes for D until it worked . And in problem E I rushed to finish it in the last 30 minutes leaving a few minutes for F. I think the biggest take way from what i said is that you should not give up until the contest is over .I also think you should approach problems from different angles and solve more problems.

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

Where s the tutorial for G?

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

why are ratings not updated yet?

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

Is it possible to solve G using bitmask dynamic programming?

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

    Yes, you don't even need to think about it as a graph.

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

      My state will be dp(pos,last,mask)

      from every state I'll increment pos by taking or not taking that element.

      last will determine what my last taken position was.

      mask will keep track what positions are already taken.

      Do you think it can be solved like this?

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

        Too slow, you don't need to care about the position, mask and last placed is enough.

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

          But without pos, how I'll reach base case which is pos == n? Can you please explain a little bit?

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

            base case is when the mask is all ones, that means you processed all songs

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

              But how will I count the number of songs that I deleted?

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

                That will be the value of the dp.

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

1950G — Shuffling Songs Tutorial unavailable. Someone please explain the solution in the meantime.

253971845 -> This is my solution which got TLE in test case 39.

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

Thank you very much for this round! Maybe I could have solved more problems (at least one more), but I finally became a pupil! This is great!

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

i just want to know that for e question,i submitted my code in c++17 and it got wrong answer on test2,then after contest i checked that test and it was giving right answer on my visualstudiocode compiler and then i submitted that same code in c++20 and it got accepted,now i want to know why is it so and am i responsible for this mistake of choosing compiler or is it a error from codeforces's side,also i dont think i used anything in my code which would not have worked in c++17 according to me.someone please help

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

    pow is a dangerous function in C++ since its precision is really bad, combining with the rounding-down nature of integer casting it might corrupt the prime check procedure. Probably 64-bit processing in CF's C++20 made it a bit more precise so you passed, but C++17 32-bit didn't.

    A safer / more stable way for square root alone should be sqrt. You can also try checking for i * i <= n, but careful for overflow (normally if the step is just i++ I'm still confident that such overflow won't happen).

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

Can anyone help me? I use dsu(Disjoint set union) to solve problem G, but I don’t know why it always goes Wrong answer on test 5. I spent a long time thinking about it, but I had no idea why.Here is my code:253955348

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

    DSU is a wrong approach. A test like this would fail you:

    1
    7
    a x
    a y
    b y
    b z
    c z
    d y
    d t
    

    Correct answer should be 1.

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

      Thank you very much, you are absolutely right. I don't fully understand the question, that's stupid.

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

        It's okay, everyone makes mistakes. Keep yourself up and do better next time.

        Glad that I could help.

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

          so sorry to ask but can you please check my submission for G. thank you. something is wrong

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

            Since it's a Hamiltonian walk, you should know where that walk is currently stopping at — instead of trying to link an edge to any vertex in the subset — your DP is lacking an attribute for the last vertex of your path.

            Bonus: comparing raw strings will TLE eventually (around test 33). Try to optimize that later.

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

              I am sorry so what should i do :(

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

              Hamiltonian walk and cycle are different??

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

              hey!!! it got accepted apparently i just changed the position of for loops and it gave me AC :), thank you!

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

          i was following 4. Check for existence of Hamiltonian walk from this blog:https://codeforces.me/blog/entry/337

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

in problem D when i am using this: for(ll i=2e5;i>=10;i--){ if(isBD(i)){ vd.pb(i); } }

to pre calculating binary numbers then it works correct for all test cases,but when i am doing for(ll i=10;i<=2e5;i++) it is producing wrong output on the last test case (1001) ,can anyone explains why the first one is fetching correct answer?

this is my approach 254040093

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

    I had the same implementation and it was outputting wrong answer on 1001 . so i just added if n in BD : print"YES" the reason is that 1001 is divisible by 1, 7, 11, 13, 77, 91, 143, 1001 notice how if you divide by 11 you won't be able to prove it's fine because you'll be left with 91 .

    another trick is to sort the array of binary decimals in non-ascending order and for(ll i=2e5;i>=10;i--) does that in your code.

    But i still don't get why this answer works . I hope someone can explain it .

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

For question g, is it wrong to use the length of the longest path in the graph?

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

sorry for the confusion with clz. Interesting, learnt something new, ty

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

include<bits/stdc++.h>

using namespace std; int main() { int t; cin>>t; while (t--) { int a,b,c; cin>>a>>b>>c; bool case1=(a<b&&b<c); bool case2=(a<b&&b>c);

if (!case1&&!case2)
    {
        cout<<"NONE"<<endl;
    }
    if (case1)
    {
        cout<<"STAIR"<<endl;
    }
    if (case2)
    {
        cout<<"PEAK"<<endl;
    }
}
return 0;

}

I think this code for A without else looks better

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

Here is an elaganto solution with T(N) = O(log(N)), S(N) = O(1) for 1950F — 0, 1, 2, Tree!

void solve()
{
    int a, b, c;
    cin>>a>>b>>c;
 
    int height = -1;
    if(a > 0){
        // a will have a + 1 slots or children
        int slots = a + 1;
        if(slots == c){
            // Calculating a's height
            int as_height = 0;
            for(int a_copy = a; a_copy; a_copy>>=1, as_height++);

            if(b == 0){
                height = as_height;
            }
            // If putting a's results in a complete tree
            else if((slots & (slots - 1)) == 0){
                int bs_height = ceil((double)b/slots) - 1;
                height = as_height + bs_height + 1;
            }else{
                // If putting a's is not producing a complete tree
                // Then how many slots are there above the base as_children
                /*
                      a
                     / \
                    a   _ <==== This is left slots
                   /\
 
                    Here, 1 is the number of empty slot
                */
                int left_slots = (1<<(int)(log2(slots) + 1)) - slots;
                if(b > left_slots){
                    int b_left = b - left_slots;
                    int bs_height = ceil((double)b_left/slots) - 1;
                    height = as_height + bs_height + 1;
                }else if(b <= left_slots){
                    height = as_height;
                }
            }
        }
    }else{
        if(c == 1){
            height = b;
        }
    }
 
    // print(a, b, c, height);
    cout<<height<<nline;
    return;
}
»
8 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Why my solution works? Submission I submitted this solution in hurry and it got AC.

I removed every divisor of n which is also a binary_decimal number from n, and in the end if the n is reduced to 1, then print "YES" else "NO".

I did it in greatest -> smallest binary_decimal number order which passed the soln. smalletst -> greatest binary_decimal number order can't work. Failing TC : 1001.

Where 11*91 = 1001

Basically, it was just a fluke, which went good.

I want to know How can i verify correctness of such wierd claims in a live contest?

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

Someone please help with problem G(im new to dp): 254308462

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

Waiting for editorial of G.....

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

Let's say we have a point (x,y) on a coordinate system. What are the possible rotations of the point?

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

I have a beautiful recursive approach for Question D https://codeforces.me/contest/1950/submission/253808823

Let F(n)=b1*b2*b3*..*bk , where b1,b2,..bk are binary decimal numbers . Then F(n)=b1*F(n/b1)

Thus if we find a binary decimal factor of n then if F(n/b1) is a product of binary decimal numbers then n also is .

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

It's been 4 days, still no tutorial for G?

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

    Consider a graph there $$$i$$$-th vertex has two values $$$(g_i, w_i)$$$. We can move from $$$i$$$ to $$$j$$$ only if $$$g_i = g_j$$$ or $$$w_i = w_j$$$. Now a simple path in that graph is some permutation we want to get (if vertex is not in our path, we will delete it). We want to delete as many as possible, so we have to find maximum simple path in that graph.

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

https://codeforces.me/contest/1950/submission/254107386 could anyone help me with this (G question) , my logic is that i have made a graph with vertices having edge on having same genre or same writer or both , and then find the longest path in the graph , but it is giving wrong answer in testcase 3 at 163rd token :/

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

Can anyone help me for Question E, here is my solution Python code. It is giving TLE but I think the time complexity is O(128*N). Also the same code of C++ version is getting accepted code.

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

what is the difference between (a<b && b<c) and if(a<b){ if(b<c){ cout<<"STAIR"<<endl; }else{ cout<<"PEAK"<<endl; }else cout<<"NONE"<<endl;

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

    Try a scenario where a < b and b >= c and see for yourself.

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

Is it possible to solve 1950G - Shuffling Songs without DP? SlavicG flamestorm mesanu

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

Could anybody tell me why my code fails? Idea of the solution is to create a graph where each node is a song and there is an edge between two songs if they have the same genre or writer. Then we can find the size of the largest connected component in the graph and the answer will be n — size of the largest connected component. This is because we can rearrange the songs in the largest connected component in any way we want and the rest of the songs will be removed.

public static int dfs(int u, List<List<int>> graph, bool[] visited)
  {
    visited[u] = true;
    var size = 1;
    foreach (var v in graph[u])
    {
      if (!visited[v])
      {
        size += dfs(v, graph, visited);
      }
    }
    return size;
  }
  public static void Main(string[] args)
  {
    var t = int.Parse(ReadLine());
    while (t-- > 0)
    {
      var n = int.Parse(ReadLine());
      var songs = new List<(string, string)>();
      for (var i = 0; i < n; i++)
      {
        var input = ReadLine().Split();
        var g = input[0];
        var w = input[1];
        songs.Add((g, w));
      }
      var graph = new List<List<int>>();
      for (var i = 0; i < n; i++)
      {
        graph.Add(new List<int>());
        for (var j = 0; j < n; j++)
        {
          if (songs[i].Item1 == songs[j].Item1 || songs[i].Item2 == songs[j].Item2)
          {
            graph[i].Add(j);
          }
        }
      }
      var visited = new bool[n];
      var mx = 0;
      for (var i = 0; i < n; i++)
      {
        if (!visited[i])
        {
          var size = dfs(i, graph, visited);
          mx = Math.Max(mx, size);
        }
      }
      Console.WriteLine(n - mx);
    }
  }
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am glad to give you an example which your solution will be failed.

    1
    5
    a e
    b e
    c e
    b f
    d f
    

    If we just consider "connected component" the answer will be 0, however we must get a continuous chain to make sure a correct shuffle. In this example, answer will be 1, as we choose to remove the song <c, e> and get a correct shuffle.

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

E was a genius question, Thanks :)

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

I did, 1950E using string hashing, (i learned that concept few days ago, so i tried it over here), And it worked...... :)

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

F can be solved in O(1), so I squeezed the code in one line lol

Code