Codeforces Round #693 (Div. 3) Editorial

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

All problems were invented MikeMirzayanov and developed by me Supermagzzz and Stepavly.

Editorial

Solution

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
  int w, h, n;
  cin >> w >> h >> n;
  int res = 1;
  while (w % 2 == 0) {
    w /= 2;
    res *= 2;
  }
  while (h % 2 == 0) {
    h /= 2;
    res *= 2;
  }
  cout << (res >= n ? "YES\n" : "NO\n");
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}

1472B - Fair Division

Editorial

Solution

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
  int n;
  cin >> n;
  int cnt1 = 0, cnt2 = 0;
  for (int i = 0; i < n; i++) {
    int c;
    cin >> c;
    if (c == 1) {
      cnt1++;
    } else {
      cnt2++;
    }
  }
  if ((cnt1 + 2 * cnt2) % 2 != 0) {
    cout << "NO\n";
  } else {
    int sum = (cnt1 + 2 * cnt2) / 2;
    if (sum % 2 == 0 || (sum % 2 == 1 && cnt1 != 0)) {
      cout << "YES\n";
    } else {
      cout << "NO\n";
    }
  }
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}

1472C - Long Jumps

Editorial

Solution

#include <bits/stdc++.h>
using namespace std;

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int &x : a) {
    cin >> x;
  }

  vector<int> dp(n);
  for (int i = n - 1; i >= 0; i--) {
    dp[i] = a[i];
    int j = i + a[i];
    if (j < n) {
      dp[i] += dp[j];
    }
  }
  cout << *max_element(dp.begin(), dp.end()) << endl;
}

int main() {
  int tests;
  cin >> tests;
  while (tests-- > 0) {
    solve();
  }
  return 0;
}

1472D - Even-Odd Game

Editorial

Solution

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
  int n;
  cin >> n;
  vector<int> v(n);
  for (int &e : v) {
    cin >> e;
  }
  sort(v.rbegin(), v.rend());
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    if (i % 2 == 0) {
      if (v[i] % 2 == 0) {
        ans += v[i];
      }
    } else {
      if (v[i] % 2 == 1) {
        ans -= v[i];
      }
    }
  }
  if (ans == 0) {
    cout << "Tie\n";
  } else if (ans > 0) {
    cout << "Alice\n";
  } else {
    cout << "Bob\n";
  }
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

1472E - Correct Placement

Editorial

Solution

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

struct man {
  int h, w, id;
};

bool operator<(const man &a, const man &b) {
  return tie(a.h, a.w, a.id) < tie(b.h, b.w, b.id);
}

struct my_min {
  pii mn1, mn2;
};

vector<pair<int, my_min>> createPrefMins(const vector<man>& a) {
  vector<pair<int, my_min>> prefMin;
  my_min curMin{pii(INT_MAX, -1), pii(INT_MAX, -1)};
  for (auto x : a) {
    if (x.w < curMin.mn1.first) {
      curMin.mn2 = curMin.mn1;
      curMin.mn1 = pii(x.w, x.id);
    } else {
      curMin.mn2 = min(curMin.mn2, pii(x.w, x.id));
    }
    prefMin.emplace_back(x.h, curMin);
  }
  return prefMin;
}

int findAny(const vector<pair<int, my_min>> &mins, int h, int w, int id) {
  int l = -1, r = (int) mins.size();
  while (r - l > 1) {
    int m = (l + r) / 2;
    if (mins[m].first < h) {
      l = m;
    } else {
      r = m;
    }
  }
  if (l == -1) {
    return -1;
  }

  auto mn1 = mins[l].second.mn1;
  auto mn2 = mins[l].second.mn2;
  if (mn1.second != id) {
    return mn1.first < w ? mn1.second + 1 : -1;
  }
  return mn2.first < w ? mn2.second + 1 : -1;
}

void solve() {
  int n;
  cin >> n;
  vector<man> hor, ver;
  vector<pii> a;
  for (int i = 0; i < n; i++) {
    int h, w;
    cin >> h >> w;
    hor.push_back({h, w, i});
    ver.push_back({w, h, i});
    a.emplace_back(h, w);
  }

  sort(hor.begin(), hor.end());
  sort(ver.begin(), ver.end());

  auto horMins = createPrefMins(hor);
  auto verMins = createPrefMins(ver);

  for (int i = 0; i < n; i++) {
    auto[h, w] = a[i];
    int id = findAny(horMins, h, w, i);
    if (id == -1) {
      id = findAny(verMins, h, w, i);
    }
    cout << id << " ";
  }
  cout << endl;
}

int main() {
  int tests;
  cin >> tests;
  while (tests-- > 0) {
    solve();
  }
  return 0;
}

1472F - New Year's Puzzle

Editorial

Solution

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
  int n, m;
  cin >> n >> m;
  map<int, int> v;
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    v[y] |= (1 << (x - 1));
  }
  const int FULL = 3;
  v[2e9] = FULL;
  int hasLast = 0, lastColor = 0;
  for (auto[x, mask] : v) {
    if (mask != FULL && hasLast) {
      int color = (x + mask) % 2;
      if (lastColor == color) {
        cout << "NO\n";
        return;
      } else {
        hasLast = false;
      }
    } else if (mask == FULL && hasLast) {
        cout << "NO\n";
        return;
    } else if (mask != FULL) {
      lastColor = (x + mask) % 2;
      hasLast = true;
    }
  }
  cout << "YES\n";
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

1472G - Moving to the Capital

Editorial

Solution

#include <bits/stdc++.h>
using namespace std;

vector<int> calcDist(vector<vector<int>> const &g) {
  vector<int> dist(g.size(), -1);
  dist[1] = 0;
  queue<int> pq;
  pq.push(1);
  while (!pq.empty()) {
    int u = pq.front();
    pq.pop();
    for (int v : g[u]) {
      if (dist[v] == -1) {
        dist[v] = dist[u] + 1;
        pq.push(v);
      }
    }
  }

  return dist;
}

void dfs(int u, vector<vector<int>> const &g, vector<int> const &dist, vector<int> &dp, vector<bool> &used) {
  used[u] = true;
  dp[u] = dist[u];
  for (int v : g[u]) {
    if (!used[v] && dist[u] < dist[v]) {
      dfs(v, g, dist, dp, used);
    }

    if (dist[u] < dist[v]) {
      dp[u] = min(dp[u], dp[v]);
    } else {
      dp[u] = min(dp[u], dist[v]);
    }
  }
}

void solve() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> g(n + 1);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
  }

  vector<int> dist = calcDist(g);
  vector<int> dp(n + 1);
  vector<bool> used(n + 1);
  dfs(1, g, dist, dp, used);
  for (int i = 1; i <= n; i++) {
    cout << dp[i] << " ";
  }
  cout << endl;
}

int main() {
  int tests;
  cin >> tests;
  while (tests-- > 0) {
    solve();
  }
  return 0;
}

count(1) % 2

count(2) % 2

Case 1

The number of ones and twos is even. Possible to distribute

Case 2

Needs more attention, because we could match extra 2 with {1, 1}

Case 3

Not possible, because of extra 1

Case 4

Not possible, because of extra 1

void Dfs (int t){
vis[t] = true;
for(auto u: g[t]){
if(!vis[u]) Dfs(u);
if(mark[u] < d[u]){
if(d[u] > d[t]) mark[t] = min(mark[t], mark[u]);
else mark[t] = min(mark[t], d[u]);
}
else mark[t] = min(mark[t], d[u]);
}
}

int arr[] = new int[n]; for(int i=0; i<n; i++){ arr[i] = ni(); } Arrays.sort(arr); int k=0; long a=0, b=0; for(int i=n-1; i>=0; i--){ k++; if(k%2 !=0 ){ if(arr[i]%2==0) a+=arr[i]; } else{ if(arr[i]%2!=0) b+=arr[i]; } } if(a==b) pn("Tie"); else if(a>b) pn("Alice"); else pn("Bob"); }

Integer arr[] = new Integer[n]; for(int i=0; i<n; i++){ arr[i] = ni(); } Arrays.sort(arr, Collections.reverseOrder()); long a=0, b=0; for(int i=0; i<n; i++){ if(i%2 ==0 ){ if(arr[i]%2==0) a+=arr[i]; } else{ if(arr[i]%2!=0) b+=arr[i]; } } if(a==b) pn("Tie"); else if(a>b) pn("Alice"); else pn("Bob"); }

include <bits/stdc++.h>

using namespace std;

int main() { int t, n; cin >> t;

for(int i = 0; i < t; ++i) { cin >> n; int a[n]; for(int j = 0; j < n; ++j) { cin >> a[j]; } int size = sizeof(a) / sizeof(a[0]); //sort array in ascending order sort(a, a + size); int score = 0; int num; int turn = 0; for(int j = n-1; j >= 0; --j) { num = a[j]; //Alice Turn if(turn % 2 == 0) { if(num % 2 == 0) score += num; } //Bob Turn else { if(num % 2 == 1) score -= num; } ++turn; } if(score > 0) cout << "Alice\n"; else if(score < 0) cout << "Bob\n"; else cout << "Tie\n"; } return 0;

} ~~~~~

define FOR(i,l,u) for(lli i=l;i<=u;i++)

int main() { lli t;cin>>t; FOR(k,1,t) { lli n;cin>>n; lli A[n+1]; FOR(j,1,n) { cin>>A[j]; } lli score[n+1]={0},maxi=0; FOR(j,1,n) { if(score[j]==0) { lli i=j; score[j]+=A[i]; i+=A[i]; while(i<=n) { score[i]=-1; score[j]+=A[i]; i+=A[i]; } if(score[j]>maxi) maxi=score[j]; } } cout<<maxi<<"\n";

}

why am I getting time limit exceeded? In the above code no element is traversed more than twice, so time complexity is-O(n) for each test case.

Comments (129)

Show archived | Write comment?

I_lOVE_ROMAN

4 years ago, # |

-65

How the editorial posted 2 years ago? If the contest is running.

→ Reply

violist

4 years ago, # ^ |

+15

2 "Hours" ago.

giantweekbold

You can write blogs and not publish them. In this case, it is so the author can get a fast editorial out — by pre-writing the editorial but not making it public yet.

Tarun_19

You wrote "years" instead of "hours":)

AntennaeVY

20 months ago, # ^ |

Now it's 2 years old 😹

r57shell

Can someone please explain why in 1472G - Moving to the Capital you can't go in first sample:

6->2->5->1
corresponding d[i] is
[2]->[1]->[2]->[1]

so there is exactly one step of kind 2.

spookywooky

To calc the distances you need to consider the direction of the edges.

Supermagzzz

+16

You use road with d[2] -> d[1] twice. It's not allowed

I use different roads. Are you talking about same distances change?

Yes, you use road with this distances twice

Oh, I got where is my mistake. I mixed up two kinds. Actually [2]->[1] is second kind of move. I thought it is first kind. shame.

Your move from 6->2 is a move of the second kind (dist 2 to dist 1) The move from 5->1 is also a move of the second kind (dist 2 to dist 0).

Therefore, you should stop at city 2 — a distance of 1 from the capital.

PigeonG

yeah,I have the same question.

sober_phoenix

how can editorial be posted if hacking phase is still ongoing

That's ok.

iamfarraz

anyone please explain d

For D you only have to justify to yourself why taking the biggest number is always the best choice to make on your turn. The editorial actually does a pretty job of this, but think of it like this — either you take the biggest item left, and it matches your parity (i.e. add it to your score), or it doesn't (your opponent doesn't gain from that item on their turn — also good for you). It's simple to see that therefore a player should ALWAYS take the biggest item (i.e. sort the array and check each move).

Aronzx

Another way to look at it:

At each point the player wants to maximise the distance between the scores of one another.

You may be tempted to look for parity while picking the numbers, but if the goal is to simply maximise the distance then you increasing your score is equal to hindering the others progress.

therefore at each point you pick The largest number which has a potential to reduce the difference between two scores.

I hope this makes sense.

sid_rasa

Thank you much

jiggly_puff

Can someone please explain the approach for B (non DP approach)?

InANutshell

← Rev. 2 →

Approach for problem B.
Let the number of 1's is one & the number of 2's is two .
Let total sum = one + 2 x two.

Casework:

Case 4.1

Case 4.2

You can also see my solution here : 103195164

egor.okhterov

8 months ago, # ^ |

Used the same case by case exhaustive enumeration, but instead I just focused on remainders after division by 2 (one_cnt % 2 == 0, two_cnt % 2 == 1).

	count(1) % 2	count(2) % 2
Case 1	0	0	The number of ones and twos is even. Possible to distribute
Case 2	0	1	Needs more attention, because we could match extra `2` with `{1, 1}`
Case 3	1	1	Not possible, because of extra `1`
Case 4	1	1	Not possible, because of extra `1`

sparkles

Lets say s represents the sum of all elements, If s is odd then its totally impossible to split it into two equal halves

Otherwise if s / 2 odd then you need to have atleast one 1 in the array to make the odd half

so the answer is no if (you have a odd total) or (a even total but odd half and no ones with you), else answer is yes

AhmedHani

Problem B is really similar to Div-2A Kitahara Haruki's Gift (https://codeforces.net/problemset/problem/433/A)

Great Contest Overall

ISuckAtLife

Can someone explain last testcase of Problem G.

For node 3 , shouldn't the ans be 1

we can go

3 (2) --> 4 (3) ---> 2 (1)

value in brackets is the corresponding d values

3--> 4 is of type 1

and

4--> 2 is of type 2

Mucosolvan

← Rev. 3 →

Distance to 4 is equal to 2 by 1>5>4, not 3.

thanks

aadit.ambadkar

3 years ago, # ^ |

Can someone explain why 6->2->5->1 isn't a valid path for the first testcase of the sample input for problem G? I'm pretty confused cause we go 6(2) -> 2(1) -> 5(2) -> 1(0).

amurto

+20

A way to avoid repeating the algorithm in E, is to always have H < W for every i. So just swap H and W for some person, if H > W.

Sooh31

Could you explain a little bit more ? thanks in advance.

Now I got it. the condition for the person i to be placed in front of the person j can be rewritten like this : min(h_i, w_i) < min(h_j, w_j) and max(h_i, w_i) < max(h_j, w_j) This means you can compare like that.

Focus_2000

this makes question very easy. thanks

Simple solution — let's iterate through how many candies of weight 2 we will give to Alice, then the remaining weight should be filled by candies of weight 1. If there are enough of them, then we have found a way of division. How is this true ? If we take the case of 1 1 2 2 2, then Alice will get 2 2, while Bob will get 2 ,1 and 1.

Thallium54

How is this not true?

galen_colin

Here are my attempts to explain solutions in video form after messing almost everything up (this seems to happen more and more often recently...)

19yjy

on G,can someone explain why (dist[u] must <dist[v]),my code doesn't add this condition and i got WA. Thanks!

if (!used[v] && dist[u] < dist[v]) { dfs(v, g, dist, dp, used); } (In the DFS function)

Because you can use only the first option from the statement as much times, as you want. We build the new graph, with edges that satisfy this condition. The second option we check by DP.

XORring-Samurai

Hi, This is my Dfs function. Where did I perform the second operation twice?
mark : stores the final answer.
d : stores the distance from root.

Adding that conditon you mentioned, gives me an AC. Can you please tell, where am I going wrong? Thanks

khaufnak

I am stuck in the same situation. Even without dist[u] < dist[v] condition, we seem to be ensuring that 2nd condition is only counted once because

if (dist[u] < dist[v]) { // Only count dp[v] if it's not bridge
   dp[u] = min(dp[u], dp[v]);
} else {
   dp[u] = min(dp[u], dist[v]);
}

shrubb

Thumbs up to the guys above. I also got stuck over this condition. For anyone interested, here's a graph exposing this bug:

In short, without the dist[u] < dist[v] condition, your DFS may update answer for some vertex x (dp[x]) by using dp[y] at a moment when y is still being processed by DFS somewhere up the tree. In this case, dp[y] isn't finalized, it's just not ready. In the graph above, x is 5 and y is 3.

Takeaway: DFS doesn't like when you close loops; better let the old DFS finish and only then spawn the new DFS tree to process x.

Zuciso

Thanks man!

Hiccup_x14

The editorial for G is very smooth. Great work Supermagzzz and Stepavly.

Dr_Strange_07

I don't know how people solve problem like today's D so fast !! sed lyf :((

Donald trump complaining even on someone solving a problem faster. Not surprising.

I am not Donald Trump..see again

KnightKnight

I wonder with B they did not include the alternate solution with DP

m0k3yDlu55y

Could anyone please help me to resolve MLE in this solution for Problem C

Your dp size is 20000 instead of 200000

you're passing the vector by value, so each time you call solve() a new copy is created. Pass it by reference or make it global.

Gojo__Satoru__

Why this dp solution gives WA on B.I thought it is equal sum partition. https://codeforces.net/contest/1472/submission/103310451

cornhub

I came across an ID in this round which was submitting solution with wrong answer for a particular corner case. FOR eg if n==123234 then print "NO" , this was done so that it could be hacked by another IDs. :p

Darshann

Can someone please help me why my code gets a WA(I get why it might get TLE but no WA): 103300499

mrkarlo

wrong answer jury found the answer, but participant didn't (test case 11)

This is a comment of your code, so you can look for test case 11(it is visible) and see why it doesn't work. EDIT: you're only looking for elements with smaller X but a correct answer could also be element whose X is larger Y is smaller and so when it is laid sideways than it could fit in the element that you are checking. So your for loop J should go from 0 to n (i.e. check all elements) P.S. even if you did this you would get TLE

aryan_anshuman

Can anyone please explain why my solution is showing WA. My logic is obvious. One can easily get that after seeing my code. Submission

Thanks in advance for helping :)

I think its because you didn't sort the arrays. You should always take largest number, and even if you divide numbers in odd and even you should sort the array and look for larges numbers. I used a similar approach 103227720. Hope this helps.

jpratik15

Can anyone explain problem G? Why do we have to change the graph? Why can't we apply dp on the graph with cycles?

hackerbhaiya

I have applied dp only my friend. You can see my submission. Reply here if you didn't get the logic.

I enjoyed the last dp problems of this contest :)

risingStark

Does anyone else feel that E was too much implementation heavy?

I thought about exactly this solution but with 30 mins remaining.
Then dropped the idea thinking that it might have some better segment tree solution instead of so much implementation. lol

BERNARD

Actually, it is not (at least for me).

It could be implemented using a segment tree in about 30 ~ 40 lines of code.

borgar02

G was cool, E took me a while but it was fun too. Overall good problems!

pyetwi

Are we allowed (yet) to ask inquiries regarding hacks for this round?

newbprogrammer

Can anyone tell me how ans of this test case of ques d is TIE.

3 2 1

I guess here bob should win. First alice chooses 2, then bob goes with 3 . Then at end alice chooses 1 and removes it. So bob wins here(since score of bob is 3 and alice score is 2).

How is it draw?

stefanopulos

IF Alica pick 3 first, then if Bob pick 1 Alica wiil win because in next turn she will pick 2(Bob_score = 1, Alica_score = 2), if Bob picked 2 insted of 1, Alica will be left with 1 (Bob_score = 0, because he piced even number, Alica_score = 0, because she picked odd number). Then answer is TIE.

Devised_positive

Can C be done by top-down approach?

dhruv7888

Yes , link to my submission https://codeforces.net/contest/1472/submission/103216440

Got it, thanks!!

jyoti360

Why is this Solution got hacked? It is almost same as the Editorial. Please let me know as I don't wanna to repeat the same mistake again. Thanks in advance !

Yes, I was wondering the same thing as well. My solution (and many other Java solutions of a similar format) were also hacked (and ultimately received TLE), but I cannot find any apparent inefficiencies.

Ahmadsm2005

I heard Java sort uses quick sort. Quick sort in a worst case takes $$$O(N^2)$$$ complexity in an anti quick sort test.

That explains it. Thanks!

hitch

I have two implementations for E which I think are easier than the one in the editorial.

A : With comments, Without comments

B : With comments, Without comments

starboy_99

Thankx Bro ! your A with comments was easy to understand!

no problem

Zahid_Hasan_Sahin

DP Contest :)

FatihSolak

There is only 2 problems I solved with dp and I think this is enough. Problems which have dp tag also have some other solutions this contest

anubh4v

For D first test case my code is giving right output in my pc whereas on codeforces it gives wrong output 103274282

codephilic

else if (o[j]>=e[i] && !fl) { sumb+=**o[i];** --j; fl=!fl; }

Maybe this is causing some problem

rahul1995

I was given similar problem as D in one of my interviews and I couldn't think of greedy approach, could only come with DP approach and was rejected. Now I solved it with so much ease in comfortable environment. Hate interview pressure.

Can someone please explain E?

alwyn

Ask everyone to stand (make $$$h_i \leq w_i$$$ for every $$$i$$$).
Sort them based on $$$h_i$$$ then $$$w_i$$$.
Now we know that the $$$i$$$-th person is at least as tall as all of the people who come before him ($$$h_i \geq h_j$$$ for every $$$j < i$$$).
Iterate through everyone and find the largest $$$j$$$ such that $$$j$$$-th person is strictly shorter than the $$$i$$$-th person ($$$h_i > h_j$$$). As they are already sorted, now we know that the $$$i$$$-th person is also taller than all of the people who stand in front of $$$j$$$-th person.
Now we have $$$j$$$ possible candidates that can be placed in front of $$$i$$$-th person. We no longer have to check whether they are shorter than $$$i$$$-th person or not, because we already know that from the previous step.
We need to find among the $$$j$$$ possible candidates, is there a person who is thinner than the $$$i$$$-th person. There could be more than one person who fits the criteria, so we will just greedily pick the thinnest person among those $$$j$$$ people and check if the thinnest person is thinner than $$$i$$$-th person.

saurabh_kl

In problem D (language used : JAVA 11) , I am getting TLE in testcase 10 with this snippet of code

while(t-->0){ int n = ni();

and getting AC with this snippet of code

Can anyone help me to know what is the cause?

naval19065

Exactly what you are not able to understand?

In first code I sort the array in non decreasing order and I traverse the array from last for chosing the number for alice and bob

and in second I sort the array in non increasing order and I traverse the array from starting for chosing the number for alice and bob

Both are about same approaches nearly while first one is getting TLE and second one is AC

Ok, I found the reason: It's because you're using Wrapper class (Integer class) in the second case. When we use wrapper classes, we are basically sorting "Objects" instead of "Values", and Arrays.sort() handles them differently. It implements "Merge Sort" while sorting Objects (Worst case time complexity: O(N*log(N))) but implements "Quick sort" while sorting Values ((Worst case time complexity: O(N^2))). So, if you use Wrapper class in the first case instead of primitive type, it would work fine as well.

Accepted Submission: https://codeforces.net/contest/1472/submission/103375034

For detailed explanation, check out the reference: https://www.geeksforgeeks.org/java-handling-tle-while-using-arrays-sort-function/

Thank you so much

stepaaa

https://codeforces.net/contest/1472/submission/103236341 this is my solution of D main idea is what person must bring max(his parity, opposite parity(it means not give this element to enemy))

DiTenix

Can problem E be solved with monotone stack? Think the array to be circular, then for each element find the next element so that (h1 < h2 and w1 < w2) or (w1 < h2 and h1 < w2)

JAISHREERAM7778

anyone can provide better sol for Problem E or any video

I wrote my solution here.

Natsu6767

Hi, I am facing some problems with D. Even-Odd Game. I have read the editorial as well as the solution provided. I think I am doing the exact same thing given in the solution: always selecting the biggest available number for either player and adding or subtracting it from a global sum depending on who the player is and the parity. However, I am getting wrong answer on test case 3. ~~~~~

Kartik_VP

Make score long long

Thanks! It worked.

Always take care of data type you are using and what max data program can generate.

KDZHR

Thanks for this round. I like problem G very much, it is the classic Codeforces' style task. Quality of this round was much better than previous five or even more.

nkumar2998

In problem D i have used erase for deleting the element and it has failed, but i see solution with same logic but using pop_back() instead of erase getting their solution accepted. I want to know that whether the time complexity of erase more than pop_back() or are they same in c++ ?

code_OR

See this and this.

raysk

I have a different solution for F, where I keep a offset between the top and bottom pointer, and use some case analysis. Time is O(mlogm).

whohet

As the problem D has a trival solution, I have faced a false plagarism accusion on it.

"Your solution 103217882 for the problem 1472D significantly coincides with solutions lit2019039/103212550, whohet/103217882."

This question has a really trival solution and hence is clearly a coincidence. Please help and remove this plagarism mark. This is literally a coincidence, as the problem really have same solution. My solution link https://codeforces.net/contest/1472/submission/103217882

Match solution link https://codeforces.net/contest/1472/submission/103212550

Please have a look as problem really have a trival solution

pranav_mehta

How does the code which was giving RE on testcase 4 with a slight modification in the comparator function (used for sorting) gives AC(aka happy new year). The change simply is using "<" instead of "<=". any input in this regard is highly appreciated

code with AC VERDICT:https://codeforces.net/contest/1472/submission/103375747

code with RE on test4 :https://codeforces.net/contest/1472/submission/103375782.

I bealive comparator function should be unique. Meaning if A > B then B < A. In your case with <= you are saying that at that if A == B then a could be before or after B which should not be possible because then sorting is not unique. I.E. if your functions returns A < B it should also return !(B < A)

I believe when you say "A<=B" that would mean that if A and B are equal then A should be before B , Although I understand what you are trying to infer, and I think that it could be right but that would depend on the sorting algorithm, furthermore if it was the case that A and B are repetitively compared with each other, shouldn't it result in a TLE instead of RE?

I bealive it works that if you compare A and B, than comparator automaticly compares B with A, and it should yield same results. In your case it gives A before B in first, and B before A in second which is contradictory. And so it gives an error.

aditya_chirania

I felt E was harder than F. I spent wayy too long on E. Shouls have attempted F first.

Guevara74

Why is there a "Tie" in the second test at problem D?

Each player takes the largest number so their opponent can't take it. So Alice takes 3, then Bob takes 2, than Alice takes 1, after that score is 0:0. This is optimal for both players. If Alice takes 2 in first turn then Bob will take 3 and win, so she has to take 3 herself. Same logic aplies after first move.

Thanks

rose_thekiller

Can someone please help me out for question D. My submission is showing runtime error on testcase 1 but it works fine on my ide

marko312

You pass odd.size() - 1 as a parameter — size() (in many implementations) returns an unsigned 64-bit value, so if it's 0 the result after subtracting will be the highest representable value. However, that is converted to a signed long long, and since the value is greater than can be represented in a long long, the value is implementation-defined.

You can cast the result from size() to a signed type first.

Thank you so much! It has worked now!

evn

Is there any way that I can uphack my solution to G. It's linked here 103279910. I have tested it on custom invocation on CF and I know there is definitely a case that makes it TLE. I waited out the hack phase since I wanted to keep my rating, but now I don't see the option to hack it anymore.

EDIT: I think you have to be 1900+ to uphack. Here is my generator that would cause my solution to TLE. https://pastebin.com/uYxwMnYz

Any1 who is eligible to uphack, go for it :)

MadhuramJ

Link1 Link2

Problem E.

Link1 solution is accepted wherease link2 is not. The only diff between the 2 solutions is that for pair(hi,wi) whose hi is least is being calculated differently:-

In link1: let the main loop take care of everything

In link2: comparing all (hj,wj) with (hi,wi) for second condition [wj < hi && hj < wi = > ans[i] = j] [Since first condition can never be satisfied]

Why does link2 solution fail?

Tareq_Abrar

What's the DP state/solution for D no. problem? I can just feel the greedy approach. But problem tag shows DP too.

Another way to think about E:

We can think about the pairs $$$(h_i, w_i)$$$ and $$$(w_i, h_i)$$$ as points on a 2D plane.

Then the problem becomes: for each point $$$P(h_i, w_i)$$$, find if there is any point that lies completely inside the rectangle that is formed by the origin $$$O(0, 0)$$$ as its bottom left corner and $$$P$$$ as its upper right corner.

silenttkillerr

19 months ago, # ^ |

How we will find that?

AnandOza

I've uploaded my post-contest stream to YouTube: https://youtu.be/nCSLlTCDnDs

_beingbest

For D how can this input be a tie? 3 2 1

raja_n

Alice will pick 3 in his first move(because he picks 2, then bob will pick 3 and wins thereafter), Then bob will pick 2(same reason for 1). Then alice will pick 1 at end. Both will have 0pts at the end.

Ok, got it, basically, it means when the game ends, both of their scores is 0.

Yes

Thanks!

PRESS_F_2_PAY_RESPECT

Can someone help me find the complexity of this code:103390550? It just barely passed the 4s time limit.

MarshallRNH2

I cant stand the fact that the dude on problem E invite n friends 1<= n <= 2 * 10^5 to celebrate new year! Guys we are in corona virus pandemic we should be more carefull! Imagine what will happen after 14 Days if there was someone with corona in the party! Be more carefule stay home and code, stay safe :D

Jonathan1234

Simpler solution for F: 103672111

Sort the blocked cells by x, y
Pair the adjacent(after sort) blocked cells in disjoint pairs.
Between blocked ceils within the same pair: distance has to be odd(or opposite color in chess grid as described in editorial)
Between the second cell from ith pair and first ceil from i+1th pair: they cannot be on the same column. Otherwise it's going to block the flow of white cells, which is going to create an odd number of white cells in both side, which is impossible to fill.

bhaskartripathi2512

i need help..! submission to D.

Please find what is wrong with this code Your text to link here.... i am not able to find any error.! it is giving runtime error.!

Non-origination

Does anyone know a possible reason for MLE in Problem G?

Samrev

using namespace std; typedef long long int lli; typedef long double lld;

0x34c

10 months ago, # |

Kind of late to the party, but I think that problem G could be solved in a lot easier way. Firstly, just as in the official editorial, find out using BFS all the shortest distances from node 1 to every other node. Then we create 2*N states for the dfs (vis[2][N] = false and ans[2][N] = INF). First state will represent, if we already took the "larger to smaller distance edge" or not. Now, we will iterate through every node (v) and if vis[1][v] is false, then we do the dfs (our dfs will be defined as dfs(took, v)).

In the dfs, for each neighbor (u) of a current node (v), we check if d[u] > d[v]. If yes, we can go there. Else we have to check if took is 1. If yes, we can go into u, but we have to update took to 0. The dfs will be returning the shortest path found yet. Also, if we encounter a visited vertex, we just answer with the solution that we precalculated (recall ans array). For better understanding you can check my solution.

Supermagzzz's blog

include <bits/stdc++.h>

include <bits/stdc++.h>

define FOR(i,l,u) for(lli i=l;i<=u;i++)