IEEEXtreme 17.0 Problems Discussion

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

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

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
2 года назад
41

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

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

-is-this-fft-

2 года назад, скрыть # |

+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

2 года назад, скрыть # ^ |

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

2 года назад, скрыть # ^ |

Yes, weirdly I can now access it...

→ Ответить

bicsi

2 года назад, скрыть # |

← 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

2 года назад, скрыть # |

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

2 года назад, скрыть # ^ |

polygon cutting

→ Ответить

noomaK

2 года назад, скрыть # ^ |

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.

→ Ответить

Morphed

2 года назад, скрыть # ^ |

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.

→ Ответить

Morphed

2 года назад, скрыть # |

+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

2 года назад, скрыть # ^ |

← 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

2 года назад, скрыть # ^ |

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

→ Ответить

bicsi

2 года назад, скрыть # ^ |

You are right. Fixed, thanks!

→ Ответить

visho33

2 года назад, скрыть # |

Someone knows how to solve Dice?

→ Ответить

Morphed

2 года назад, скрыть # ^ |

+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

2 года назад, скрыть # ^ |

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

→ Ответить

Morphed

2 года назад, скрыть # ^ |

+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

2 года назад, скрыть # ^ |

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

→ Ответить

noomaK

2 года назад, скрыть # |

Can I get a hint for Powerful Strings?

→ Ответить

0xEmadeddin

2 года назад, скрыть # ^ |

-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

2 года назад, скрыть # ^ |

+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

2 года назад, скрыть # ^ |

-25

Why tf I’m getting these downvotes?

→ Ответить

noomaK

2 года назад, скрыть # ^ |

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

2 года назад, скрыть # ^ |

+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

2 года назад, скрыть # ^ |

+13

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

→ Ответить

kostia244

2 года назад, скрыть # |

← 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

2 года назад, скрыть # ^ |

+19

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

→ Ответить

Morphed

2 года назад, скрыть # ^ |

+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

2 года назад, скрыть # ^ |

BTW, what was the solution?

→ Ответить

aVanwithaMan

2 года назад, скрыть # |

How to solve Rumors ?

→ Ответить

DeadPixel99

2 года назад, скрыть # ^ |

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

2 года назад, скрыть # ^ |

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

2 года назад, скрыть # |

← 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

2 года назад, скрыть # ^ |

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.

→ Ответить

uamer

2 года назад, скрыть # |

← Rev. 2 →

how i solve Rumors problem ?

→ Ответить

tenzen

2 года назад, скрыть # ^ |

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

2 года назад, скрыть # ^ |

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

2 года назад, скрыть # |

How to solve happy numbers and Labradoodle?

→ Ответить

noomaK

2 года назад, скрыть # ^ |

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.

→ Ответить