mraron's blog

By mraron, history, 5 weeks ago, In English

We hope you liked the problems. See you on day 2 :D

Problem A
Problem B
Problem C
 
 
 
 
  • Vote: I like it
  • +100
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Problems were really good.

»
5 weeks ago, # |
Rev. 2   Vote: I like it -64 Vote: I do not like it

i use the same approach as mention in tutorial A but scores only 12 points, will someone help me to find out the bug?

/*
  In the name of ALLAH
  Author : Raashid Anwar
*/

#include <bits/stdc++.h>
using namespace std;
 
#define int int64_t
const int M1 =  998244353;
const int M2 =  1000000007;
mt19937 rng((uint64_t)chrono::steady_clock::now().time_since_epoch().count());

int lo[100001];
int hi[100001];


int get(int x, int y) {
  x *= (x + 1);
  x /= 2;
  x %= M2;
  y *= (y + 1);
  y /= 2;
  y %= M2;
  x = (x * y) % M2;
  return x;
}


void solve() {
  int n;
  cin >> n;
  vector <pair<int, int>> a;
  for(int i = 0; i < n; i++) {
    int h;
    cin >> h;
    a.push_back({h, i});
  }
  for(int i = 0; i < n; i++) {
    int w;
    cin >> w;
    lo[i] = (i? hi[i - 1]: 0);
    hi[i] = lo[i] + w;
  }
  sort(a.rbegin(), a.rend());
  int ans = 0;
  set <pair<int, int>> s;
  s.insert({-1, -1});
  s.insert({M2 * M2, M2 * M2});
  for(auto [height, i] : a) {
    int from = lo[i];
    int to = hi[i];
    auto ri = s.lower_bound({from, 0});
    auto li = ri;
    li--;
    if((*ri).first == hi[i]) {
      to = (*ri).second;
      s.erase(ri);
    }
    if((*li).second == lo[i]) {
      from = (*li).first;
      s.erase(li);
    }
    s.insert({from, to});
    ans = (ans + get(to - from, height)) % M2;
    ans = (ans + (M2 - get(to - hi[i], height)) % M2) % M2;
    ans = (ans + (M2 - get(lo[i] - from, height)) % M2) % M2;
  }
  cout << ans << "\n";
}

 
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  solve();
}
  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    try multiplying by inverse of 2 instead of dividing by 2, that could be the issue.

    UPD : inverse of 2 is $$$2^{MOD - 2}$$$

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I dont think so since x*(x+1) is always divisble by 2

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it -25 Vote: I do not like it

        It's not about whether it's divisible or not, when you're using mod you shouldn't perform division. For example, try computing n choose k with mod and dividing and then try it using inverse modular.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          " x *= (x + 1); x /= 2; x %= M2; " He uses mod after dividing which works here just fine.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      For 2 inverse is always (MOD+1)/2 if it exists.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    I believe you can overflow int64 in get because x can be as large as $$$10^9 \cdot n$$$?

»
5 weeks ago, # |
Rev. 3   Vote: I like it +29 Vote: I do not like it

C can also be solved with all-directions DP + matrix fast pow: For the last layer ($$$i = D$$$), we compute for every edge $$$u \to v$$$ whether the state we get after moving from $$$u$$$ to $$$v$$$ is winning. This allows us to compute for every vertex whether starting at this vertex is a winning state in $$$O(n)$$$ time in total. Let's call those vertices winning vertices.

Let an $$$i$$$-configuration be a way of placing the tunnels between layers $$$i, i+1, ..., D$$$. (In particular, the total number of $$$i$$$-configurations is $$$n^{2(D-i)}$$$.) When considering tunnels from $$$i$$$ to $$$i+1$$$, we only care about whether this tunnel leads to a winning vertex or not. We compute for every edge $$$u \to v$$$ the number of $$$i$$$-configurations for which the state we get after moving from $$$u$$$ to $$$v$$$ is winning/losing and for which the tunnel is reachable from $$$v$$$. This in turn allows us to compute for every vertex in layer $$$i$$$ the number of $$$i$$$-configurations for which this vertex is winning in $$$O(N)$$$ time in total. Doing this for all $$$i$$$ gives an $$$O(D N)$$$ time algorithm.

To get $$$O(N + \log D)$$$ time, note that total number of winning/losing vertices in layer $$$i$$$ among all $$$i$$$-configurations depends linearly on the total number of winning and the total number of losing vertices in layer $$$i+1$$$ among all $$$(i+1)$$$-configurations. Hence we only have to run the dp three times: Twice to get the matrix of this linear map and once for the first layer (as the starting vertex is fixed). (It is also possible to avoid the third call.)

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C, subtask 5, I don't really get the ''we can reroot the tree easily'' part and I've complicated myself with if's and all that.. Could someone please help me?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Figured it out, because when you go father->son the father become's son's son (ironically), you can have another variable ver in dfs which is what father's state would be as a son (pretty complicated but it's late and I can't think straight), and ver is state[father] unless state[father]=1 and he has only one son with state=0 (the number of sons with state 0 is |{state[son]=0}|+(ver=0) because ver is also a son!) and state[son]=0, in which case ver=0 because the father's state becomes 0, having only 1's as sons, AND state[son]=1. A few observations are that you need to copy the states vector since you will need it later in another dfs and ver is initially 1 because why not :)

    I wrote this in case anyone else had this problem for them not to spend a lot of time with 1's and 0's going crazy in their heads XD

    Sorry for not using Codeforces syntax but I don't know any of it

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Guys could you tell me why do i get tl on subtask 6? Code

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me find bug in my code, it is for subtask 4 of Problem A. 91100908

»
5 weeks ago, # |
  Vote: I like it +51 Vote: I do not like it

Can someone explain the Problem B sweep line more in detail, I don't really understand what the author means by Rmost(u), how is it calculated, and how it helps us in building the tree.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 6   Vote: I like it +16 Vote: I do not like it

    Let me a try. When sweep line move along the plane there are current lines, past lines and future lines. Past and current lines are already connected to tree.

    When sweep line intersect new future line it should be connected to one of the current or past line. We can't connect it to the right end of the current line (it can intersect future line) and we can't connect it to the left end of the current line because it can intersect past lines. But if we store rightmost end of the past line then it can't intersect with any other line. Let's store past rightmost end of the past lines between current lines. When we connect line to the past or current line the left(!) point of added line become new rightmost point for sectors above and below added line. And connected line become current line.

    And now with picture :)

    The rose is red, the violet’s blue ... sory another picture. :) Rightmost points are red. Past lines are blue. Current lines are green. Future lines are purple.

    For purple line 1: Current lines are 1 and 2. The Rightmost point is end of the blue line 1. Connect purple line 1 to blue line 1 and add purple one to current lines. Left point of purple line 1 is a new Rightmost point for sector between green 1 and purple 1. Also Left point of purple line 1 is a new Rightmost point for sector between green 2 and purple 1

    For purple line 2: There is no past lines between green 2 and green 3 so the Rightmost point is left point of green 2 (it was added later than green 3). Connect and update left point of purple 2 is a Rightmost for green 2 — purple 2 and purple 2 green 3.

    For purple line 3: The same as for purple 1. Connect purple 3 to blue 2 and left point of Purple 3 is a new rightmost point for green 3- purple 3 and purple 3 — green 4.

    I tried ... sorry :)

»
5 weeks ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

In Problem A, I am not able to understand why my solution is not working. It has only passed Subtask 2. I dont know why it does not work on all subtasks. A little help would be really appreciated.

Logic
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Oh! yellow_13 helped me figure out. Actually, I had over seen a modular mistake and also, wherein I was multiplying two elements of prefix sum as (pref1*pref2)%mod which may give overflow. There were some other problem with the way I was writing code too.

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

I read the editorial of problem B. It's a good approach. But I didn't understand how can we find for every point q such points v, u that q is located between v and u. Could anybody please help me with that?

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

After 3 days of trying to get the last subtask of problem A. I finally solved it with segment tree lol.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved A in Linear time complexity using Stack(By precalculating the next smallest element in left and right). But not able to understand how DSU or sorting can be used to solve this problem.

Can somebody explain how DSU more clearly? How we are able to get sum of widths from x to yth node using dsu?

»
6 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

REDACTED