UNICOLOR - Editorial

editorial
, , ,
12

Assuming you implement things properly, you get y almost for free when computing x - please do read through the editorial, I’ve tried to explain in some detail.

1 Like
13

Yeah, thanks very much. I’ve solved that issue, but my new fix still seems to be incorrect. I’ll try to figure it out though. :slight_smile:

14

i tried using dsu on clubs , but im getting WA . is it possible for someone to suggest any test cases so that i can debug my code .
the link to my code is CodeChef: Practical coding for everyone . can you check what i am missing ?

16

Why I’m getting TLE in subtask 2? I’m constructing a graph of size at most 10^5 (C*x) and do BFS Traversal to find non-intersecting clubs.
code is here Solution: 44236788 | CodeChef it’s time complexity is O(c*x log(c*x)))

17

There were several issues with your code:

  1. There was a useless vi club(n + 1, 0) which is bad for when n \leq 10^9
  2. Your mul(x, y) function is too slow. while (prod >= MOD) doesn’t really work well because you might have to do \mathcal{O}(MOD) subtractions to get the result down - just take the mod directly instead.
  3. Your power(x, y) function is technically wrong as well, but it gets saved by C++ being smart.
  4. Fixing the above will make your code run fast enough, but it gets WA because you’re missing a case.
Try this input 
1
1 4 2
1
1 1

A couple of my latest submissions fix your code, take a look at them if you like.

18

:neutral_face::relieved:that was my mistakes but,
ThankYou so much after fixing this I got fully accepted, thank you for helping.

21

You forgot to account for the students not in a club, before the first interval.

22

Yep found it…Thanks for the help. @iceknight1093

24

https://www.codechef.com/viewsolution/44272106

@iceknight1093 cam u plz explain why i m getting RE on subtask 2
i have used dsu with both path compression and rank by union and after doing the operations if the par node is -ve it signifies its the parent of a connected component so the count is increased if par[node]<0

25

My solution is O(cxlog(cx)+cx). Why is it giving TLE on subtask 2? I used co-ordinate compression to lower the co-ordinates to order of c*x and then used sets to traverse the elemets within ranges like [l…r].
My Code

26

Near the end of your solution, F(i, 1, n + 1) should be F(i, 1, c + 1).

1 Like
27

Hey all, I tried to implement the idea as per the editorial but I’m getting TLE for almost all cases. Can anyone please help where I’m going wrong?

Here is my code : CodeChef: Practical coding for everyone

28

oh thanks a lot

29

bro ur GOD and i m so dumb and I couldnt even debug myself , thanks for being so helpful

30

Before this problem, I wasn’t about the line sweep technique, every time I think a lot about such intervals.
Now I got the exact thing line sweep.
Here is a nice blog on this How to sweep like a Sir - Codeforces.
Happy coding :slightly_smiling_face:

1 Like
31

Getting WA in subtask 2
https://www.codechef.com/viewsolution/44316180
edit: forgot to add students at the end of the interval to the independent students variable. AC now

32

It was indeed a good question. Learned a lot. Still solving.

1 Like
35

Thanks for help @iceknight1093

36

I solved this question using dsu, I was hoping to get TLE on this solution CodeChef: Practical coding for everyone
because I got TLE on this:
CodeChef: Practical coding for everyone

The only optimization I did in the first solution is that I am not applying binary search if parent[i]=parent[j] for all i [0,c-1] and all j [i+1,c-1], which should fail for extreme case like c=1000, all x=100 and all intervals have zero intersection.

Number of iterations in worst case scenario - T*(number of elements) * (clubs) * (sum of log(elements in each club))

which comes out to be- 10* 2e5 * 1e3 *7e3 ~ 1e12.

37

I am using Klee’s algorithm. My solution is passing 70 point sub-task but giving runtime error in sub-task 1. Can any one help with this?