IEEEXtreme 17.0 Problems Discussion

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
32:37:16
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

IEEEXtreme 17.0 Problems Discussion

Автор noomaK, история, 13 месяцев назад, По-английски

Yesterday IEEEXtreme 17.0 was held, and there are a lot of problems to upsolve, so let's discuss problems here.

If there is a problem that you can't solve, maybe ask here and someone will help!

I will start with this problem, Cool Sum, I couldn't get more than 50% points and the only thing that came up online while searching for similar problems is “Generating Functions”, help.

upsolve, help, ieeextreme

noomaK
13 месяцев назад
41

Комментарии (39)

Показать архивные | Написать комментарий?

-is-this-fft-

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

+19

Can you make a PDF of the problemset? IEEEXtreme is famously very closed. I can't access the problem you want help with, it sounds cool.

→ Ответить

noomaK

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

← Rev. 3 →

All the tasks from some of previous IEEEXtreme contests can be found here, https://csacademy.com/ieeextreme-practice/tasks/

Maybe try logging in csacademy ?

→ Ответить

-is-this-fft-

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

Yes, weirdly I can now access it...

→ Ответить

bicsi

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

← Rev. 2 →

+49

For Cool Sum, there's a "trick" for computing sums of binomial coefficients with step $$$k$$$:

Let's look at the binomial formula: $$$(1+X)^n = \sum_{i=0}^n \binom{n}{i}X^i$$$.

The "trick" is to consider $$$X$$$ as the $$$k$$$-th roots of unity. This is because they wrap around when multiplied to the $$$k$$$-th power.

In essence, for some $$$\omega$$$ where $$$\omega^k = 1$$$ you have that:

$$$(1 + \omega)^n = \sum_{i=0}^n \binom{n}{i}\omega^i = \sum_{i=[0:n:k]} \binom{n}{i} + \omega \sum_{i=[1:n:k]} \binom{n}{i} + \ldots + \omega^{k-1} \sum_{i=[k-1:n:k]} \binom{n}{i} $$$.

Here $$$[a:b:c]$$$ is the set of numbers starting from $$$a$$$ until $$$b$$$ with step $$$c$$$ (similar to Python notation of slices).

So, in essence, $$$(1 + \omega)^n = ans_0 + ans_1 \omega + \ldots + ans_{k-1} \omega^{k-1}$$$. In other words, it's the answer (seen as a polynomial) evaluated in $$$\omega$$$.

Now, the FFT/NTT step comes naturally: first, compute $$$(1 + \omega_i)^n$$$ for all $$$\omega_i$$$ $$$k$$$-th roots of unity. Then, interpolate the polynomial given these $$$k$$$ $$$(\omega_i, (1 + \omega_i)^n)$$$ pairs. Because the $$$\omega_i$$$ are roots of unity, the "interpolation" can, in fact, be achieved by simply applying the inverse DFT on the array given by $$$(1 + \omega_i)^n$$$.

→ Ответить

TheoGermal

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

did you manage to solve Rectangles and Polygon Cutting?. I wasn't able to solve both. It'd be great if you share your intuitions for these

→ Ответить

DeadPixel99

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

polygon cutting

→ Ответить

noomaK

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

For the Rectangles, you can create a graph where there is an edge between $$$i$$$ and $$$j$$$ if $$$i$$$ and $$$j$$$ are coprime, then you can iterate over the cliques in this graph and calculate the maximum sum of a clique.

This seems to pass within the TL when you don't consider the elements that are coprime with everything else.

→ Ответить

Morphymorphymorphy

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

True. But max independent set is NP hard. So I used a bitmask DP with time complexity O(2^25 * poly), considering the set of prime factors used below 100.

→ Ответить

Morphymorphymorphy

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

+18

Cool sum:

Very short solution: Answer is the coefficients of (1+x)^n.

More details: In FFT, the degrees are "cyclic", which means x^a * x^b = x^((a+b)%L), where L=2^k is the length of FFT. So even if n is very large, the degree of each term in (1+x)^n is taken modulo by 2^k.

a[0] = a[1] = 1; // a is initialized as (1+x)
FFT(a, L);
for (int i = 0; i < L; i++) a[i] = POWER(a[i], n);
FFT(a, L, -1);

→ Ответить

bicsi

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

← Rev. 2 →

Actually, the answer is the coefficients of $$$(1 + X)^n \textbf{ mod } (X^k - 1)$$$, which happens to be exactly the ring under which DFT space works.

→ Ответить

aryanc403

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

It should be $$$(1 + X)^n \textbf{ mod } (-1 + X^k)$$$ ?

→ Ответить

bicsi

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

You are right. Fixed, thanks!

→ Ответить

visho33

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

Someone knows how to solve Dice?

→ Ответить

Morphymorphymorphy

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

+26

The answer is the n-th coefficient of generating function $$$(D^1+D^2+...+D^k)/k$$$, where $$$D=(x^1+x^2+...+x^6)/6$$$ represents a single die. Simplify the formula and you will finally get something easy to calculate.

→ Ответить

mo_onrabbit2

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

Could you please elaborate a bit more? I can only think of methods using FFT, which is too slow.

→ Ответить

Morphymorphymorphy

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

+10

$$$(D^1+\cdots+D^k)/k=\dfrac{D^1-D^{k+1}}{(1-D)k}$$$

Continue on substituting with $$$D=\dfrac{x^1-x^7}{6(1-x)}$$$

And finally you can get the n-th coefficient of the formula without FFT.

→ Ответить

mo_onrabbit2

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

Got it, thanks! It is quite surprising that inverse part can be done in a way without involving complex methods.

→ Ответить

HliasBoss

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

Could you explain a bit more how you get the nth coefficient of that polynomial? I'm struggling with the division.

→ Ответить

noomaK

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

Can I get a hint for Powerful Strings?

→ Ответить

0xEmadeddin

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

-42

It’s dp on aho corasick dp[length][node]

for len=0....n
   for j=0....m
     for c = 0.....25
        int nx=nxt[j][c] 
        dp[len+1][nx]+=dp[len][j]*pw[cnt[nx]]

with some optimizations.

→ Ответить

golikovnik

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

+31

Elaborating on "some optimizations":

Let's create matrix $$$A$$$, where $$$A[x, y] = \operatorname{pw}[\operatorname{cnt}[y]] * \operatorname{edges}[x, y]$$$, where $$$\operatorname{edges}[x, y]$$$ is a number of transitions in Aho-Corasick automaton from $$$x$$$ to $$$y$$$. Now answer is equal to the sum of coefficients $$$A^n[1, i]$$$.

Let's denote the answer for given $$$n$$$ as $$$f[n]$$$, then $$$f[n]$$$ follows a linear recurrence of size $$$m$$$, where $$$m$$$ is a size of matrix $$$A$$$. Therefore, you can find first $$$2 \cdot m$$$ values of $$$f[n]$$$ with DP in time $$$O(m^2 \cdot 26)$$$, find the linear recurrence in $$$O(m^2)$$$ with Berlekamp-Massey, and after that you need to find $$$n$$$-th element of linear recurrence, which can be done in $$$O(m^2 \cdot \log N)$$$ with polynomial exponentiation, or even in $$$O(m \log m \log N)$$$ with FFT.

→ Ответить

0xEmadeddin

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

-25

Why tf I’m getting these downvotes?

→ Ответить

noomaK

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

I tried doing that, but I keep getting only 40%, this is my code.

I generated more than $$$2 \cdot m$$$ elements of the sequence then used Berlekamp-Massey, but I get WA on most cases.

Can you please provide a link to your code, or tell me what's wrong with my approach?

→ Ответить

golikovnik

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

+16

In line 137 it should be cnt[root] += 1;, not cnt[root] = 1;. It is not guaranteed that the input strings are distinct.

→ Ответить

noomaK

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

+13

Thank you!! That was really stupid of me, I just got 100%.

→ Ответить

kostia244

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

← Rev. 2 →

+29

For those wondering why you have 9 on cosinus peoblem. Try reading negative numbers incorrectly. First read the integer part(with minus), then read the fractional part(as positive number) and ADD them. So when you see -1.1 solve the problem for -1.0 + 0.1 = -0.9.

Upd: 0.9 -> -0.9, a typo

→ Ответить

AbdelmagedNour

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

+19

actually it doesn’t matter 0.9 or -0.9 because cos(-x) = cos(x)

→ Ответить

Morphymorphymorphy

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

+11

No wonder. During the contest, I had already known that the test data is wrong. A lot of strong teams got the same 9 points, and our team's solution had been revised for a whole day :(

→ Ответить

vivivi

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

BTW, what was the solution?

→ Ответить

aVanwithaMan

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

How to solve Rumors ?

→ Ответить

DeadPixel99

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

The idea is simple Get every connected component using only "??" edges And now you can test every component alone. If someone in the component has an in degree edge "->" then the whole component fails to be the source other wise all of them are possible sources.

→ Ответить

tenzen

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

Make a weighted tree, i.e., If a->b exists: add edge (a, b, 1), (b, a, -1) For a ?? b add edge (a, b, 0), (b, a, 0)

For each node as root find the sum of weight of edge going away from root. If the sum is exactly equal to the number of edges a->b (form) then it is a possible source. Basically, you need to find sum of weight of edge for every node as root node. For this, you will do rerooting.

Here's my accepted code:

Code

#include<bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ones(x) __builtin_popcountll(x)
#define int long long
#define pii pair<int,int>
#define mii map<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vpii vector<pair<int, int>>
using namespace std;
const int mod = 1e9+7;
const int N = 2e5+5;

vpii adj[N];
int val[N];

void dfs(int node, int par = -1){
	val[node] = 0;
	for (auto i:adj[node]) {
        int v = i.first, w = i.second;
        if (v!=par){
            dfs(v, node);
            val[node] += val[v] + w;
        }
	}
}

void dfs1(int node, int par = -1){
	for (auto i:adj[node]){
        int v = i.first, w = i.second;
        if (v==par) continue;
        val[v] = val[node] - 2 * w;
        dfs1(v, node);
    }
}

signed main() {
	int n; cin>>n;
    int k = 0;
    map<string, int> m;
    int cnt_dir = 0;
    for (int i = 0;i<n;i++){
    	string s,t,u;
    	cin>>s>>t>>u;
    	if (m.count(s)==0) m[s]=k++;
    	if (m.count(u)==0) m[u]=k++;
    	if (t=="->"){
    		cnt_dir++;
    		adj[m[s]].emplace_back(m[u], 1);
    		adj[m[u]].emplace_back(m[s], -1);
    	} else {
    		adj[m[s]].emplace_back(m[u], 0);
    		adj[m[u]].emplace_back(m[s], 0);
    	}
    }
    dfs(0);
    dfs1(0);
    bool poss[k] = {0};
    for (int i = 0;i<k;i++){
    	if (val[i]==cnt_dir) poss[i] = 1;
    }
    for (auto i:m){
        string s = i.first;
        if(poss[i.second]) cout<<s<<'\n';
    	// if (poss[v]) cout<<s<<'\n';
    }
    return 0;
}

→ Ответить

Malacoda

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

← Rev. 2 →

How to solve Theme Park?

I only managed to get 60 points by floyd-warshall, iterating over all edges as options, taking the best option, and if d = 2, take the best option after taking the one selected before.

This might be not the best answer, as maybe you can take two edges that are not the best, but their sum are the best. But I didn't know any better approximation

→ Ответить

golikovnik

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

It is enough to consider only pairs of edges which have a common vertex (either starting or ending one), which leads to $$$O(n^3)$$$ solution.

Why: let's say we have a pair of edges $$$(u \to v)$$$ and $$$(x \to y)$$$, then at least one of options $$$u := x$$$, $$$x := u$$$, $$$v := y$$$, $$$y := v$$$ is not worse. You can prove it by contradiction by writing down inequalities.

→ Ответить

eGoMask

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

← Rev. 2 →

how i solve Rumors problem ?

→ Ответить

tenzen

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

Make a weighted tree, i.e., If a->b exists: add edge (a, b, 1), (b, a, -1) For a ?? b add edge (a, b, 0), (b, a, 0)

Here's my accepted code:

Code

#include<bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ones(x) __builtin_popcountll(x)
#define int long long
#define pii pair<int,int>
#define mii map<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vpii vector<pair<int, int>>
using namespace std;
const int mod = 1e9+7;
const int N = 2e5+5;

vpii adj[N];
int val[N];

void dfs(int node, int par = -1){
	val[node] = 0;
	for (auto i:adj[node]) {
        int v = i.first, w = i.second;
        if (v!=par){
            dfs(v, node);
            val[node] += val[v] + w;
        }
	}
}

void dfs1(int node, int par = -1){
for (auto i:adj[node]){
        int v = i.first, w = i.second;
        if (v==par) continue;
        val[v] = val[node] - 2 * w;
        dfs1(v, node);
    }
}

signed main() {
	int n; cin>>n;
    int k = 0;
    map<string, int> m;
    int cnt_dir = 0;
    for (int i = 0;i<n;i++){
    	string s,t,u;
    	cin>>s>>t>>u;
    	if (m.count(s)==0) m[s]=k++;
    	if (m.count(u)==0) m[u]=k++;
    	if (t=="->"){
    		cnt_dir++;
    		adj[m[s]].emplace_back(m[u], 1);
    		adj[m[u]].emplace_back(m[s], -1);
    	} else {
    		adj[m[s]].emplace_back(m[u], 0);
    		adj[m[u]].emplace_back(m[s], 0);
    	}
    }
    dfs(0);
    dfs1(0);
    bool poss[k] = {0};
    for (int i = 0;i<k;i++){
    	if (val[i]==cnt_dir) poss[i] = 1;
    }
    for (auto i:m){
        string s = i.first;
        if(poss[i.second]) cout<<s<<'\n';
    	// if (poss[v]) cout<<s<<'\n';
    }
    return 0;
}

→ Ответить

aprohACk

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

You can erase all nodes you can reach from any node in a path where the first edge is directed (the -> edges). The answer are the remaining nodes. This is because, if a-> b, then obviously b can't be the source of the rumour. a, or an ancestor of a must be the source. Now, as b heard the rumour, all edges that the node b has should be directed from b, say b-> x for all edges b ?? x

Why?

Then, x heard the rumour and you can continue erasing nodes until there are only left nodes with ?? edges and no -> edges.

My Code

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ff first
#define ss second
using namespace std;
int n;
int in[100009];
int out[100009];
map<string, int> mapa;
string names[100009];
vector<int>adj[100009][2];// 0 for normal, 1 for directed
bool vis[100009];
bool erased[100009];

void dfs(int node, int parent){
    //cout << " at " << names[node] << endl;
    vis[node] = true;
    erased[node] = true;
    for(int i = 0 ; i < adj[node][1].size() ; i ++){
        int v = adj[node][1][i];
        if(v == parent)continue;
        if(!vis[v])dfs(v, node);
        //erased[v] = true;
    }
    for(auto j : adj[node][0]){
        if(j == parent)continue;
        if(!vis[j])dfs(j, node);
        //erased[j] = true;
    }
}


int main(){
    cin >> n;
    string a, b, how;
    int cur = 0 ;
    for(int i = 0 ; i <= n+3 ; i ++){
        in[i] = 0;
        out[i] = 0;
    }
    for(int i = 0 ; i < n ; i++){
        cin >> a >> how >> b;
        if(mapa.count(a) == 0){
            names[cur] = a;
            mapa[a] = cur ++ ;
        }
        if(mapa.count(b) == 0){
            names[cur] = b;
            mapa[b] = cur ++ ;
        }
        int A = mapa[a], B = mapa[b];
        bool isDir = how[0] == '-';
        if(isDir){
            in[B] ++ ;
            adj[A][1].pb(B);
            out[A] ++ ;
        }else{
            adj[A][0].pb(B);
            adj[B][0].pb(A);
        }
    }
    memset(vis, false, sizeof vis);
    memset(erased, false, sizeof erased);
    for(int i = 0 ; i <= n+1 ; i ++){
        if(in[i] == 0 and out[i] > 0){
            //vis[i] = true;
            for(auto j : adj[i][1]){
                if(!vis[j])dfs(j, i);
            }
        }
    }
    if(cur != n+1){
        return 0;
    }
    for(auto i : mapa){
        if(!erased[i.ss])cout << i.ff << "\n";
    }

    
}

→ Ответить

salhawamde1

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

How to solve happy numbers and Labradoodle?

→ Ответить

noomaK

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

For Labradoodle, you can solve it by brute forcing every prefix and suffix of the potential words, and checking for their existance using std::map or something like that then checking for ambiguity, if you're having a hard time implementing that you can check my code here.

As for Happy Numbers, you need to know Digit DP before you can solve it, so you can try learning that then coming back to it.

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 22.11.2024 08:57:44 (j1).

Десктопная версия, переключиться на мобильную.

При поддержке