Educational Codeforces Round 65 Editorial

1167A - Telephone Number

Idea: Roms

1167B - Lost Numbers

Idea: vovuh

1167C - News Distribution

Idea: MikeMirzayanov

1167D - Bicolored RBS

Idea: adedalic

1167E - Range Deleting

Idea: Roms

1167F - Scalar Queries

Idea: adedalic

1167G - Low Budget Inception

Idea: adedalic

Comments (49)

• 3 years ago, # ^ |

  wouldn't this solution overcount?

  ohhhh nevermind this is genius thank you!

• 2 years ago, # ^ |

  just a minor correction in last line: (i + 1) * (n — i) + leftTree.queryRange(0, i) * (n — i) + rightTree.queryRange(i + 1, n) * (i + 1) . Thnx for the explanation.

  • 2 years ago, # ^ |

    Oh shoot, thanks!!!

    (also there were some other typos in that last line i corrected)

• 3 years ago, # ^ |

  ← Rev. 2 →  

  0

  Use some pen & paper, you'll get eventually.

• 3 years ago, # ^ |

  Read the problem attentively, you'll understand input & output.

• 3 years ago, # ^ |

  Firstly you read the number of people and the number of groups, then for each group you read the which people belong to this group. In then end for each people ii you wish to find the number of people that are share a group with ii.

• 15 months ago, # ^ |

  plz someone xplain hep ..i also stuck that how is this output for sample test case ?plz help

• 3 years ago, # ^ |

  ← Rev. 3 →  

  0

  Yes. Initially, you want to add everyone in a group of friends do the same component. Then, when someone is into another group, you connect the components.

  This is exactly what the editorial says in the last line.

  • 2 years ago, # ^ |

    I think one person cannot be in more than one component as if he's in more than one component those components cannot be disjoint as he'll be friends with people from both components. I'm still not very clear about problem C. Can somebody explain the solution once.

    • 2 years ago, # ^ |

      Let's say there are two main groups on the input: group A consisting of p, q and r and group B with two other guys: u and v.

      If the next line of the input says that there exists another group, C, consisting of r and u, that means there's an edge connecting them and, therefore, their groups. Now, there is a connection between p and q with r, from r to u (just became friends), and from u to v.

      That means we need a fast way to unite those disjoint sets of friends.

      In the end, we are required to say how many people will know about the news if person i starts spreading it. From the statement, we know that one guy tells the news to everyone in his groups of friends, so we only need to print the size of the component containing i-th person.

      You can check my submission (54194939). It's pretty easy to read and there are lots of comments.

      • 2 years ago, # ^ |

        Thanks for the explanation! I get it now

• 3 years ago, # ^ |

  ← Rev. 2 →  

  +8

  No. It's your fault for using IO optimizations without understanding what they do minimally. https://codeforces.com/contest/1167/submission/54261003 fflush + commenting the optimizations.

  My tip is always using endl instead of '\n' since code stays the same and endl flushes the output. Example: https://codeforces.com/contest/1167/submission/54205213

  With this being said this is worth mentioning in that blog.

  • 3 years ago, # ^ |

    Thanks. Now I know. Good lesson tho.

  • 2 years ago, # ^ |

    Use endl only in interactive problems! It's slow so you risk TLE.

    • 2 years ago, # ^ |

      I meant always using endl in interactive problems, my bad I was careless in the comment.

• 3 years ago, # ^ |

  If you use cout and endl then you don't need an extra cout.flush() in C++.

• 3 years ago, # ^ |

  gcd(x,y) gives you b only if gcd(a,c)=1. Otherwise, it will give you gcd(a,c)*b, which is a multiple of b.

• 3 years ago, # ^ |

  Use a DSU to connect all of the groups. This can be done in O(group size) for each group by connecting the first person in each group to everyone else. Then find the size of the group each person is in to get the answer.

• 3 years ago, # ^ |

  Why is it enough to maintain 7000 positions to the left and right?

  • 3 years ago, # ^ |

    Oh, I totally forgot to mention this in editorial. Basically, positions further than that won't ever be needed. Check the angle you get for the closest collision between a building and a ray. It's less or equal to arctan(13500)arctan(13500). Find the maximum xx such that 2arctan(1x)>arctan(13500)2arctan(1x)>arctan(13500) so that two buildings collinding produce greater angle. That xx is 7000, thus further collisions will never affect the answer.

    • 3 years ago, # ^ |

      Bitsets can be updated in (d/32). Can you give any reference for this? I didn't get this. Thanks for the editorial.

• 3 years ago, # ^ |

  ← Rev. 2 →  

  0

  Whenever your program might go in deep recursion or dfs you might get RunTime Error. This is due to StackOverFlow Error. As stack size of Java is very low, hence, either you should avoid deep recursion and use iteration or increase stack size dynamically.

  Source :

• 2 years ago, # ^ |

  You are declaring a vector of size z inside you for loop — and you are doing it m times. Two global arrays of size 5*1e5 and m vectors with variable sizes (but sum equal to 1e5) are using too much memory.

  You can declare the vector "vec" outside of the for loop and just reuse it — or don't use it at all.

  • 2 years ago, # ^ |

    OK thanks :D