DBradac's blog

By DBradac, history, 8 years ago, In English

Join us this Saturday on the 5th round of this year's COCI!

Click to see where the coding begins in your timezone.

We can discuss the problems here after the contest.

  • Vote: I like it
  • +60
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it +23 Vote: I do not like it

I loved solve hsin.hr problems. Quality of problem is high. Thank you.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How often do you have a contest there? One in a year or mouth?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Usually 7 rounds in one season and a special, more difficult final round. So, roughly one contest a month.

»
8 years ago, # |
  Vote: I like it -15 Vote: I do not like it

But it is clashes with my birthday :(

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Contest starts in 3 minutes. Good luck everyone.

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

How to solve F? BTW, what was the purpose of this E?

»
8 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Seemed fairly easy, I only spent about 1.5 hours coding and I think I got all. My solutions:

p4
p5
p6

UPD: Damnit, my last problem failed just on a triviality.

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

    Or you could simply use long long instead of bitset(in the last problem).

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

      I always use long long *as* bitset.

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you tell more about your p4 and p5 solutions, please?

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

          Notice that for each edge, it would be redundant to switch both endpoints. This means we can simply go through the vertices one by one (denote this u) such that u is not marked, and if there is any other vertex v, such that there is no edge u-v, then we will switch all edges from u. We will then mark all vertices v such that there is no edge u-v (the same edges as mentioned above).

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

    Can you explain how can you reduce it to a tree since the graph may have cycles?

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The cycles are irrelevant. You can block what's on the cycles in any way you want.

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

    Could you explain problem 5's solution using BIT in more detail? Tnx. :)

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

As the contest has ended, so how long should we wait for the system testing to finish?
Edit: Ranklist can be seen now

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How did Mo's algorithm TLE on E? I thought 5 seconds was enough for 500,000*700 = 350,000,000.

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

    I used Mo's algorithm and got full points. Implementation details are often important in Mo's algorithm. My implementation is here: http://paste.dy.fi/TVD

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

    You are absolutely right. My solution (MO) had passed.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    I thought log(N) ≠ 700.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yup, MO definitely worked for me, might be an error in the code or high constant.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same here. I thought my solution with Mo's algo would pass all testcases but gave TLE on last 4 test cases. Here is my solution

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

      You need O(1) acces to cnt[v[st]] , not O(log n) with map

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        Did Coordinate compression so that the values fit inside array.Accepted code
        Thanks :)

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got TLE with MO too :(

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Perhaps, you got TLE with map/unordered_map, too? Could you show your code?

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you please see my code, I also used map with Mo's algo but got TLE in last 4 cases.

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh wow I'm so dumb.. I have solved the exact problem a few weeks ago and I just copied the code and modified 2 lines, but I didn't see that the limits for the numbers are bigger here so I didn't switch from array to unordered_map. Well I guess that's what I get for copying the solution.

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

    Actually it's 500,000*700*log(N) when you update the index with map, use array instead of map then it becomes 500,000*700

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

Seems I got 105/120 on D with a seemingly wrong solution.

My solution

I couldn't find a counterexample during the contest, can maybe someone give me one? EDIT: Seems I only failed one test case, the solution might even be correct, I'd still like your opinion, since I can't prove it. EDIT 2: Seems the only test case I failed was 3 0.

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

    I didn't understand your algorithm. Aren't the endpoints of an edge always in the same connected component?

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      He meant that all connected components in the graph are cliques. The solution is indeed correct(i got it accepted, probably he had bug in his code). The solution is easily provable to be correct.

      If we denote number of clicks(where a click toggles the edges and their complement) on a node as Anode then for some 3 nodes x, y, z if there is an edge already present Ax + Ay should be even, otherwise odd(similarly for Ax + Az and Ay + Az). It is easy to see this only satisfies when either Ax + Ay, Ax + Az, Ay + Az are all even or 1 of them is even while other two are odd. This corresponds to the clique condition.

      Code

      EDIT: sorry for errors, i didnt pay attention while typing.

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

        With his wording, it sounds like he didn't think cliques of size two were okay.

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          The case I missed was 3 0. Even i_dont_talk's missed 2 0, luckily that was in the sample tests. I submitted a minute before the end so I didn't have time to look for special cases.

          My code is practically the same as i_don't_talk's:

          Code
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes! Thank you so much! Yes, I just realized what I described were cliques haha Yes, I see it now why it's correct. Thanks again :)

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

      Sorry, I should've explained better. I marked connected components based on the edges that existed in the beginning, but the edges I checked whether they had endpoints in the same connected component were the non-existing ones, the ones you were supposed to create. So for N = 3, M = 1, e ={ 1, 2 }, the edges I looked at were {1, 3} and {2, 3}.

      I noticed that if you flipped the node x, you'd also have to flip every node it's currently connected to, so you could get that edge back after destroying it, so basically, you'd have to flip the entire connected component. The problem arises when two nodes that aren't directly connected are in the same connected component, let's say nodes w and y. After flipping w, you'd create the edge {_w, y_}, but you'd have to flip y too, therefore destroying the edge. The only thing I'm not sure about, and only based on my gut feeling is that each node will be flipped at most once.

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

        Flipping a node twice is the same as not flipping it, so yes, you were correct. It's a 2SAT problem.

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Well, I may be wrong, but not really right? Say if you flipped a node, then flipped some other nodes, then flipped this very node again, you will obtain different graph.

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

            This would result in the same graph as if you had never flipped the first node.

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

            No, you won't obtain a different graph. It's the same as flipping the same other nodes and not touching this one.

»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

In a frenzy, I accidentally submitted my STRELICE solution for POKLON, and got 0 points... after the contest, I submitted the old POKLON solution and it got full points :(

»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

For problem D.

The only case that this can happen is either there exists only one complete graph (trivial case), or two complete graphs.

Code

»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

P6 is clearly undefined if Hansel can't paint exactly K colors. (e.g S = 1) The game can't proceed, and there is no winner and loser. I made a clarification request about this after 1h of contest, but couldn't hear any response.

I understand everyone can make a mistake, but please don't dismiss the clarification next time!

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just want to point out that p5 is almost exactly the same as 375D - Tree and Queries. So if anyone wants practice for something similar, this problem is perfect.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone else solved Problem E : Poklon with segment tree? i would like to compare my segment tree approach!

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you share your approach for a start? xD I solved it using MO's algorithm but I am interested how you did it using segment tree.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it
      My approach: 
      problem: how many numbers in a segment that appears exactly 2 times!
      PREREQUISITE : loj - 1188; i wrote an editorial there.
      Solution : off-line solve, segment tree.
      

      okay lets jump into it with an example (given array):

      8
      1 1 1 2 3 5 1 2
      

      first lets solve the problem if the query always starts from 0th index and ends at any index. how to approach that? using this array: 0 1 -1 0 0 0 0 1 (and make cumulative sum array of course!)

      query [0-7] ans = 1. correct.

      query [0-1] ans = 1. correct.

      okay let me explain how i made this array here. we marked the index where x has appeared 2nd time as 1, meaning: till this index, there is an answer.

      then, as we need numbers who are present EXACTLY 2 times, we marked the the index where x has appeared 3rd time as -1, which crosses out index where x appeared 2nd time, meaning: till this point there is no answer! i hope the making of the array is clear now!

      now the next part, what happens when the starting index of query is not 0th index? this is where off-line solve comes into play!

      we will use this array still:

      0 1 -1 0 0 0 0 1

      but how do we get the answer when the query is lets say [1,2] using current array if we try to find the answer then the answer will be 0, which is wrong! so how do we find it? think about it! if we make the 1st index 0, 2nd index 1 and 6th index -1 then we can answer any query starting from 1st index! :D and the array is :

      0 0 1 0 0 0 -1 1

      can you say why we specifically updated the 1st,2nd,6th index? because those are the places where 1 is present. and we changed the positions where 1 is present, why? because 1 is 0th index, which is the previous 1st index.

      so for example if the query is [2-7] the we would have to do the same for 0th index value, 1st index value. and the array will be like:

      0 0 0 0 0 0 1 1

      and the answer is 2!

      we simple used segment tree to update and find the query.

      CODE

      PS: sorry for my bad English and the way i wrote, i usually do not post in codeforces :S

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Tnx. I learned a lot from you! Have a nice day. ;)

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

    I used a segment tree :-

    Code

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

But it is clash with global game jam :(

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How do I solve p3? A trivial solution gains 50 points.

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

    You only have to find the area of the first quadrant and then multiply it by 4.
    - For each rectangle do x=x/2 and y=y/2.
    - For each X store the max Y coordinate for it.
    - Start from largest X and visit till x=1.
    If for current X the Y coordinate(if exist) is greater than the max_y_coordinate(till now), update the max_y_coordinate.
    Answer=Answer+max_y_coordinate.