Codeforces Round 937 (Div. 4) Editorial

4 weeks ago, # |

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).

→ Reply

Markusssian

4 weeks ago, # ^ |

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

→ Reply

zhy_

4 weeks ago, # ^ |

thank u

→ Reply

par4dox

4 weeks ago, # |

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

→ Reply

Vampire

4 weeks ago, # |

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

→ Reply

DC_H

4 weeks ago, # ^ |

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

→ Reply

4 weeks ago, # ^ |

+20

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

→ Reply

Lalit_G11

4 weeks ago, # ^ |

-10

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

→ Reply

saelcc03

4 weeks ago, # ^ |

-9

__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))

→ Reply

4 weeks ago, # ^ |

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.

→ Reply

saelcc03

4 weeks ago, # ^ |

+20

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

→ Reply

amoad

4 weeks ago, # ^ |

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

→ Reply

4 weeks ago, # ^ |

← Rev. 2 →

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).

→ Reply

_smile

4 weeks ago, # ^ |

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 ??

→ Reply

4 weeks ago, # ^ |

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

→ Reply

_smile

4 weeks ago, # ^ |

ok, thank u

→ Reply

flamestorm

4 weeks ago, # ^ |

+10

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.

→ Reply

prakhartrivedi3

4 weeks ago, # ^ |

← Rev. 2 →

solution you can check this solution for O(1)

→ Reply

4 weeks ago, # ^ |

bro u used power function is not o(1)

→ Reply

4 weeks ago, # ^ |

int ha=log2(a); is logarithmic

→ Reply

Husanboy

4 weeks ago, # ^ |

'cause it is div4 :)

→ Reply

PrinzeOP

2 weeks ago, # ^ |

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

→ Reply

R1nixi

4 weeks ago, # |

thanks you for the quick editorial and good round!

→ Reply

4 weeks ago, # |

-17

Hello I am gokula kannan siva ji

→ Reply

4 weeks ago, # ^ |

-10

why am i geting downvoted i am gokula kannan siva ji < : (

→ Reply

ilovenandini

4 weeks ago, # ^ |

don't be sad bro, I upvoted

→ Reply

4 weeks ago, # ^ |

thank you bro i appreciate it :( they are just mad for no reason

→ Reply

destroyer_sam

4 weeks ago, # |

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??

→ Reply

4 weeks ago, # ^ |

← Rev. 2 →

-7

Consider

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

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

→ Reply

destroyer_sam

4 weeks ago, # ^ |

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

→ Reply

KostyR13

4 weeks ago, # ^ |

← Rev. 2 →

[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.

→ Reply

hara108

4 weeks ago, # ^ |

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

→ Reply

4 weeks ago, # ^ |

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.

→ Reply

han_hyo_joo

4 weeks ago, # ^ |

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.

→ Reply

https://clist.by/problems/

4 weeks ago, # ^ |

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.

→ Reply

Luciefer_x

4 weeks ago, # |

what would be the rating for problem E? just wondering

→ Reply

aayein__O_O

4 weeks ago, # ^ |

around 1300

→ Reply

dhruvokay

4 weeks ago, # ^ |

realistically 1200-1300, Clist says its 1500:

→ Reply

a_gt3_rs

4 weeks ago, # ^ |

← Rev. 2 →

Maybe 1200-1300

→ Reply

Phuocbua

4 weeks ago, # ^ |

maybe around 1200-1300, maximum ~1500

→ Reply

xiorra

4 weeks ago, # |

thanks for the solutions!

→ Reply

MrSavageVS

4 weeks ago, # |

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.

→ Reply

AlephNullams2008

4 weeks ago, # |

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

→ Reply

saelcc03

4 weeks ago, # ^ |

try case 1 2 aa

→ Reply

Barytania_001

4 weeks ago, # |

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.

→ Reply

Gandu_Korotkevich

4 weeks ago, # |

can someone explain solution to problem E

→ Reply

4 weeks ago, # ^ |

brute force check for every factor of n

→ Reply

dikidikiantasadiki

4 weeks ago, # ^ |

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.

→ Reply

Gandu_Korotkevich

4 weeks ago, # ^ |

thanks got it now

→ Reply

GohTengFong

4 weeks ago, # ^ |

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

→ Reply

4 weeks ago, # ^ |

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

→ Reply

4 weeks ago, # ^ |

← Rev. 2 →

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

→ Reply

4 weeks ago, # ^ |

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

→ Reply

wsaleem

4 weeks ago, # ^ |

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

→ Reply

nflight11

4 weeks ago, # |

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.

→ Reply

nflight11

4 weeks ago, # ^ |

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

→ Reply

ssh.

4 weeks ago, # |

← Rev. 2 →

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.

→ Reply

4 weeks ago, # ^ |

Counter Example

→ Reply

futuristic_coder

4 weeks ago, # |

← Rev. 2 →

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

→ Reply

pramana

4 weeks ago, # ^ |

← Rev. 3 →

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

→ Reply

micha77

4 weeks ago, # ^ |

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

→ Reply

micha77

4 weeks ago, # ^ |

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.

→ Reply

futuristic_coder

4 weeks ago, # ^ |

← Rev. 2 →

but this method is giving error on test 2 https://mirror.codeforces.com/contest/1950/submission/253788629 here is my solution

→ Reply

micha77

4 weeks ago, # ^ |

        int count = 0;
        for(int i = 0 ; i < size ; i++){
            pro*=arr.get(i);
            if(isBinary(pro)) {
                pro = 1;
                count++;
            }
 
        }
        if(pro==1)
            System.out.println("YES");
        else
            System.out.println("NO");

Instead of this, erase all binary prime factors and pass the remaining primes to the recursive function with two nested for loops, erase both elements if they multiply to a binary number and do a recursive call on remaining primes. If no elements are left in the primes vector then binary multiplies were found. here's my solution https://mirror.codeforces.com/contest/1950/submission/253817219

→ Reply

futuristic_coder

4 weeks ago, # ^ |

Got it. Thank You

→ Reply

ishat_jha

4 weeks ago, # |

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

→ Reply

PylyaoTBabyliUltraNysha

4 weeks ago, # |

← Rev. 3 →

+12

My solutions to problems A

code

O(1)

#include <bits/stdc++.h> // Nya
#define all(x) x.begin(),x.end() // Nya
#define rll(x) x.rbegin(),x.rend() // Nya
#define sz(x) x.size()
using ll = long long;
using namespace std;
void Solve()
{
    ll a,b,c;
    cin >> a >> b >> c;
    if (a < b && b < c)
    {
        cout << "STAIR\n";
        return;
    }
    if (a < b && b > c)
    {
        cout << "PEAK\n";
        return;
    }
    cout << "NONE\n";
}
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    ll tt = 1;
    cin >> tt;
    while (tt-->0)
    {
        Solve();
    }
}

My solutions to problems B

code

O((n * 2) ^ 2) In this problem it was possible to notice that when numbers (i/2) and (j/2) that they had to be of the same parity

#include <bits/stdc++.h> // Nya
#define all(x) x.begin(),x.end() // Nya
#define rll(x) x.rbegin(),x.rend() // Nya
#define sz(x) x.size()
using ll = long long;
using namespace std;
void Solve()
{
    ll n;
    cin >> n;
    n*=2;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if ((i / 2 + j / 2) % 2 == 0)
            {
                cout << "#";
            }
            else
            {
                cout << ".";
            }
        }
        cout << '\n';
    }

}
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    ll tt = 1;
    cin >> tt;
    while (tt-->0)
    {
        Solve();
    }
}

My solutions to problems C

code

This code can be considered in O(1) complexity. I break this line that is given for hours and minutes if the time is on the clock less than 12 or equal to 24, then it will always be AM in other cases PM. And then look at the clock

#include <bits/stdc++.h> // Nya
#define all(x) x.begin(),x.end() // Nya
#define rll(x) x.rbegin(),x.rend() // Nya
#define sz(x) x.size()
using ll = long long;
using namespace std;
void Solve()
{
    string s;
    cin >> s;
    ll hh = stoll(s.substr(0, 2));
    string t = (hh < 12 || hh == 24 ? "AM" : "PM");
    if (hh == 0)
        hh = 12;
    else if (hh > 12)
        hh -= 12;
    cout << (hh < 10 ? "0" : "") << hh << s.substr(2, 3) << " " << t << '\n';

}
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    ll tt = 1;
    cin >> tt;
    while (tt-->0)
    {
        Solve();
    }
}

My solutions to problems D

code

My logic consisted of creating an array that would store all binary decimal numbers. 1. I considered if the number consists only of the digits 1 and 0 then if it consisted it displayed "YES" If not then I took the number n and divided it by all binary numbers, if the cycle cannot divide anymore then the answer is NO, otherwise if it came to the cycle n == 1 then the answer is YES

#include <bits/stdc++.h> // Nya
#define all(x) x.begin(),x.end() // Nya
#define rll(x) x.rbegin(),x.rend() // Nya
#define sz(x) x.size()
using ll = long long;
using namespace std;
set <ll> pr;
void Rec(ll sum)
{
    if (sum > 1e5)
        return;
    pr.insert(sum);
    Rec(sum * 10);
    Rec(sum * 10 + 1);
}
void Solve()
{
    ll n; cin >> n;
    ll p  = n;
    ll null = 0;
    ll one = 0;
    string s = to_string(n);
    while (p > 0)
    {
        null+=(p % 10 == 0);
        one+=(p % 10 == 1);
        p/=10;
    }
    if (null + one == sz(s))
    {
        cout << "YES\n";
        return;
    }
    bool ans = true;
    while (n > 1)
    {
        bool q = false;
        for (auto & it : pr)
        {
            if (it == 1)
                continue;
            while (n % it == 0)
            {
                n/=it;
                q = true;
            }
        }
        if (!q && n > 1)
        {
            ans = false;
            break;
        }
    }
    cout << (ans ? "YES\n" : "NO\n");
}
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    ll tt = 1;
    cin >> tt;
    Rec(1);
    while (tt-->0)
    {
        Solve();
    }
}

My solutions to problems E

code

Let's note that the length of the string k — can only be a divisor of n — the size of the string. In my logic I went by the size that it might be. Then I took cycle 2 which one might say created substrings from i to i + d i — where we are d is the divisor, which we consider to be the length . 3 in a loop I simply checked whether the string matches the condition. I remind you of the condition “Find the length of the shortest string k, such that several (possibly one) copies of k can be concatenated together to form a string the same length as s, and there is at most one different character". Complexity of the algorithm that is implemented sqrt(n) * log(n) * n

#include <bits/stdc++.h> // Nya
#define all(x) x.begin(),x.end() // Nya
#define rll(x) x.rbegin(),x.rend() // Nya
#define sz(x) x.size()
using ll = long long;
using namespace std;
void Solve()
{
     ll n; cin >> n;
    string s; cin >> s;
    vector <ll> divs;
    for (int i = 1; i * i <= n ; i++)
    {
        if (n % i == 0)
        {
            divs.push_back(i);
            if (i != n / i)
                divs.push_back(n/i);
        }
    }
    sort(all(divs));
    for (auto& d : divs)
    {
        bool ok = false;
        for (int i = 0; i < n; i += d)
        {
            bool q = true;
            string t = s.substr(i,d);
            ll len = 0;
            ll cnt = 0;
            for (int j = 0; j < n; j++)
            {
                if (t[len % d] != s[j])
                {
                    cnt++;
                }
                if (cnt > 1)
                {
                    q = false;
                    break;
                }
                len++;
            }
            if (q)
            {
                ok = true;
                break;
            }
        }
        if (ok)
        {
            cout << d << '\n';
            return;
        }
    }
}
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    ll tt = 1;
    cin >> tt;
    while (tt-->0)
    {
        Solve();
    }
}

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

In this problem it is more difficult to implement dp than to come up with logic. In this problem you just need to go through all the permutations.

Even the authors gave hints that this is due to permutations. Problem limits

1 <= n <= 16

2^n < 2^16

^ — degree

#include <bits/stdc++.h> // Nya
#define all(x) x.begin(),x.end() // Nya
#define rll(x) x.rbegin(),x.rend() // Nya
#define sz(x) x.size()
using ll = long long;
using namespace std;
void Solve()
{
    ll n;
    cin >> n;
    map<string, ll> mp;
    vector<pair<string, string>> par(n);
    for(ll i = 0; i < n; i++)
    {
        cin >> par[i].first >> par[i].second;
        mp[par[i].first]++;
        mp[par[i].second]++;
    }
    ll cnt = 0;
    vector<pair<ll, ll>> kol(n);
    for (auto & [x,y] : mp)
        y = ++cnt + 1;
    for(ll i = 0; i < n; i++)
        kol[i].first = mp[par[i].first],kol[i].second = mp[par[i].second];
    ll ans = 0;
    ll TwoLenMask = (1<<n)-1;
    vector<vector<ll>> dp(1 + n + 1 , vector<ll>(1 + TwoLenMask + 1, -1));
    function <ll(ll, ll, ll)> rec = [&] (ll TwoLenMask,ll len,ll n)
    {
        if(TwoLenMask == 0) return 0LL;
        if(len != -1 && dp[len][TwoLenMask] != -1) return dp[len][TwoLenMask];
        pair<ll,ll> cnt = {-1,-1};
        if (len != -1)
            cnt = kol[len];
        ll ans = 0;
        for(ll i = 0; i<n; i++)
            if(TwoLenMask & (1LL << i))
            {
                if(len == -1 ||  kol[i].first == cnt.first ||  kol[i].second == cnt.second)
                    ans = max(ans,1+rec((TwoLenMask^(1<<i)), i, n));
            }

        if(len == -1) return ans;
        return dp[len][TwoLenMask] = ans;
    };
    cout << n - rec(TwoLenMask, -1, n) << '\n';
}

int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    ll tt = 1;
    cin >> tt;
    while (tt-->0)
    {
        Solve();
    }
}

→ Reply

sasank555

4 weeks ago, # |

Help Anyone

→ Reply

Ashar-Usmani

4 weeks ago, # |

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

→ Reply

janY_

4 weeks ago, # ^ |

+22

💀

→ Reply

SeineAle

4 weeks ago, # ^ |

And she's buying a stairway to Heaven ....

→ Reply

sairamnst

4 weeks ago, # |

← Rev. 2 →

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

→ Reply

rashmi_12345

4 weeks ago, # |

can someone explain me this approach for problem d ? 253830700

→ Reply

https://mirror.codeforces.com/contest/1950/submission/253824980

4 weeks ago, # ^ |

← Rev. 2 →

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

→ Reply

Harshiv_27

4 weeks ago, # |

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?

→ Reply

650iq

4 weeks ago, # ^ |

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

→ Reply

Harshiv_27

4 weeks ago, # ^ |

Thankss!

→ Reply

AvaraKedavra

4 weeks ago, # |

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.

→ Reply

wsaleem

4 weeks ago, # ^ |

Indeed, here is a solution. https://mirror.codeforces.com/contest/1950/submission/253859143

→ Reply

sshreyansh962

4 weeks ago, # |

253824980

WHY IS THIS WRONG QUES 4

→ Reply

sshreyansh962

4 weeks ago, # ^ |

→ Reply

https://mirror.codeforces.com/contest/1950/submission/253868766

4 weeks ago, # ^ |

You only considered good numbers divisible by 11 and 10, while not all of them have that attribute.

An example of such good numbers, and very possibly the one caused you a WA, is $$$10201$$$ ($$$101^2$$$).

→ Reply

sshreyansh962

4 weeks ago, # ^ |

ok thanku so much,will u share your soln plz

→ Reply

Dev77G

4 weeks ago, # ^ |

→ Reply

tanvir_islam

4 weeks ago, # |

thanks for very fast editorial.

→ Reply

Byte_maze

4 weeks ago, # |

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

→ Reply

ilovenandini

4 weeks ago, # ^ |

there are no constraints on n over all test cases.

→ Reply

i3mr125

4 weeks ago, # |

← Rev. 2 →

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

→ Reply

sairamnst

4 weeks ago, # |

← Rev. 2 →

253841056

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

→ Reply

von_arrow

4 weeks ago, # |

← Rev. 2 →

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.

→ Reply

Eliminator123

4 weeks ago, # |

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

→ Reply

Siddharth_78

4 weeks ago, # ^ |

boo hoo. grow up.

→ Reply

-linked-list-

4 weeks ago, # ^ |

"Grow up"? You unironically have Andrew Tate as your profile picture.

→ Reply

Siddharth_78

4 weeks ago, # ^ |

so?

→ Reply

mneo

4 weeks ago, # |

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

→ Reply

destroyer_sam

4 weeks ago, # ^ |

finding biggest component wont work!

look at this

→ Reply

I_lOVE_ROMAN

4 weeks ago, # |

← Rev. 2 →

Can anyone share the solution for D by DP?

→ Reply

dikidikiantasadiki

4 weeks ago, # ^ |

253844267

→ Reply

JoeDelaney2012

4 weeks ago, # |

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).

→ Reply

macaquedev

4 weeks ago, # |

← Rev. 2 →

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

→ Reply

prb_yes

4 weeks ago, # |

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://mirror.codeforces.com/contest/1950/submission/253828002

→ Reply

tickbird

4 weeks ago, # |

← Rev. 2 →

nvm, my assumption was wrong

→ Reply

Shivam2105

4 weeks ago, # |

← Rev. 2 →

→ Reply

saptarshi1729

4 weeks ago, # |

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!

→ Reply

anhuiwuhuyhb

4 weeks ago, # |

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

→ Reply

anhuiwuhuyhb

4 weeks ago, # ^ |

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

→ Reply

FelixNotter

4 weeks ago, # |

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

→ Reply

Dev77G

4 weeks ago, # ^ |

Here is a simpler solution for D : https://mirror.codeforces.com/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.

→ Reply

arihant_j

4 weeks ago, # |

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

→ Reply

Dev77G

4 weeks ago, # |

→ Reply

theRealChainman

4 weeks ago, # |

Problem G was great

→ Reply

pranut

4 weeks ago, # |

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

→ Reply

Fork512Hz

4 weeks ago, # |

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......

→ Reply

dimethylglyoxime

4 weeks ago, # |

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.

→ Reply

Priyansh_Kumar

4 weeks ago, # ^ |

It would be updated once the open hacking phase ends.

→ Reply

dimethylglyoxime

4 weeks ago, # ^ |

Thank you for the clarification!

→ Reply

4 weeks ago, # ^ |

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

→ Reply

jzavaglia

4 weeks ago, # |

← Rev. 2 →

(found)

→ Reply

4 weeks ago, # |

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)

→ Reply

djm03178

4 weeks ago, # ^ |

← Rev. 2 →

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

→ Reply

4 weeks ago, # ^ |

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.

→ Reply

djm03178

4 weeks ago, # ^ |

This is the simplest counterexample I can think of:

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

→ Reply

4 weeks ago, # ^ |

thank you very much.:)

→ Reply

4 weeks ago, # ^ |

how did you solve this question?

→ Reply

djm03178

4 weeks ago, # ^ |

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.

→ Reply

____L___

4 weeks ago, # ^ |

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

→ Reply

https://mirror.codeforces.com/contest/1950/submission/253812424

4 weeks ago, # ^ |

ohk got it. thanks.

→ Reply

sukh_x

4 weeks ago, # |

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

it would be great help!! thanks

→ Reply

jzavaglia

4 weeks ago, # ^ |

← Rev. 2 →

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

→ Reply

Ehsan

4 weeks ago, # |

name of problem D was a hint about its tag.

Spoiler

→ Reply

4 weeks ago, # ^ |

→ Reply

Ehsan

4 weeks ago, # ^ |

it was a troll. (DP : dynamic programming) tag of problem D.

→ Reply

Vampire

4 weeks ago, # |

Just 1 char from AC :sob:

Wa test 2: https://mirror.codeforces.com/contest/1950/submission/253816793

Accepted: https://mirror.codeforces.com/contest/1950/submission/253892875

→ Reply

theFixer

4 weeks ago, # |

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

→ Reply

ishwarendra

4 weeks ago, # ^ |

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

→ Reply

SpecialOperations0

4 weeks ago, # |

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

→ Reply

e3e

4 weeks ago, # |

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

→ Reply

unfettered_one

4 weeks ago, # ^ |

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

→ Reply

e3e

4 weeks ago, # ^ |

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

→ Reply

unfettered_one

4 weeks ago, # ^ |

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)

→ Reply

Imran435

4 weeks ago, # ^ |

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

bool check(vector<int> &arr, int n) {
  if (n == 1)
    return true;

  for (auto x : arr) {
    if (n % x == 0)
      return check(arr, n / x);
  }

  return false;
}

→ Reply

4 weeks ago, # ^ |

← Rev. 3 →

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)

→ Reply

jzavaglia

4 weeks ago, # ^ |

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

→ Reply

weirdflexbutok

4 weeks ago, # ^ |

← Rev. 2 →

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

→ Reply

weirdflexbutok

4 weeks ago, # ^ |

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

→ Reply

e3e

4 weeks ago, # ^ |

← Rev. 2 →

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

→ Reply

Protik_7

4 weeks ago, # |

Waiting for the tutorial of G...

→ Reply

Nsywtz

4 weeks ago, # |

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

→ Reply

4 weeks ago, # ^ |

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.

→ Reply

dmmr328go

4 weeks ago, # ^ |

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://mirror.codeforces.com/contest/1950/submission/253975967

→ Reply