Codeforces Round 937 (Div. 4) Editorial

8 months 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

8 months ago, # ^ |

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

→ Reply

zhy_

8 months ago, # ^ |

thank u

→ Reply

par4dox

8 months ago, # |

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

→ Reply

Vampire

8 months ago, # |

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

→ Reply

DC_H

8 months ago, # ^ |

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

→ Reply

8 months 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

8 months 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

8 months 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

8 months 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

8 months ago, # ^ |

+20

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

→ Reply

amoad

8 months ago, # ^ |

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

→ Reply

8 months 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

8 months 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

8 months ago, # ^ |

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

→ Reply

_smile

8 months ago, # ^ |

ok, thank u

→ Reply

flamestorm

8 months 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

8 months ago, # ^ |

← Rev. 2 →

solution you can check this solution for O(1)

→ Reply

8 months ago, # ^ |

bro u used power function is not o(1)

→ Reply

8 months ago, # ^ |

int ha=log2(a); is logarithmic

→ Reply

Y_erasyl

6 months ago, # ^ |

← Rev. 2 →

can someone please explain why my code fails in task F https://mirror.codeforces.com/contest/1950/submission/262901913

→ Reply

Husanboy

8 months ago, # ^ |

'cause it is div4 :)

→ Reply

PrinzeOP

7 months ago, # ^ |

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

→ Reply

R1nixi

8 months ago, # |

thanks you for the quick editorial and good round!

→ Reply

8 months ago, # |

-17

Hello I am gokula kannan siva ji

→ Reply

8 months ago, # ^ |

-10

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

→ Reply

ilovenandini

8 months ago, # ^ |

don't be sad bro, I upvoted

→ Reply

8 months ago, # ^ |

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

→ Reply

destroyer_sam

8 months 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

8 months 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

8 months ago, # ^ |

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

→ Reply

KostyR13

8 months 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

8 months 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

8 months 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

8 months 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/

8 months 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

8 months ago, # |

what would be the rating for problem E? just wondering

→ Reply

aayein__O_O

8 months ago, # ^ |

around 1300

→ Reply

dhruvokay

8 months ago, # ^ |

realistically 1200-1300, Clist says its 1500:

→ Reply

a_gt3_rs

8 months ago, # ^ |

← Rev. 2 →

Maybe 1200-1300

→ Reply

Phuocbua

8 months ago, # ^ |

maybe around 1200-1300, maximum ~1500

→ Reply

xiorra

8 months ago, # |

thanks for the solutions!

→ Reply

MrSavageVS

8 months 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

8 months ago, # |

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

→ Reply

saelcc03

8 months ago, # ^ |

try case 1 2 aa

→ Reply

Barytania_001

8 months 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

8 months ago, # |

can someone explain solution to problem E

→ Reply

8 months ago, # ^ |

brute force check for every factor of n

→ Reply

dikidikiantasadiki

8 months 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

8 months ago, # ^ |

thanks got it now

→ Reply

GohTengFong

8 months ago, # ^ |

← Rev. 2 →

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

8 months ago, # ^ |

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

→ Reply

8 months 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

8 months ago, # ^ |

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

→ Reply

wsaleem

8 months ago, # ^ |

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

→ Reply

nflight11

8 months 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

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

8 months 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

8 months ago, # ^ |

Counter Example

→ Reply

futuristic_coder

8 months 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

8 months ago, # ^ |

← Rev. 3 →

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

→ Reply

micha77

8 months ago, # ^ |

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

→ Reply

micha77

8 months 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

8 months 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

8 months 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

8 months ago, # ^ |

Got it. Thank You

→ Reply

ishat_jha

8 months ago, # |

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

→ Reply

PylyaoTBabyliUltraNysha

8 months 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

8 months ago, # |

Help Anyone

→ Reply

Ashar-Usmani

8 months ago, # |

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

→ Reply

janY_

8 months ago, # ^ |

+22

💀

→ Reply

SeineAle

8 months ago, # ^ |

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

→ Reply

sairamnst

8 months 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

8 months ago, # |

can someone explain me this approach for problem d ? 253830700

→ Reply

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

8 months 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

8 months 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

8 months 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

8 months ago, # ^ |

Thankss!

→ Reply

AvaraKedavra

8 months 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

8 months ago, # ^ |

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

→ Reply

sshreyansh962

8 months ago, # |

253824980

WHY IS THIS WRONG QUES 4

→ Reply

sshreyansh962

8 months ago, # ^ |

→ Reply

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

8 months 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

8 months ago, # ^ |

ok thanku so much,will u share your soln plz

→ Reply

Dev77G

8 months ago, # ^ |

→ Reply

tanvir_islam

8 months ago, # |

thanks for very fast editorial.

→ Reply

Byte_maze

8 months 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

8 months ago, # ^ |

there are no constraints on n over all test cases.

→ Reply

i3mr125

8 months 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

8 months ago, # |

← Rev. 2 →

253841056

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

→ Reply

von_arrow

8 months 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

8 months ago, # |

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

→ Reply

Siddharth_78

8 months ago, # ^ |

boo hoo. grow up.

→ Reply

-linked-list-

8 months ago, # ^ |

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

→ Reply

Siddharth_78

8 months ago, # ^ |

so?

→ Reply

mneo

8 months ago, # |

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

→ Reply

destroyer_sam

8 months ago, # ^ |

finding biggest component wont work!

look at this

→ Reply

I_lOVE_ROMAN

8 months ago, # |

← Rev. 2 →

Can anyone share the solution for D by DP?

→ Reply

dikidikiantasadiki

8 months ago, # ^ |

253844267

→ Reply

JoeDelaney2012

8 months 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

8 months ago, # |

← Rev. 2 →

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

→ Reply

prb_yes

8 months 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

8 months ago, # |

← Rev. 2 →

nvm, my assumption was wrong

→ Reply

Shivam2105

8 months ago, # |

← Rev. 2 →

→ Reply

saptarshi1729

8 months 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

8 months 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

8 months 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

8 months 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

8 months 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

8 months 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

8 months ago, # |

→ Reply

theRealChainman

8 months ago, # |

Problem G was great

→ Reply

pranut

8 months ago, # |

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

→ Reply

Fork512Hz

8 months 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

8 months 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

8 months ago, # ^ |

It would be updated once the open hacking phase ends.

→ Reply

dimethylglyoxime

8 months ago, # ^ |

Thank you for the clarification!

→ Reply

8 months 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

8 months ago, # |

← Rev. 2 →

(found)

→ Reply

8 months 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

8 months ago, # ^ |

← Rev. 2 →

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

→ Reply

8 months 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

8 months ago, # ^ |

This is the simplest counterexample I can think of:

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

→ Reply

8 months ago, # ^ |

thank you very much.:)

→ Reply

8 months ago, # ^ |

how did you solve this question?

→ Reply

djm03178

8 months 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

y_force

5 months ago, # ^ |

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

→ Reply

____L___

8 months 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

8 months ago, # ^ |

ohk got it. thanks.

→ Reply

sukh_x

8 months 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

8 months 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

8 months ago, # |

name of problem D was a hint about its tag.

Spoiler

→ Reply

8 months ago, # ^ |

→ Reply

Ehsan

8 months ago, # ^ |

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

→ Reply

Vampire

8 months 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

8 months 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

8 months ago, # ^ |

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

→ Reply

SpecialOperations0

8 months ago, # |

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

→ Reply

e3e

8 months ago, # |

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

→ Reply

unfettered_one

8 months 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

8 months ago, # ^ |

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

→ Reply

unfettered_one

8 months 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

8 months 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

8 months 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

8 months ago, # ^ |

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

→ Reply

weirdflexbutok

8 months 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

8 months 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

8 months ago, # ^ |

← Rev. 2 →

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

→ Reply

Protik_7

8 months ago, # |

Waiting for the tutorial of G...

→ Reply

Nsywtz

8 months 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

8 months 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

8 months 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