PikMike's blog

By PikMike, history, 7 months ago, translation, In English,

1167A - Telephone Number

Idea: Roms

Tutorial
Solution (Roms)

1167B - Lost Numbers

Idea: Vovuh

Tutorial
Solution (BledDest)

1167C - News Distribution

Idea: MikeMirzayanov

Tutorial
Solution (BledDest)
Solution (PikMike)

1167D - Bicolored RBS

Idea: adedalic

Tutorial
Solution (adedalic)

1167E - Range Deleting

Idea: Roms

Tutorial
Solution (Roms)

1167F - Scalar Queries

Idea: adedalic

Tutorial
Solution (adedalic)

1167G - Low Budget Inception

Idea: adedalic

Tutorial
Solution (adedalic)
 
 
 
 
  • Vote: I like it
  • +55
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it +32 Vote: I do not like it

Editorial of F is soooo goooooddd. thx man

»
7 months ago, # |
Rev. 5   Vote: I like it +19 Vote: I do not like it

F is a little overcomplicated I think. Easier way to think about it is to see that every contribution of the lower-valued items on the left is that their contribution is just the number of spaces on the left of each of them plus one (if example $$$a_j < a_i$$$ and $$$j < i$$$, contribution is $$$j + 1$$$, since this is the number of intervals that the lower-valued item gets included in). Multiply this by the number of intervals on the right (n - index), since it contributes that many more times. Then easy done. Do this with the segment tree by updating the position index in fenwick tree with itself to get contribution over all of them fast (contribution from left side is query(index) * (n - index)). Then do same thing on the right side. (All values are zero indexed in this explanation)

UPD: Ok, someone has asked for a clearer explanation, so I have taken a little more time to write it out. It is very large, so I spoilered it.

better explanation
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    wouldn't this solution overcount?

    ohhhh nevermind this is genius thank you!

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh shoot, thanks!!!

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please explain problem C .The problem as well as input ,output is not clear to me. How become the output 4 4 1 4 4 2 2 for sample test case ?

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 $$$i$$$ you wish to find the number of people that are share a group with $$$i$$$.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can problem C be solved using DSU data structure ?

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I'm really sad that this is the first time I did an interactive problem and the tutorial in the contest show fflush(stdout) to flush output in C++. I kept getting idleness error in the contest and couldn't figure out why (WA is much easier to deal with). After this editorial released, I changed fflush(stdout) to cout.flush() and I could debug my old code in a blink. You guys should update the tutorial for the interactive problem. It was frustrating.

»
7 months ago, # |
  Vote: I like it +4 Vote: I do not like it

The link to this blog has not yet been mentioned in the contest page. Should you not add it to the contest page as soon as the editorial is published? Just asking.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Lost Numbers I used almost the same trick.But struck with one problem.I was using GCD to get to know unique number but it turns out that it is not.let say the array is [a,b,c,d,e,f] and x=a*b and y=b*c .So GCD(x,y) should give me "b" but i was getting multiple of b.So is there a way to resolve this issue.Thanks is advance.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The explanation to the solution of problem C is not very clear. Can someone explain the approach in simpler words ?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I managed to pass G with 2 pointers (breaking early helped a lot). I do prefer the editorial solution though. Thanks!

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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(\frac 1 {3500})$$$. Find the maximum $$$x$$$ such that $$$2 arctan (\frac 1 x) > arctan (\frac 1 {3500})$$$ so that two buildings collinding produce greater angle. That $$$x$$$ is 7000, thus further collisions will never affect the answer.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Can someone explain the editorial of problem E (Range Deleting)?
Having a difficult time to understand it or is there any other approach which is simpler and easy to explain.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, I solved Problem C using DFS in Java. I saw one "Accepted" submission in GNU C++ with the same logic. I am getting time limit exceeded on test case 6. I have tried to speed up the code as much as possible. Is it possible that the same solution in Java gives a time limit but not in GNU C++?

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 :

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

May you attach this tutorial link to the contest material section?

It might really be a mess (a search will work :3) for future participants to look for it (for practice).

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem F

Many people got WA on test 35 (me too) as we didn't mod while adding inside BIT

»
7 months ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

pikmike adedalic
Can you please explain the editorial of problem E (Range Deleting)? Not able to get it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain problem D properly?? here is my solution.. and it is getting wrong on test case 17Your text to link here...

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please help! I have a question about question C solution. Why my code get TLE on 6th test case and is slow in general because I do not understand:(. The code -> https://codeforces.com/contest/1167/submission/54572709 The solution inspired by BledDest solution, just written in Java, not line by line so there might be difference but it should do roughly the same. It creates graph where person nodes and groups nodes are mixed with each other and to recognize what is what the groups nodes are enumerated from (n+1) to (n + m + 1) and person nodes from 1 to n. verts array holds colors of nodes after DFS. So if there is only one connected component in graph, then DFS should run only once. DFS returns the number of person nodes that the code encounter during search.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain problem E

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

54435380 In C, Why am I getting memory limit over and over again? Can anyone please help?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

here is my submission of problem C News Distribution http://codeforces.com/problemset/submission/1167/55075296 please, can someone tell what's wrong in it its showing tle and I don't know why?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain problem c sample test case 4 4 1 4 4 2 2 in some details? how to get this output? please.

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone please check why 57224389 for 1167E - Range Deleting gets WA on test #51?

I used a greedy approach similar to tutorial and some two pointers. The overall time complexity is $$$O(n)$$$.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am trying to understand the issue of my submissions for problem C, that hit Memory Limit. It would be nice if someone can help with my understanding.

Submission #1 , Submission #2

The only difference between them, is the allocation of:

const int N = 1e6 + 5;
int cluster_map[N], cluster_size[N];
array< vector<int>, N >g;

In #1, N = 1e6 + 5. In #2, N = 2e5 + 5. So I thought #2 would require less memory than #1, but it turned out #1 Accepted, while #2 is over limit. Can someone help me understand the issue?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Help me in my code of problem c, i am getting TLE