AtCoder Beginner Contest 259 Announcement

2 years ago, # ^ |

-28

Union-Find-Set and $$$\mathcal O(n^2)$$$ to get if any of the two circles are connected.

You can see the two points as two circles which $$$r = 0$$$.

→ Reply

mikcf

2 years ago, # ^ |

Same solution ;)

→ Reply

spookywooky

2 years ago, # |

+78

Honestly, that A and B where worst problems I ever had on atcoder. Abc is supposed to be constest for beginner partitipants, not beginner problem setters.

I am disapointed because quality of atcoder contests was very good before.

→ Reply

ScarletS

2 years ago, # |

+89

I would recommend whoever wrote B to consider never problemsetting again.

E and F were fun though.

→ Reply

ssvb

2 years ago, # ^ |

+15

Why do people dislike geometry problems? Problem B can be solved by a simple use of https://en.wikipedia.org/wiki/Rotation_matrix and this is something that many people are expected to be familiar with.

→ Reply

ScarletS

2 years ago, # ^ |

Since when?

→ Reply

ssvb

2 years ago, # ^ |

Since 3D accelerators became a part of every computer. Anyone who tried to play with programming 3D graphics, learned about transformation matrices as one of the first things. Not to mention that every math/physics/cs university student probably has linear algebra in their curriculum.

→ Reply

ScarletS

2 years ago, # ^ |

+32

It's intended as a beginner contest, and I would argue more high schoolers take ABCs than not. I think you're probably in the minority on the 3D graphics too.

→ Reply

omemi

2 years ago, # ^ |

Can you help me find out what's wrong with my code? Thanks a lot.

→ Reply

2 years ago, # ^ |

Judge Result shows that your solution gives WA on sample-input-3. Maybe when a=b=0, you will get l=0, and denominator=0 will lead to wrong answers.

→ Reply

spookywooky

2 years ago, # ^ |

+26

The problem ask to receite or google a formular. This is kind of the lowest class of quality a problem can be categroized. It does not make a difference how difficult or simple that formular is.

→ Reply

2 years ago, # |

+31

Found problem B harder than E. Maybe I need to pickup my high school mathsbook again.

→ Reply

Insanity_123

2 years ago, # ^ |

Can you explain your approach for E please ?

→ Reply

2 years ago, # ^ |

Lets consider the lcm of all numbers initially. We know that lcm is the maximum count of each prime among all the numbers. So we can store the maximum count of each prime in a map. The lcm will change only if the ai has a prime with its count equal to maximum count of same prime and no other ai has the same prime with the maximum count. We could do so by storing count of ai that have their count of that prime equal to maximum count. Lastly we need to check whether the lcm of the whole array is possible or not after performing any operation, we could do so by checking if for any ai there is no prime which has unique maximum count or we could just check if answer is less than n and than we could simply add 1 to our answer.

→ Reply

Insanity_123

2 years ago, # ^ |

← Rev. 2 →

I did something similar but couldn't understand last part of your explanation can you provide me feedback on below here was my approach (obv wrong).

Maintain a vector of power of each prime and sort , so we know which number(s) in the input have this maximum power of prime. If there are two number with max power of considered prime our lcm won't change ever since there would always be one of the two numbers present. This needs to be checked across all primes for a given number.
If the above doesn't hold then a number has one or more primes with max power and removal of this number should change the lcm so add 1 to the answer there.

→ Reply

2 years ago, # ^ |

← Rev. 2 →

Yeah so it maybe possible that the lcm wont change for a possible operation so we need to add 1 to our final answer for it, so we see that if the answer is n then every operation changed the lcm else if answer < n then there exists atleast 1 index for which our lcm won't change so we could just increment 1 to our answer.

→ Reply

Dan4Life

2 years ago, # |

A: Statement is so hard to understand. Bruh

B: Why is this a problem???

C: Decent

D: Repeated problem but now with gEomeTRy

TLDR: This is actually WaCoder. The first half of problemset is shit

→ Reply

udta_kouwa

2 years ago, # |

← Rev. 4 →

-32

I used bfs but 6 testcase are failing is it due to overflow im not getting idea?? Plzz help

Spoiler

vector<int>v[3001];
bool vis[3001];
ull distance(int x1, int y1, int x2, int y2){
    return pow(x2 - x1, 2) + pow(y2 - y1, 2);
}
bool bfs(ull sp,ull ep){
    if(sp==ep)return true;
    queue<ull>q;
    q.push(sp);
    vis[sp]=true;
    while(!q.empty()){
        ull x = q.front();
        q.pop();
        for(auto y:v[x]){
            if(y==ep){
                return true;
            }
            if(!vis[y]){
                q.push(y);
                vis[y]=true;
            }
        }
    }
    return false;
}
void solve(){
    int n;
    cin>>n;
    ull sx,sy,tx,ty;
    cin>>sx>>sy>>tx>>ty;
    vector<vector<ull>>p(n+1);
    for(int i=1;i<=n;i++){
        ull x,y,r;
        cin>>x>>y>>r;
        p[i]={x,y,r};
    }
    int sp = -1;
    for(int i=1;i<=n;i++){
        if((p[i][0]-sx)*(p[i][0]-sx) + (p[i][1]-sy)*(p[i][1]-sy)+0ULL==p[i][2]*p[i][2]+0ULL){
            sp=i;
        }
    }
    if(sp==-1){
        cout<<"No\n";
        return;
    }
    int ep = -1;
    for(int i=1;i<=n;i++){
        if((p[i][0]-tx)*(p[i][0]-tx) + (p[i][1]-ty)*(p[i][1]-ty)+0ULL==p[i][2]*p[i][2]+0ULL){
            ep=i;
        }
    }
    if(ep==-1){
        cout<<"No\n";
        return;
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            ull dis = distance(p[i][0],p[i][1],p[j][0],p[j][1]);
            ull d1 = (p[i][2]-p[j][2])*(p[i][2]-p[j][2]);
            ull d2 = (p[i][2]+p[j][2])*(p[i][2]+p[j][2]);
            if(d1<dis && dis<d2){
                v[i].push_back(j);
                v[j].push_back(i);
            }
            else if(d1==dis){
                v[i].push_back(j);
                v[j].push_back(i);
            }else if(d2==dis){
                v[i].push_back(j);
                v[j].push_back(i);
            }
        }
    }
    memset(vis,0,sizeof(vis));
    // cout<<sp<<" "<<ep<<endl;
    // for(int i=1;i<=n;i++){
    //     cout<<i<<" ";
    //     for(auto x:v[i]){
    //         cout<<x<<" ";
    //     }
    //     cout<<endl;
    // }
    if(bfs(sp,ep)){
        cout<<"Yes\n";
    }else{
        cout<<"No\n";
    }
    //1.Check whether those points lie on any circle..
    //check whether circles intersect or not..
    //graph problem there is egde between intersecting circle
    //find whether path exist between sx,sy,tx,ty
}

→ Reply

frexe

2 years ago, # ^ |

maybe try using x*x instead of pow(x,2).

I've had problems with that before.

→ Reply

ExpectoPatronum

2 years ago, # |

+11

problem E can solved with divide and conquer + hashing. code

→ Reply

Insanity_123

2 years ago, # ^ |

Can you describe your solution a bit so its easier to go through the code ?

→ Reply

ExpectoPatronum

2 years ago, # ^ |

The idea of this D&C is similar with Dynamic conectivity problem you can calculate LCM for all Ai except Al. So you can use something like hash to check if the LCM exist before.

→ Reply

spookywooky

2 years ago, # ^ |

What is the expected solution?

I solved it by marking each number if it has one of the most frequent e[i] values, but do not understand the editorial.

→ Reply

ExpectoPatronum

2 years ago, # ^ |

I think not. Maybe I solved it overkill.

→ Reply

Yahia_Emara

2 years ago, # ^ |

I tried using Multiset To store the current maximums before and after deletion and re-insertion of elements, but it seems that using a triple Hash did TLE, and got WA on one of the tests even, i tried double Hash and Got nowhere either, codes (1,2)

→ Reply

welleyth

2 years ago, # ^ |

I submitted it using multisets and double hashes. Here is my code click.

→ Reply

2 years ago, # |

← Rev. 2 →

In editorial of problem G:

Spoiler!!!

Shouldn't it be?:

Another Spoiler!!!

Also, I don't really understand why solution works :(

To be more precise, I don't understand why do we add edge from:

Same Spoiler!!!

→ Reply

2 years ago, # ^ |

It's problem G I think?

→ Reply

2 years ago, # ^ |

Yeah, sorry!

→ Reply

2 years ago, # ^ |

← Rev. 2 →

It's because in the problem statement, if the value of the intersection square of the two peoples' choices is less than 0, a very large penalty is added, so we cannot let them choose this intersection point. In the graph, cutting an edge corresponds to choosing an intersection square, and setting its capacity to infinity in a minimum cut ensures that it will never be cut(chosen).

Also yeah I think they messed up the ordering on C and R.

→ Reply

2 years ago, # ^ |

But why is it true that if $$$C_j$$$ and $$$R_i$$$ are both chosen, we'll always need to cut this edge with weight $$$inf$$$?

→ Reply

2 years ago, # ^ |

If they are both chosen and we do not cut this edge, there will be a complete path from $$$S$$$ to $$$T$$$. Choosing $$$R_i$$$ means that there is a complete path from $$$S$$$ to $$$R_i$$$, but not from $$$R_i$$$ to $$$T$$$. The similar is true for $$$C_j$$$.

→ Reply

2 years ago, # ^ |

← Rev. 3 →

okay, if there is a path from $$$S$$$ to $$$R_i$$$, also there's a path from $$$C_j$$$ to $$$T$$$, and also there's an edge from $$$C_j$$$ to $$$R_i$$$, why does it mean that there will be a path from $$$S$$$ to $$$T$$$? I'm very sorry for being stupid, but I really don't understand :(

→ Reply

2 years ago, # ^ |

← Rev. 3 →

I believe they fixed the editorial to " $$$R_i$$$ to $$$C_j$$$ " already.

Edit: Oh they didn't, but just look at brunovsky's comment.

→ Reply

2 years ago, # ^ |

But author's code says otherwise:

g.add_edge(h+j, i, inf)

→ Reply

2 years ago, # ^ |

What in the world... And when I change the edge to $$$R_i$$$ to $$$C_j$$$, it got WA... Now I'm confused too...

→ Reply

2 years ago, # ^ |

My friend helped me to understand the author's solution. Actually, we take a row to the answer, if it's connected with T in the cut.(then we delete absolute sum of negative elemets) And we take a column to the answer if it's with S in the cut (also we delete absolute sum of negative elements)

→ Reply

magga

2 years ago, # ^ |

← Rev. 3 →

Can u elaborate on this a little more bashkort, I am struggling to understand how this definition helps and how is it justified

→ Reply

2 years ago, # ^ |

I'll try to :)

In the beggining we added all positive elements to the answer. Then we want to create a graph, then find a minimum cut from $$$s$$$ to $$$t$$$ in this graph and subtract this value from the answer.

We will create graph as editorial says, and I'll show why this graph works.

So I say that we take some row $$$i$$$ to the answer if it is connected with $$$t$$$ in the minimum cut. Else if we don't take it, it will be connected with $$$s$$$ in the cut.

Also we take some column $$$j$$$ to the answer if it's connected with $$$s$$$ in the cut. Else if we don't take it, it will be connected with $$$t$$$ in the cut.

So why does this work: If we take a row $$$i$$$ to the answer, so it won't be connected with $$$s$$$ in the answer $$$=>$$$ then we already added every positive element from that row in the very beggining, so now if we take it to the answer, we have to add negative values too (so now we have to cut edge from $$$s$$$ to $$$i$$$, because as I said "we take some row i to the answer if it is connected with t in the minimum cut"). So because of this we create edge with weight = sum of absolute values of negative elements in the row $$$i$$$.

This edge will go from $$$s$$$ to $$$i$$$, so if it's in the answer, we subtracted this edge, or didn't subtract otherwise.

You can apply pretty much the same logic for columns.

Now let's have a look at edges between rows and columns. If we took both row $$$i$$$ and column $$$j$$$, then there is a path from $$$i$$$ to $$$t$$$, and also there is a path from $$$s$$$ to $$$j$$$. Then if a[i][j] < 0, we have to cut edge from $$$j$$$ to $$$i$$$ with weight $$$inf$$$. It's pretty obvious that's it's not optimal.

If we did't take both of $$$i$$$ and $$$j$$$, then need to subtract the edge between $$$i$$$ and $$$j$$$, because otherwise there will be a path between $$$s$$$ and $$$t$$$.

I hope you understand now :D

→ Reply

brunovsky

2 years ago, # ^ |

← Rev. 2 →

~~Should be $$$R_i\to C_j$$$ with capacity $$$a_{ij}$$$ if $$$a_{ij}\geq 0$$$ else $$$+\infty$$$~~. For more context, see image segmentation on wikipedia.

→ Reply

2 years ago, # ^ |

Thanks! But why do we add edge with capacity $$$+∞$$$ from $$$C_j$$$ to $$$R_i$$$, but not from $$$R_i$$$ to $$$C_j$$$?

→ Reply

2 years ago, # ^ |

-10

Because we connect $$$S$$$ with $$$R$$$ and $$$C$$$ with $$$T$$$. Otherwise, You can swap the order but you must guarantee that the connected ways are flowing from $$$S$$$ to $$$T$$$.

→ Reply

2 years ago, # ^ |

Author's code says that we add edge from $$$C_j$$$ to $$$R_i$$$

Then, if there is a path from $$$S$$$ to $$$R_i$$$, also there's a path from $$$C_j$$$ to $$$T$$$, and also there's an edge from $$$C_j$$$ to $$$R_i$$$, why does it mean that there will be a path from $$$S$$$ to $$$T$$$?

→ Reply

brunovsky

2 years ago, # ^ |

+11

Ok it appears the construction in the editorial is a bit different from the usual segmentation setup. The later is probably easier to understand — see the submissions of those on top of the leaderboard.

Here's my interpretation (see the article on wikipedia):

We earn $$$r_i=\sum_{j}a_{ij}$$$ if we assign row $$$i$$$ to the foreground, $$$0$$$ to the background.
We earn $$$c_j=\sum_{i}a_{ij}$$$ if we assign col $$$j$$$ to the background, $$$0$$$ to the foreground.
We pay $$$b_{ij}$$$ if we assign row $$$i$$$ to foreground and col $$$j$$$ to background, where $$$b_{ij}=a_{ij}$$$ if $$$a_{ij}\geq 0$$$ else $$$b_{ij}=\infty$$$ to prevent this altogether. This adds an edge from row $$$i$$$ to col $$$j$$$.

Now we can build the standard segmentation graph and not think about this any further, but consider some row $$$i$$$. This would add either edge $$$s\to i$$$ with capacity $$$r_i$$$ if $$$r_i>0$$$ or edge $$$i\to t$$$ with capacity $$$-r_i$$$ if $$$r_i<0$$$. But in the second case the edge is completely useless ($$$r$$$ has no other incoming edges) so you may as well ignore it. Similarly for cols.

→ Reply

2 years ago, # ^ |

Thanks!

→ Reply

CSQ31

2 years ago, # ^ |

how do you model the flow graph if the $$$a_{i,j} < 0$$$ pay $$$10^{100}$$$ condition wasn't there, the condition seems very convenient as to setup the graph such that you don't double counting some cells

→ Reply

2 years ago, # |

← Rev. 2 →

-63

Sorry but according to this post in Chinese(You don't have to understand Chinese but just see the code), GREEDY ALGORITHM can pass problem G, and there's just a hack data below.

Well if you can't see the code and the hack data, here I will copy it :

int main() {
    qread(n, m);
    rep(i, 1, n) rep(j, 1, m) qread(a[i][j]);

    rep(i, 1, n) {
        ll sum = 0;
        rep(j, 1, m) sum += a[i][j];
        if(sum > 0) ans1 += sum, v[i] = 1; 
    }
    rep(i, 1, m) {
        ll sum = 0;
        rep(j, 1, n) if(v[j] && a[j][i] < 0) {
            sum = -1;
            break;
        }
        else if(!v[j]) sum += a[j][i];
        if(sum > 0) ans1 += sum;
    }

    memset(v, 0, sizeof v);

    rep(j, 1, m) {
        ll sum = 0;
        rep(i, 1, n) sum += a[i][j];
        if(sum > 0) ans2 += sum, v[j] = 1; 
    }
    rep(i, 1, n) {
        ll sum = 0;
        rep(j, 1, m) if(v[j] && a[i][j] < 0) {
            sum = -1;
            break;
        }
        else if(!v[j]) sum += a[i][j];
        if(sum > 0) ans2 += sum;
    }

    cout << max(ans1, ans2) << '\n';
    return 0;
}

4 4
-1 -1 100 100
-1 100 100 100
100 100 -1000 -1000
100 100 -1000 -1000

→ Reply

2 years ago, # ^ |

-61

Also, great thanks to the Sample 2 in problem D cause that reminds me if one circle is inside the other.

→ Reply

Yahia_Emara

2 years ago, # |

← Rev. 2 →

Out of all problems from A to E, I think only C,D were Decent

→ Reply

2 years ago, # |

+16

For problem F, my first idea is based on greedy algorithm (inspired by Kruskal's algorithm), i.e., sort edges in decreasing order of weight, and choose from large ones to small ones as long as the "rule of degree" is not broken. But, I really wonder why this does not work? What are the counter-examples?

By the way (I am sorry that this is off topic), I find KrK in the standings!!! I am sorry to disturb you here, but you are really a legend!! During past years, I kept practicing by virtual participation in codeforces, and I usually saw you in standings, and witness your persistence and improvement. Early codeforces rounds usually do not have detailed tutorials, and it is difficult for me to understand for most of the time. During that tough period, I learned a lot by reading your solutions. The codes are clean, simple, and it helps me understand the idea behind the solution quite a lot. I am very glad to attend a true contest with you this time.

→ Reply

brunovsky

2 years ago, # ^ |

Consider 1 — 2 — 3 — 4, with weights $$$2$$$, $$$3$$$, $$$2$$$ in order and $$$d_i=1$$$ for every $$$i$$$.

→ Reply

2 years ago, # ^ |

Wow, thank you so much for your simple counter-examples!

→ Reply

KrK

2 years ago, # ^ |

+16

Thank you for your nice words, SummerSky! :) I am glad to hear that following me has helped you to learn. I wish you all the best with competitive progamming!

→ Reply

2 years ago, # ^ |

+10

Thank you so much for your encouragement, and giving me motivation!! I will try my best to keep up learning and practicing!

→ Reply

RF_Faisal

2 years ago, # |

← Rev. 3 →

Can anyone give me any test case for problem C that fails in my submission. My approach seems similar to the official editorial.

→ Reply