UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359) Announcement

5 days ago, # |

← Rev. 2 →

Idk how I passed C after 4 WAs, just did some +/- math. Idea was to move diagonally as much as possible and align the x coordinate or y coordinate with the target node.

Code

#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define pii pair<int,pi>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define cusrep(i,a,b,j) for(int i=a;i<b;i+=j)
#define rng(i,a,b) for(int i=a;i<b;i++)
#define rrng(i,a,b) for(int i=a;i>b;--i)
#define ar array

void run_case() {
  ll sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;
  ll alpha = min(abs(sx-tx), abs(sy-ty));
  ll nx = (sx>=tx) ? sx - alpha : sx + alpha;
  ll ny = (sy>=ty) ? sy - alpha : sy + alpha;

  if(ty%2==0){
      if(abs(tx)%2!=0){
        --tx;
      }
    } else {
      if(abs(tx)%2==0){
        --tx;
      }
  }
  if(sy!=ty){
    if(ty%2==0){
      if(abs(nx)%2!=0){
        --nx;
      }
    } else {
      if(abs(nx)%2==0){
        --nx;
      }
    }
  }
  ll ans = alpha + (1LL*abs(nx - (tx))/2LL) + 1LL*abs(ny - ty);
  cout << ans << "\n";
}
 
int main() {
  fast;
  int t = 1;
  while(t--){
    run_case();
  }
}

→ Reply

_trie_again

5 days ago, # |

+25

what the fck was C

→ Reply

5 days ago, # ^ |

Idk man, I just figured some +/- math after moving diagonally as much as possible and aligning resultant x or y with target node. After that it was tricky to move in the same direction where I did some guessing.

→ Reply

5 days ago, # ^ |

I felt like leaving the contest .

→ Reply

ExplodingFreeze

5 days ago, # |

Is there a simpler solution to G than Small to Large merging? Or did people just manage to implement that approach in like 5 mins @_@

→ Reply

Pirate_King

5 days ago, # ^ |

-8

small to large merging is simple ??

→ Reply

andrewtam

5 days ago, # ^ |

+18

It's a classic euler tour + monostack problem.

→ Reply

qiuzx

5 days ago, # ^ |

There are indeed simpler solutions, but small to large merging is also simple enough. It's only about 30 lines and 5 mins or so is enough to implement it (my solution in contest was small to large merging).

→ Reply

kelzzin2_fan

4 days ago, # ^ |

Could you roughly explain your approach using small-to-large merging?

→ Reply

ok12

5 days ago, # |

can someone please explain the idea behind the 3rd question import math a,b=map(int,input().split()) c,d=map(int,input().split()) t=math.ceil(1.5*abs(b-d))

if t<=abs(a-c) and t!=0: print(int(abs(a-c) -1.5*abs(b-d))//2 + abs(b-d)+1) else: a=abs(b-d) print(a) please explain me why my code is incorrect please

→ Reply

TrendBattles

5 days ago, # ^ |

you can try to move the initial and the end points to adjacent ones (where (x + y) mod 2 = 0) such that each one is still in its tile and then draft some examples

→ Reply

ok12

5 days ago, # ^ |

thanks

→ Reply

udta_kouwa

5 days ago, # |

← Rev. 3 →

My solution for problem-D is to store last K characters as state. AC

→ Reply

Ishaan_23

5 days ago, # ^ |

Same here, I used a bitset and converted it using to_ulong

→ Reply

AvaraKedavra

4 days ago, # ^ |

nice mate. I used bits instead of using strings. Submission

→ Reply

Dkboss3103

32 hours ago, # ^ |

this solution is really good.

→ Reply

then00bprogrammer

5 days ago, # |

Great contest. D was a really good problem, wish I would've solved E a bit quicker though. Also, How to do C?

→ Reply

Solved ABDEFG. So strange.

5 days ago, # ^ |

Idea is to move diagonally as much as possible and then align target with the resultant x or y coordinate. Tricky part was to move in the same direction in x. In y its just that difference of y coordinates as height of tiles are 1.

→ Reply

someanth

5 days ago, # |

how can we get atcoder contest testcase at which our solution got failed...

→ Reply

Parzival18s

5 days ago, # |

Anybody who found C,D tougher than E,F or just me?

→ Reply

Physics212303

5 days ago, # |

→ Reply

Physics212303

5 days ago, # ^ |

And G is the easy version of CF1725E.

→ Reply

shove_it

5 days ago, # ^ |

Can you explain the complexity of your E solution?

→ Reply

5 days ago, # |

Anyone can give hints on how to solve D?.

My approach to count all the possibilities such there is atleast 1 subarray of K length that is a palindrome and then the subtract that from 2^q and get the answer, but I couldn't calculate it properly(due to overcounting).

→ Reply

5 days ago, # ^ |

bitmask dp

→ Reply

5 days ago, # ^ |

Damn bro!! Pease explain a bit further, what will you store using bitmasking? and time complexity of your solution

→ Reply

https://atcoder.jp/contests/abc359/submissions/54847829

5 days ago, # ^ |

← Rev. 2 →

in mask I will store values of last $$$K$$$ question marks

$$$O(2^K * N * K)$$$

→ Reply

gurnam771

5 days ago, # ^ |

i think for each index we only need last k-1 elements and check if they are forming palindrome or not

→ Reply

5 days ago, # ^ |

same thing

→ Reply

5 days ago, # ^ |

thanks

→ Reply

ExplodingFreeze

5 days ago, # ^ |

Let $$$dp[i][m]$$$ (for $$$k - 1 \leq i \lt n$$$) represent the number of ways of constructing a good prefix of the first $$$i$$$ characters ending with mask $$$m$$$.

For $$$i = k - 1$$$, this is fairly direct, check all $$$2^k$$$ possible masks and see if they work (are possible and don't contain any palindromes). If they do, set $$$dp[k - 1][m] = 1$$$, otherwise set it to $$$0$$$.

Now notice that the masks for position $$$i$$$ and $$$i - 1$$$ share $$$k - 1$$$ characters. So for any $$$i \geq k$$$, we can check each of the $$$2^k$$$ masks again. If a mask $$$m$$$ is valid, we simply calculate $$$dp[i][m] = dp[i - 1][m'] + dp[i - 1][m' + 1]$$$ where $$$m'$$$ is $$$m$$$ with its highest ($$$(k - 1)$$$-th) bit disabled.

→ Reply

5 days ago, # ^ |

thanks a lot

→ Reply

comingsoon.cpp

5 days ago, # |

I think problem B's statement could have been made a lot easier to understand.

→ Reply

shviv1

5 days ago, # |

My code failed for last three testcases in C.Can someone point out where the mistake lies?

Code

ll sx,sy;
cin>>sx>>sy;

ll tx,ty;
cin>>tx>>ty;



ll ans=(abs(ty-sy));

ans+=(max(0LL,((abs(sx-tx)-(abs(ty-sy))))/2));


cout<<ans<<endl;

→ Reply

5 days ago, # ^ |

answer for

4 0
-1 0

should be 3 and not 2.

→ Reply

shviv1

5 days ago, # ^ |

But -1 is invalid input

→ Reply

5 days ago, # ^ |

2 1
200 98

Expected is 148 but your code gives 147

→ Reply

jrsak_vrmr

5 days ago, # |

← Rev. 2 →

"Can anyone explain C, please? I should have at least tried d, as I've spent so much time with C, actually, not so much time but significant time. I'm feeling bad about it now."

→ Reply

5 days ago, # |

D is good.

→ Reply

polosatic

5 days ago, # |

← Rev. 4 →

I used small to large in G. But I can't understand what's wrong in my solution. mp[v][c] contains two numbers: the number of vertices of color c in v's subtree and the total length of paths to them.

Code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#pragma GCC optimize("unroll-loops,O3")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define cok cout << (ok ? "YES\n" : "NO\n");
#define dbg(x) cout << (#x) << ": " << x << endl;
#define dbga(x,l,r) cout << (#x) << ": "; for (int ii=l;ii<r;ii++) cout << x[ii] << " "; cout << endl;
#define int long long
#define pi pair<int, int>
const int N = 1e6+9;
int n, ans, a[N], sz[N];
vector<int> vec[N];
map<int, pi> *mp[N];
int add[N];
void dfs(int v, int p = -1) {
    sz[v] = 1;
    pi mx = {-1, -1};
    for (int u: vec[v]) {
        if (u == p) continue;
        dfs(u, v);
        sz[v] += sz[u];
        mx = max(mx, pi{sz[u], u});
    }
    if (mx.se == -1) {
        mp[v] = new map<int, pi>;
        (*mp[v])[a[v]] = {1, 0};
        return;
    }
    mp[v] = mp[mx.se];
    add[v] = add[mx.se] + 1;
    ans += (*mp[v])[a[v]].se + (*mp[v])[a[v]].fi * add[v];
    (*mp[v])[a[v]].fi++;
    (*mp[v])[a[v]].se -= add[v];
    for (int u: vec[v]) {
        if (u == mx.se || u == p) continue;
        for (auto [color, para]: *mp[u]) {
            ans += ((*mp[v])[color].se + (*mp[v])[color].fi * add[v]) * para.fi + (para.se + para.fi * (add[u] + 1)) * (*mp[v])[a[v]].fi;
        }
        for (auto [color, para]: *mp[u]) {
            (*mp[v])[color].fi += para.fi;
            (*mp[v])[color].se += para.se + para.fi * add[u] - para.fi * add[v];
        }
    }
}
signed main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        a--;b--;
        vec[a].pb(b);
        vec[b].pb(a);
    }
    for (int i = 0; i < n; i++) cin >> a[i];
    dfs(0);
    cout << ans;
}

UPD: submission

UPD2: I found issue, AC

→ Reply

Chimpanzee

5 days ago, # |

+63

If C has a million haters I'm one of them. If C has a hundred haters I'm one of them. If C has one hater it's me. If C has zero haters I have died. If the world is against C I am with the world, if the world is for C I am against the world.

→ Reply

5 days ago, # ^ |

D E easier than C

→ Reply

Noobish_Monk

5 days ago, # ^ |

The whole contest was easier

→ Reply

nichke

5 days ago, # ^ |

+25

Tbh C was cute problem. I didn't like it either, but it's really simple and solution is pretty concise. I feel like CP turned into mindlessly rewriting same algos over and over, especially on AtCoder ABC. Problems like this humiliate you in a good way.

→ Reply

https://www.luogu.com.cn/problem/P7840

5 days ago, # ^ |

I was helllbent on solving C, finally did and missed on other problems D,E,...

→ Reply

Chimpanzee

5 days ago, # ^ |

I don't particularly enjoy writing math casework

→ Reply

pkhaustov

5 days ago, # ^ |

+33

I also don't like problems like this one. But since ABC is supposed to be educational, I try to make use of such problems. For example, I've learned the following lessons (in this particular order):

Skip nasty non-standard grid problems whenever it's possible. Especially if there are problems with more points to get.
Try to find out "simple observation" (as they will call it in editorial for sure) before considering shit tons of edge cases.
Test your solution like crazy. After the first WA, write stress test immediately, don't wait for luck.
Solving more and more similar problems make your more resistant and prepared to them.
Competitive programming is 100% pain.

→ Reply

Chimpanzee

5 days ago, # ^ |

Last point is real

→ Reply

harvey_wzy

4 days ago, # ^ |

If C has n haters ($$$ 3 \le n $$$) I'm one of them. If C has two haters that's you and me. If C has one hater I have AFOed. If the world is for C, I'm with you.

→ Reply

lazy-guy-1618

5 days ago, # |

E was stack and $$$\text{O(N)}$$$ ? (Asking cuz constraints had 2e5)

Code

void solve() {
    int n;
    cin >> n;
    vector<int> h(n), dif(n);
    inc(i, n) cin >> h[i];
    stack<pair<int, int> > st;
    st.push({1e9 + 1, 0});
    inc(i, n){
        auto val = st.top().first;
        if(val < h[i]){
            while(val < h[i]){
                st.pop();
                val = st.top().first;
            }
        }
        dif[i] = st.top().second;
        st.push({h[i], i+1});
    }

    vector<ll> final(n + 1);
    for(int i = 1; i<=n; ++i){
        final[i] = final[dif[i-1]] + (1LL*h[i-1]*(i - dif[i-1]));
    }

    for(int i = 1; i<=n; ++i) cout << final[i] + 1 << " ";
    cout << "\n";
    return;
}

→ Reply

0x0002

5 days ago, # |

So typical problem G. Maybe it will be better to swap some orders of the problem.

→ Reply

Misaka16172

5 days ago, # |

Could you guys just STOP making "greedy in grid" problems such as C plz? :(

→ Reply

someanth

5 days ago, # |

how can we get atcoder contest testcase at which our solution got failed...

→ Reply

acwing_gza

5 days ago, # |

+113

this is the original problem of F?

→ Reply

5 days ago, # ^ |

Why ABC usually has an original problem?

→ Reply

incra

5 days ago, # ^ |

My code which get AC in AT also get AC in LG!

But I suppose it wasn't on purpose, as there weren't many easy ideas:(

→ Reply

CF_xyy

5 days ago, # ^ |

But I think ABC is a good way to let us find the same problem so that get AC.

→ Reply

acwing_gza

4 days ago, # ^ |

so that get AC is wrong in grammar,you should modify it to be "so that you can get AC on the original problem."

→ Reply

5 days ago, # |

This problem is same as F!

→ Reply

DukhiAatma420

5 days ago, # |

← Rev. 3 →

+21

C was exactly same as https://mirror.codeforces.com/contest/1421/problem/D. Just consider the right point of tiles (moving between left and right didn't encounter any cost), and those right points forms the hexagon.

It can be solved via linear algebra, no need to go into greedy

→ Reply

Coder2020HCY

5 days ago, # |

+25

Problem F has appeared here previously : https://www.luogu.com.cn/problem/P7840

However, Luogu is a website that currently mainly used in China. So I think it is a coincidence. I only point out for notice.

Here is the translation by Copilot:

There are $$$n$$$ servers.
Each server has a busyness level denoted by $$$v_i$$$.
The servers are connected using $$$n−1$$$ network links.
Each server has a connection count $$$d_i$$$.

The total running time of the server network is given by the expression:

$$$ \sum_{i = 1}^n d_i^2 v_i $$$

The goal is to minimize this value.

→ Reply

5 days ago, # ^ |

I think so.

I wonder who finds this original problem?

→ Reply

ziyistudy

5 days ago, # |

-29

Didn't Atcoder check for if there have been the same problem？？？

This problem from Luogu same as today's G.

And this problem is from the year 2021.

→ Reply

Coder2020HCY

5 days ago, # ^ |

+26

It is a Chinese website and it only support Chinese... It is extremely difficult to check EVERY CP website and search whether there is a same problem. So It can be only coincidence. BTW it didn't cause any significant effect, because it is just an ABC contest.

→ Reply

Coder2020HCY

5 days ago, # ^ |

+29

They do nothing wrong. Try not to be too aggressive.

→ Reply