Codeforces Round 937 (Div. 4) Editorial

8 месяцев назад, # |

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

8 месяцев назад, # ^ |

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

→ Ответить

zhy_

8 месяцев назад, # ^ |

thank u

→ Ответить

par4dox

8 месяцев назад, # |

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

→ Ответить

Vampire

8 месяцев назад, # |

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

→ Ответить

DC_H

8 месяцев назад, # ^ |

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

→ Ответить

8 месяцев назад, # ^ |

+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

8 месяцев назад, # ^ |

-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

8 месяцев назад, # ^ |

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

→ Ответить

8 месяцев назад, # ^ |

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

8 месяцев назад, # ^ |

+20

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

→ Ответить

amoad

8 месяцев назад, # ^ |

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

→ Ответить

8 месяцев назад, # ^ |

← 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

8 месяцев назад, # ^ |

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

→ Ответить

8 месяцев назад, # ^ |

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

→ Ответить

_smile

8 месяцев назад, # ^ |

ok, thank u

→ Ответить

flamestorm

8 месяцев назад, # ^ |

+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

8 месяцев назад, # ^ |

← Rev. 2 →

solution you can check this solution for O(1)

→ Ответить

8 месяцев назад, # ^ |

bro u used power function is not o(1)

→ Ответить

8 месяцев назад, # ^ |

int ha=log2(a); is logarithmic

→ Ответить

Y_erasyl

6 месяцев назад, # ^ |

← Rev. 2 →

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

→ Ответить

Husanboy

8 месяцев назад, # ^ |

'cause it is div4 :)

→ Ответить

PrinzeOP

7 месяцев назад, # ^ |

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

→ Ответить

R1nixi

8 месяцев назад, # |

thanks you for the quick editorial and good round!

→ Ответить

8 месяцев назад, # |

-17

Hello I am gokula kannan siva ji

→ Ответить

8 месяцев назад, # ^ |

-10

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

→ Ответить

ilovenandini

8 месяцев назад, # ^ |

don't be sad bro, I upvoted

→ Ответить

8 месяцев назад, # ^ |

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

→ Ответить

destroyer_sam

8 месяцев назад, # |

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

Detailed approach:

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

→ Ответить

8 месяцев назад, # ^ |

← 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

8 месяцев назад, # ^ |

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

→ Ответить

KostyR13

8 месяцев назад, # ^ |

← 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

8 месяцев назад, # ^ |

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

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

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

→ Ответить

8 месяцев назад, # ^ |

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

8 месяцев назад, # ^ |

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/

8 месяцев назад, # ^ |

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

8 месяцев назад, # |

what would be the rating for problem E? just wondering

→ Ответить

aayein__O_O

8 месяцев назад, # ^ |

around 1300

→ Ответить

dhruvokay

8 месяцев назад, # ^ |

realistically 1200-1300, Clist says its 1500:

→ Ответить

a_gt3_rs

8 месяцев назад, # ^ |

← Rev. 2 →

Maybe 1200-1300

→ Ответить

Phuocbua

8 месяцев назад, # ^ |

maybe around 1200-1300, maximum ~1500

→ Ответить

xiorra

8 месяцев назад, # |

thanks for the solutions!

→ Ответить

MrSavageVS

8 месяцев назад, # |

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

8 месяцев назад, # |

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

→ Ответить

saelcc03

8 месяцев назад, # ^ |

try case 1 2 aa

→ Ответить

Barytania_001

8 месяцев назад, # |

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

8 месяцев назад, # |

can someone explain solution to problem E

→ Ответить

8 месяцев назад, # ^ |

brute force check for every factor of n

→ Ответить

dikidikiantasadiki

8 месяцев назад, # ^ |

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

8 месяцев назад, # ^ |

thanks got it now

→ Ответить

GohTengFong

8 месяцев назад, # ^ |

← 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

→ Ответить

8 месяцев назад, # ^ |

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

→ Ответить

8 месяцев назад, # ^ |

← 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

→ Ответить

8 месяцев назад, # ^ |

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

→ Ответить

wsaleem

8 месяцев назад, # ^ |

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

→ Ответить

nflight11

8 месяцев назад, # |

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

8 месяцев назад, # ^ |

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.

8 месяцев назад, # |

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

→ Ответить

8 месяцев назад, # ^ |

Counter Example

→ Ответить

futuristic_coder

8 месяцев назад, # |

← 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

8 месяцев назад, # ^ |

← Rev. 3 →

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

→ Ответить

micha77

8 месяцев назад, # ^ |

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

→ Ответить

micha77

8 месяцев назад, # ^ |

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

8 месяцев назад, # ^ |

← Rev. 2 →

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

→ Ответить

micha77

8 месяцев назад, # ^ |

        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.net/contest/1950/submission/253817219

→ Ответить

futuristic_coder

8 месяцев назад, # ^ |

Got it. Thank You

→ Ответить

ishat_jha

8 месяцев назад, # |

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

→ Ответить

PylyaoTBabyliUltraNysha

8 месяцев назад, # |

← 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

8 месяцев назад, # |

Help Anyone

→ Ответить

heesooyaam

8 месяцев назад, # |

← 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

8 месяцев назад, # |

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

→ Ответить

janY_

8 месяцев назад, # ^ |

+22

💀

→ Ответить

SeineAle

8 месяцев назад, # ^ |

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

→ Ответить

sairamnst

8 месяцев назад, # |

← 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

8 месяцев назад, # |

can someone explain me this approach for problem d ? 253830700

→ Ответить

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

8 месяцев назад, # ^ |

← 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

8 месяцев назад, # |

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

8 месяцев назад, # ^ |

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

8 месяцев назад, # ^ |

Thankss!

→ Ответить

AvaraKedavra

8 месяцев назад, # |

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

8 месяцев назад, # ^ |

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

→ Ответить

sshreyansh962

8 месяцев назад, # |

253824980

WHY IS THIS WRONG QUES 4

→ Ответить

sshreyansh962

8 месяцев назад, # ^ |

→ Ответить

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

8 месяцев назад, # ^ |

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

8 месяцев назад, # ^ |

ok thanku so much,will u share your soln plz

→ Ответить

Dev77G

8 месяцев назад, # ^ |

→ Ответить

tanvir_islam

8 месяцев назад, # |

thanks for very fast editorial.

→ Ответить

Byte_maze

8 месяцев назад, # |

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

→ Ответить

ilovenandini

8 месяцев назад, # ^ |

there are no constraints on n over all test cases.

→ Ответить

i3mr125

8 месяцев назад, # |

← 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

8 месяцев назад, # |

← Rev. 2 →

253841056

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

→ Ответить

von_arrow

8 месяцев назад, # |

← 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

8 месяцев назад, # |

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

→ Ответить

Siddharth_78

8 месяцев назад, # ^ |

boo hoo. grow up.

→ Ответить

-linked-list-

8 месяцев назад, # ^ |

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

→ Ответить

Siddharth_78

8 месяцев назад, # ^ |

so?

→ Ответить

mneo

8 месяцев назад, # |

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

→ Ответить

destroyer_sam

8 месяцев назад, # ^ |

finding biggest component wont work!

look at this

→ Ответить

I_lOVE_ROMAN

8 месяцев назад, # |

← Rev. 2 →

Can anyone share the solution for D by DP?

→ Ответить

dikidikiantasadiki

8 месяцев назад, # ^ |

253844267

→ Ответить

JoeDelaney2012

8 месяцев назад, # |

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

8 месяцев назад, # |

← Rev. 2 →

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

→ Ответить

prb_yes

8 месяцев назад, # |

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

→ Ответить

tickbird

8 месяцев назад, # |

← Rev. 2 →

nvm, my assumption was wrong

→ Ответить

Shivam2105

8 месяцев назад, # |

← Rev. 2 →

→ Ответить

saptarshi1729

8 месяцев назад, # |

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

8 месяцев назад, # |

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

→ Ответить

anhuiwuhuyhb

8 месяцев назад, # ^ |

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

8 месяцев назад, # |

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

8 месяцев назад, # ^ |

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

8 месяцев назад, # |

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

8 месяцев назад, # |

→ Ответить

theRealChainman

8 месяцев назад, # |

Problem G was great

→ Ответить

pranut

8 месяцев назад, # |

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

→ Ответить

Fork512Hz

8 месяцев назад, # |

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

8 месяцев назад, # |

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

8 месяцев назад, # ^ |

It would be updated once the open hacking phase ends.

→ Ответить

dimethylglyoxime

8 месяцев назад, # ^ |

Thank you for the clarification!

→ Ответить

8 месяцев назад, # ^ |

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

8 месяцев назад, # |

← Rev. 2 →

(found)

→ Ответить

8 месяцев назад, # |

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

8 месяцев назад, # ^ |

← Rev. 2 →

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

→ Ответить

8 месяцев назад, # ^ |

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

8 месяцев назад, # ^ |

This is the simplest counterexample I can think of:

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

→ Ответить

8 месяцев назад, # ^ |

thank you very much.:)

→ Ответить

8 месяцев назад, # ^ |

how did you solve this question?

→ Ответить

djm03178

8 месяцев назад, # ^ |

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.

→ Ответить

y_force

5 месяцев назад, # ^ |

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

→ Ответить

____L___

8 месяцев назад, # ^ |

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.net/contest/1950/submission/253812424

8 месяцев назад, # ^ |

ohk got it. thanks.

→ Ответить

sukh_x

8 месяцев назад, # |

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

8 месяцев назад, # ^ |

← Rev. 2 →

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

→ Ответить

elseecay

8 месяцев назад, # |

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

→ Ответить

Ehsan

8 месяцев назад, # |

name of problem D was a hint about its tag.

Spoiler

→ Ответить

8 месяцев назад, # ^ |

→ Ответить

Ehsan

8 месяцев назад, # ^ |

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

→ Ответить

Vampire

8 месяцев назад, # |

Just 1 char from AC :sob:

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

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

→ Ответить

theFixer

8 месяцев назад, # |

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

8 месяцев назад, # ^ |

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

→ Ответить

SpecialOperations0

8 месяцев назад, # |

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

→ Ответить

e3e

8 месяцев назад, # |

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

→ Ответить

unfettered_one

8 месяцев назад, # ^ |

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

8 месяцев назад, # ^ |

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

→ Ответить

unfettered_one

8 месяцев назад, # ^ |

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

8 месяцев назад, # ^ |

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

→ Ответить

8 месяцев назад, # ^ |

← 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

8 месяцев назад, # ^ |

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

→ Ответить

weirdflexbutok

8 месяцев назад, # ^ |

← 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

8 месяцев назад, # ^ |

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

8 месяцев назад, # ^ |

← Rev. 2 →

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

→ Ответить

Protik_7

8 месяцев назад, # |

Waiting for the tutorial of G...

→ Ответить

Nsywtz

8 месяцев назад, # |

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

→ Ответить

8 месяцев назад, # ^ |

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

8 месяцев назад, # ^ |

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

→ Ответить