Codeforces Round 937 (Div. 4) Editorial

6 недель назад, # |

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

→ Ответить

Markusssian

6 недель назад, # ^ |

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

→ Ответить

zhy_

6 недель назад, # ^ |

thank u

→ Ответить

par4dox

6 недель назад, # |

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

→ Ответить

Vampire

6 недель назад, # |

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

→ Ответить

DC_H

6 недель назад, # ^ |

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

→ Ответить

6 недель назад, # ^ |

+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

→ Ответить

Lalit_G11

6 недель назад, # ^ |

-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

→ Ответить

saelcc03

6 недель назад, # ^ |

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

→ Ответить

6 недель назад, # ^ |

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.

→ Ответить

saelcc03

6 недель назад, # ^ |

+20

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

→ Ответить

amoad

6 недель назад, # ^ |

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

→ Ответить

6 недель назад, # ^ |

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

→ Ответить

_smile

6 недель назад, # ^ |

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

→ Ответить

6 недель назад, # ^ |

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

→ Ответить

_smile

6 недель назад, # ^ |

ok, thank u

→ Ответить

flamestorm

6 недель назад, # ^ |

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

→ Ответить

prakhartrivedi3

6 недель назад, # ^ |

← Rev. 2 →

solution you can check this solution for O(1)

→ Ответить

6 недель назад, # ^ |

bro u used power function is not o(1)

→ Ответить

6 недель назад, # ^ |

int ha=log2(a); is logarithmic

→ Ответить

Husanboy

6 недель назад, # ^ |

'cause it is div4 :)

→ Ответить

PrinzeOP

4 недели назад, # ^ |

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

→ Ответить

R1nixi

6 недель назад, # |

thanks you for the quick editorial and good round!

→ Ответить

6 недель назад, # |

-17

Hello I am gokula kannan siva ji

→ Ответить

6 недель назад, # ^ |

-10

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

→ Ответить

ilovenandini

6 недель назад, # ^ |

don't be sad bro, I upvoted

→ Ответить

6 недель назад, # ^ |

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

→ Ответить

destroyer_sam

6 недель назад, # |

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

→ Ответить

6 недель назад, # ^ |

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

→ Ответить

destroyer_sam

6 недель назад, # ^ |

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

→ Ответить

KostyR13

6 недель назад, # ^ |

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

→ Ответить

hara108

6 недель назад, # ^ |

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

→ Ответить

6 недель назад, # ^ |

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.

→ Ответить

han_hyo_joo

6 недель назад, # ^ |

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.

→ Ответить

https://clist.by/problems/

6 недель назад, # ^ |

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.

→ Ответить

Luciefer_x

6 недель назад, # |

what would be the rating for problem E? just wondering

→ Ответить

aayein__O_O

6 недель назад, # ^ |

around 1300

→ Ответить

dhruvokay

6 недель назад, # ^ |

realistically 1200-1300, Clist says its 1500:

→ Ответить

a_gt3_rs

6 недель назад, # ^ |

← Rev. 2 →

Maybe 1200-1300

→ Ответить

Phuocbua

6 недель назад, # ^ |

maybe around 1200-1300, maximum ~1500

→ Ответить

xiorra

6 недель назад, # |

thanks for the solutions!

→ Ответить

MrSavageVS

6 недель назад, # |

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.

→ Ответить

AlephNullams2008

6 недель назад, # |

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

→ Ответить

saelcc03

6 недель назад, # ^ |

try case 1 2 aa

→ Ответить

Barytania_001

6 недель назад, # |

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.

→ Ответить

Gandu_Korotkevich

6 недель назад, # |

can someone explain solution to problem E

→ Ответить

6 недель назад, # ^ |

brute force check for every factor of n

→ Ответить

dikidikiantasadiki

6 недель назад, # ^ |

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.

→ Ответить

Gandu_Korotkevich

6 недель назад, # ^ |

thanks got it now

→ Ответить

GohTengFong

6 недель назад, # ^ |

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

→ Ответить

6 недель назад, # ^ |

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

→ Ответить

6 недель назад, # ^ |

← 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

→ Ответить

6 недель назад, # ^ |

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

→ Ответить

wsaleem

6 недель назад, # ^ |

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

→ Ответить

nflight11

6 недель назад, # |

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.

→ Ответить

nflight11

6 недель назад, # ^ |

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

→ Ответить

ssh.

6 недель назад, # |

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

→ Ответить

6 недель назад, # ^ |

Counter Example

→ Ответить

futuristic_coder

6 недель назад, # |

← 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

→ Ответить

pramana

6 недель назад, # ^ |

← Rev. 3 →

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

→ Ответить

micha77

6 недель назад, # ^ |

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

→ Ответить

micha77

6 недель назад, # ^ |

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.

→ Ответить

futuristic_coder

6 недель назад, # ^ |

← Rev. 2 →

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

→ Ответить

micha77

6 недель назад, # ^ |

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

→ Ответить

futuristic_coder

6 недель назад, # ^ |

Got it. Thank You

→ Ответить

ishat_jha

6 недель назад, # |

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

→ Ответить

PylyaoTBabyliUltraNysha

6 недель назад, # |

← 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();
    }
}

→ Ответить

sasank555

6 недель назад, # |

Help Anyone

→ Ответить

heesooyaam

6 недель назад, # |

← Rev. 3 →

решение за O(log(a)):

Для начала построим полное бинарное дерево наибольшей высоты, используя вершинки первого типа

Как это сделать: найдем наибольшее n такое, что 2 ^ n — 1 <= a, тогда n — будет высотой этого дерева, а свободных ребер(ребер, к которым надо привязать вершинку) будет 2^n

Тогда есть два случая: либо вершинок первого типа не останется, либо их останется a — 2^n — 1 штук, чего не хватит на новый слой. Если вершинок первого типа не осталось, то привязывая к свободным ребрам вершинки второго типа, мы не увеличим количество этих свободных ребер. Тогда ответ — сeil(b / кол-во свободных ребер)

Если же вершинки первого типа остались, то привяжем их на новый слой. Каждая привязанная вершинка даст +1 к количеству свободных ребер. Так как на новом слое еще остались места, нужно заполнить его вершинками второго типа. Если количество свободных мест после расстановки всех вершинок первого типа больше ил равно количества вершинок второго типа, то ответ — n + 1. Иначе вершинок второго типа слишком много, тогда дозаполним новый слой ими, а дальше начнем заполнять новые слои, пока вершины второго типа еще есть. В этом случае ответ n + 1 + ceil(кол-во оставшихся вершин второго типа после заполнения n+1 го слоя / кол-во свободных ребер)

код: 253819555

→ Ответить

Ashar-Usmani

6 недель назад, # |

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

→ Ответить

janY_

6 недель назад, # ^ |

+22

💀

→ Ответить

SeineAle

6 недель назад, # ^ |

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

→ Ответить

sairamnst

6 недель назад, # |

← 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

→ Ответить

rashmi_12345

6 недель назад, # |

can someone explain me this approach for problem d ? 253830700

→ Ответить

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

6 недель назад, # ^ |

← 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

→ Ответить

Harshiv_27

6 недель назад, # |

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?

→ Ответить

650iq

6 недель назад, # ^ |

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

→ Ответить

Harshiv_27

6 недель назад, # ^ |

Thankss!

→ Ответить

AvaraKedavra

6 недель назад, # |

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.

→ Ответить

wsaleem

6 недель назад, # ^ |

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

→ Ответить

sshreyansh962

6 недель назад, # |

253824980

WHY IS THIS WRONG QUES 4

→ Ответить

sshreyansh962

6 недель назад, # ^ |

→ Ответить

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

6 недель назад, # ^ |

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

→ Ответить

sshreyansh962

6 недель назад, # ^ |

ok thanku so much,will u share your soln plz

→ Ответить

Dev77G

6 недель назад, # ^ |

→ Ответить

tanvir_islam

6 недель назад, # |

thanks for very fast editorial.

→ Ответить

Byte_maze

6 недель назад, # |

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

→ Ответить

ilovenandini

6 недель назад, # ^ |

there are no constraints on n over all test cases.

→ Ответить

i3mr125

6 недель назад, # |

← 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

→ Ответить

sairamnst

6 недель назад, # |

← Rev. 2 →

253841056

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

→ Ответить

von_arrow

6 недель назад, # |

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

→ Ответить

Eliminator123

6 недель назад, # |

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

→ Ответить

Siddharth_78

6 недель назад, # ^ |

boo hoo. grow up.

→ Ответить

-linked-list-

6 недель назад, # ^ |

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

→ Ответить

Siddharth_78

6 недель назад, # ^ |

so?

→ Ответить

mneo

6 недель назад, # |

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

→ Ответить

destroyer_sam

6 недель назад, # ^ |

finding biggest component wont work!

look at this

→ Ответить

I_lOVE_ROMAN

6 недель назад, # |

← Rev. 2 →

Can anyone share the solution for D by DP?

→ Ответить

dikidikiantasadiki

6 недель назад, # ^ |

253844267

→ Ответить

JoeDelaney2012

6 недель назад, # |

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

→ Ответить

macaquedev

6 недель назад, # |

← Rev. 2 →

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

→ Ответить

prb_yes

6 недель назад, # |

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

→ Ответить

tickbird

6 недель назад, # |

← Rev. 2 →

nvm, my assumption was wrong

→ Ответить

Shivam2105

6 недель назад, # |

← Rev. 2 →

→ Ответить

saptarshi1729

6 недель назад, # |

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!

→ Ответить

anhuiwuhuyhb

6 недель назад, # |

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

→ Ответить

anhuiwuhuyhb

6 недель назад, # ^ |

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

→ Ответить

FelixNotter

6 недель назад, # |

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

→ Ответить

Dev77G

6 недель назад, # ^ |

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

→ Ответить

arihant_j

6 недель назад, # |

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

→ Ответить

Dev77G

6 недель назад, # |

→ Ответить

theRealChainman

6 недель назад, # |

Problem G was great

→ Ответить

pranut

6 недель назад, # |

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

→ Ответить

Fork512Hz

6 недель назад, # |

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

→ Ответить

dimethylglyoxime

6 недель назад, # |

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.

→ Ответить

Priyansh_Kumar

6 недель назад, # ^ |

It would be updated once the open hacking phase ends.

→ Ответить

dimethylglyoxime

6 недель назад, # ^ |

Thank you for the clarification!

→ Ответить

6 недель назад, # ^ |

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

→ Ответить

jzavaglia

6 недель назад, # |

← Rev. 2 →

(found)

→ Ответить

6 недель назад, # |

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)

→ Ответить

djm03178

6 недель назад, # ^ |

← Rev. 2 →

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

→ Ответить

6 недель назад, # ^ |

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.

→ Ответить

djm03178

6 недель назад, # ^ |

This is the simplest counterexample I can think of:

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

→ Ответить

6 недель назад, # ^ |

thank you very much.:)

→ Ответить

6 недель назад, # ^ |

how did you solve this question?

→ Ответить

djm03178

6 недель назад, # ^ |

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.

→ Ответить

____L___

6 недель назад, # ^ |

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

→ Ответить

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

6 недель назад, # ^ |

ohk got it. thanks.

→ Ответить

sukh_x

6 недель назад, # |

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

it would be great help!! thanks

→ Ответить

jzavaglia

6 недель назад, # ^ |

← Rev. 2 →

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

→ Ответить

elseecay

6 недель назад, # |

туториал здорового человека

→ Ответить

Ehsan

6 недель назад, # |

name of problem D was a hint about its tag.

Spoiler

→ Ответить

6 недель назад, # ^ |

→ Ответить

Ehsan

6 недель назад, # ^ |

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

→ Ответить

Vampire

6 недель назад, # |

Just 1 char from AC :sob:

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

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

→ Ответить

theFixer

6 недель назад, # |

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

→ Ответить

ishwarendra

6 недель назад, # ^ |

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

→ Ответить

SpecialOperations0

6 недель назад, # |

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

→ Ответить

e3e

6 недель назад, # |

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

→ Ответить

unfettered_one

6 недель назад, # ^ |

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

→ Ответить

e3e

6 недель назад, # ^ |

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

→ Ответить

unfettered_one

6 недель назад, # ^ |

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)

→ Ответить

Imran435

6 недель назад, # ^ |

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;
}

→ Ответить

6 недель назад, # ^ |

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

→ Ответить

jzavaglia

6 недель назад, # ^ |

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

→ Ответить

weirdflexbutok

6 недель назад, # ^ |

← 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

→ Ответить

weirdflexbutok

6 недель назад, # ^ |

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

→ Ответить

e3e

6 недель назад, # ^ |

← Rev. 2 →

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

→ Ответить

Protik_7

6 недель назад, # |

Waiting for the tutorial of G...

→ Ответить

Nsywtz

6 недель назад, # |

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

→ Ответить

6 недель назад, # ^ |

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.

→ Ответить

dmmr328go

6 недель назад, # ^ |

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

→ Ответить