Блог пользователя diskoteka

Автор diskoteka, 4 года назад, По-русски

1822A - Лента TubeTube

Идея: diskoteka, разработка: Vladosiya

Разбор
Решение
Оценка задачи

1822B - Карина и массив

Идея: playerr17, разработка: playerr17

Разбор
Решение
Оценка задачи

1822C - Любитель булочек

Идея: diskoteka, разработка: diskoteka

Разбор
Решение
Оценка задачи

1822D - Супер-перестановка

Идея: isosto, pavlekn, разработка: diskoteka

Разбор
Решение
Оценка задачи

1822E - Делаем антипалиндромы

Идея: pavlekn, разработка: pavlekn

Разбор
Решение
Оценка задачи

1822F - Подружки-садоводы

Идея: playerr17, разработка: playerr17

Разбор
Решение
Оценка задачи

1822G1 - Магические тройки (простая версия)

Идея: pavlekn, разработка: pavlekn

Разбор
Решение
Оценка задачи

1822G2 - Магические тройки (сложная версия)

Идея: pavlekn, разработка: pavlekn

Разбор
Решение
Оценка задачи
Разбор задач Codeforces Round 867 (Div. 3)
  • Проголосовать: нравится
  • +51
  • Проголосовать: не нравится

»
4 года назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

G2 can be solved by going threw array from left to right and for every i get all divisors of a[i] and for perfect square divisors X increase answer by cnt[a[i] / X] * cnt[a[i] / sqrt(X)]. We just need to get divisors using prime factorization which we can get by going only threw prime numbers [1, sqrt(10^9)].

»
4 года назад, скрыть # |
← Rev. 3  
Проголосовать: нравится -7 Проголосовать: не нравится

G2 can be solved by going threw array from left to right and for every i get all divisors of a[i] and for perfect square divisors X increase answer by cnt[a[i] / X] * cnt[a[i] / sqrt(X)]. We just need to get divisors using prime factorization which we can get by going only threw prime numbers [1, sqrt(10^9)] (only ~3000).

»
4 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Here. Problem F. Gardening Friends can be solve easily using REROOTING TECHNIQUE.

»
4 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +18 Проголосовать: не нравится

Alternatively for g2, we can prime factorize the number to look for candidates for k. Apparently prime factorization can be done with pollard(although I didn’t do this) and the number of perfect squares can be found in logM (someone needs to prove this I suck at math). Essentially g2 can be solved in o(n*M^1/4).

For the log constant on m, you can notice that the number of perfect squares is the number of each p divided by 2 and choosing how much of each p exists. The number of terms is maximum 6 or approximately 2^6 operations. If someone has a better analysis of this it would be greatly appreciated.

»
4 года назад, скрыть # |
 
Проголосовать: нравится +14 Проголосовать: не нравится

Also we can solve G2 with pointers and achieve better complexity without unordered map.

»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Editorial for C missing last few characters

»
4 года назад, скрыть # |
 
Проголосовать: нравится -14 Проголосовать: не нравится

F can also be solved using rerooting dp.

Here is my submission.

»
4 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Can someone hack this solution

It should get a TLE verdict.

»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I don't know why my solution was not TLE. Could you help me? This is my g2 solution

»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

nice div3

»
4 года назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

Can someone pls tell why I am getting TLE at test 16 For Problem G1 even though my idea is same as the official editorial. Link of submission: (https://codeforces.me/contest/1822/submission/203514583)

»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can u give a test cases where this solution did not pass link of my solution https://pastebin.ubuntu.com/p/kVh39TVsk5/

  • »
    »
    4 года назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Input
    Expected output
    Your output
    Explanation
»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How does one solve D? Is it just finding the pattern? I could only figure out that there is no answer for odd (>1) and n would be the first number.

»
4 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +8 Проголосовать: не нравится

I think $$$a=[n, 1, n−2, 3, n−4, 5, …, n−1, 2]$$$ is wrong.

Isn't it $$$a=[n, 1, n−2, 3, n−4, 5, …, 2, n-1]$$$.

That's how your code is written.

»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Does 10 ^ 8 complexity passes in CF ?? asking becouse of editorial of G1

»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Alternative Solution for Problem F

Intuition and Solution

-> Code

  • »
    »
    4 года назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится 0 Проголосовать: не нравится

    thank you so much for the solution, it was way more simpler to understand

    however i dont really get why we dont have to also DFS from the other end point of the diameter (which can be found in the process of DFS from A) but only from A to find the answer?

    • »
      »
      »
      4 года назад, скрыть # ^ |
       
      Проголосовать: нравится +1 Проголосовать: не нравится
      Let's dive in and Think of it.
»
4 года назад, скрыть # |
 
Проголосовать: нравится +19 Проголосовать: не нравится

how to tell that the time complexity for G2 passes ? O(M^(1/3)nlogn) seems bigger than 10^8 for M = 10^9, n = 2*10^5

»
4 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Where can I have a mistake?:

Problem F — Wrong answer on test 36.

But it works:

Problem F — Accepted.

»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I should definitely stop complicating problems. I used Binary Lifting to solve F.

If anybody wants to check the stupid submission: 203630946.

»
4 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Yet another solution for G2 using sqrt decomposition(excuse my English):

First,for each prime number in (1e9^(1/4),1e9^(1/2)],simply iterate over all multiples of its square.The time complexity is at most O(M^(1/2)lnM^(1/2)),and it is clear that each number <=1e9 can have at most one of these square numbers as its factor because (1e9^(1/4))^2*(1e9^(1/4))^2=1e9,so we can precalculate it using std::map in O(M^(1/2)lnM^(1/2)logM^(1/2)).

Next,for each number,iterate over all prime numbers in [2,1e9^(1/4)].It doesn't takes long since there are less than 100 primes in [2,1e9^(1/4)].Then check the map for its factor in (1e9^(1/4),1e9^(1/2)] (if exist) in O(logM).At last,iterate over all its factors.Since 2^2*3^2*5^2*7^2*11^2*13^2~=9e8,there are at most 2^6=64 factors to iterate over for a single number.The total time complexity is O(M^(1/2)log^2(M^(1/2))+(100+logM+64)n). Solution:203320262

»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

For F you can dfs 3 times to find the maximum distance to the leaves.

»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

really good contest! still curious about how you guys figure E out want to know how you think and fix this problem, is that two maximum number in the tutorial the most important?

»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I don't understand the tutorial of G1. Can someone explay it in newbie language? ∑ni=1(cnt[ai]−1)⋅(cnt[ai]−2) I don't know exactly what are we doing here

»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

The key to question E is to figure out that if m*2>=k, the answer is m/2+m%2,isn't it? In other words,there must exist some way to match every two pairs that are not the same letter when m*2>=k. I probably know how to prove it through mathematical induction, it may seem unnecessary though.

»
4 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

In problem F cant both down1[p] and down2[p] lie in the subtree of v? playerr17

also please explain what is int64_t ans = -1'000'000'000'000'000'002;

»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

why is this not passing? code is in segfault function

https://codeforces.me/contest/1822/submission/205472462

»
4 года назад, скрыть # |
← Rev. 4  
Проголосовать: нравится 0 Проголосовать: не нравится

UPD: solved it.

The tutorial for G2 says the time complexity $$$O(n \cdot M^{\frac{1}{3}} \cdot \text{log } n)$$$ with the use of std::map will pass. Why does my solution TLEs then?

https://codeforces.me/contest/1822/submission/205547154

pavlekn what do you mean? I don't understand.

»
4 года назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

deleted comment

»
3 года назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

Another solution for G2, I believe is much simpler but is somehow getting tle. Can someone verify this?

*Time Complexity: O(n*pow(M,1/3)) *Idea:

  • Array a has distinct sorted numbers and hash map f stores the frequency of these.
  • Also, a[i]*b==a[j] and a[j]*b==a[k]
  • thus a[i]*b*b==a[k]
  • From the above equation, b should lie in range [1 , pow(a[k]/a[j],1/2)] or [1,pow(M,1/2)] here is M is max(a).
  • Now, for i>=pow(M,1/3) we have b in range [1,sqrt(M/pow(M,1/3))] = [1,sqrt(pow(M,2/3))] = [1,pow(M,1/3)] .
  • so we loop through this entire range of b if i>1000 ( as elements are distinct and sorted i>1000 means a[i]>1000 ). Hence, O(n*pow(M,1/3))
  • Also for i<pow(M,1/3) we can iterate through all j>i => O(n*pow(M,1/3))

so we have ensured that time complexity is O(n*pow(M,1/3)) submission

pavlekn Help Orz

»
11 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
// I think Best solution/code of G1-G2 is this :


ll MAX_VAL = 1e9, k = 1e6;

void solve(){
    ll n; cin >> n;
    map<ll,ll> cnt;
    vector<ll>a(n);
    for(ll i=0;i<n;i++){ cin>>a[i]; cnt[a[i]]++; }
    ll ans=0, flip;

    for(auto it=cnt.begin(); it!=cnt.end(); ++it){
        ll num=it->first, val=it->second;
        flip = (num<=k ? num : k);

        for(ll b=2; b*b<=flip; ++b){
            if(num%b) continue;

            if(num*b<=MAX_VAL && cnt.count(num/b) && cnt.count(num*b))
                ans += cnt[num/b]*cnt[num*b]*val;

            if(b*b!=num){
                ll z = num*num/b;
                if(z<=MAX_VAL && cnt.count(b) && cnt.count(z))
                    ans += cnt[b]*cnt[z]*val;
            }
        }

        if(num>1 && num*num<=MAX_VAL && cnt.count(1) && cnt.count(num*num))
            ans += cnt[1]*cnt[num*num]*val;

        ans += val*(val-1)*(val-2);
    }
    cout << ans << '\n';
}

// and logic is simple for G1 because we want all divisor of x<=1e6 so this can be done in root(1e6) 
// and for G2 we have two condition :
// if(x<=1e6) as same as above
// else(this is between 1e6 and 1e9) so every time we calculate this x/b x x*b so we know that x*b<=1e9 but 
// x>=1e6 so b<=1e3=root(1e9) so this align perfectly with above code.
»
10 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Is there any proof for D.