Блог пользователя BledDest

Автор BledDest, история, 3 месяца назад, По-русски,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Проголосовать: нравится  
  • +42
  • Проголосовать: не нравится  

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится +35 Проголосовать: не нравится

Problem E is not original! link

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    So what? Same thing could be said about countless other problems. One could say the same thing whenever he encounters an MST or shortest path problem.

    • »
      »
      »
      3 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

      I agree with you! Maybe what I was trying to say is that the other problem's editorial could be a little help to whoever didn't get this one. I'm just trying to point out the similarities, that's all!

»
3 месяца назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится

I had a different idea for E.

First, let's take the vertices whose degree is bigger than N/2. Any two such vertices must be in the same connected component, because their neighbor sets must overlap.

What about the other vertices? Well, their degrees are smaller than N/2. That means that N-deg(v)>deg(v) for each of them. but the sum of N-deg(v) is at most 2M, hence their sum of degrees is at most 2M as well. So we can apply a regular algorithm (dfs, or dsu) to those vertices.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You have to extend the set of vertices where degree is bigger than N/2 to its maximal, since vertices of degree no more then N/2 may also in the set.

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes, I guess I wasn't clear.

      For the vertices whose degree is less than N/2, you process ALL their edges — the ones leading to each other, as well as to the big set.

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Thank you very much for this explanation.

    Now I got E

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Sorry, I don't get this part:

    but the sum of N-deg(v) is at most 2M, hence their sum of degrees is at most 2M as well

    Why "N-deg(v) is at most 2M", and what does "N-deg(v)" imply? and how we can derive "their sum of degrees is at most 2M" from that?

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      N — deg(v) counts the vertices w, such that (v,w) is NOT an edge in the graph.

      There are M pairs (x,y) that are NOT edges, and 2M if we count both (x,y) and (y,x).

      Thus if we add up (N — deg(v)) for every vertex v, we will get 2M. And if we add up (N — deg(v)) for only some vertices, we will get a number at most as big as 2M.

      Now, if deg(v) < N — deg(v), then the sum of deg(v) in the set is also less than the sum of N — deg(v) in the set, which we have already established is at most 2M.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Nice idea

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

someone know why i get RE on Test 9 by using it=vis.lower_bound(*it) ,setvis for unvisited node and auto it=vis(iterator) 34911809

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

someone know why i get Re on test9 by using it=vis.lower_bound(*it) ,

set<int>vis,it=vis(itertator) 34911809 ,I get AC after changing *it to x (int x=*it)

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    I belive its because you should not keep using the iterator it after you erased it from the set

»
3 месяца назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Editorial for E looks unfinished.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Could someone explain it in a better way/more understandable way? Or Can someone provide the Implementation?

    Thanks.

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      Here's the implementation: http://codeforces.com/contest/920/submission/34871219

      Just keep all the unvisited nodes in a set and keep erasing vertices as you visit them in the bfs. You are now selectively only going to traverse through the unvisited nodes, which brings down the complexity to O(NlogN) [use of sets gives the logN factor.

    • »
      »
      »
      3 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      add 1~n node in "unvisited node"set , take out one of the node untile set is empty, for the node you take out ,denote it U, find the edge"you can go",which is [upper_bound s — find the smallest integer y from the set such that y > s.] in the tutorial and those nodes you find from node U will be one of the component.

      keep the graph bu using STL:set it will be easy to implement.

      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I tried to implement and I'm getting Runtime error in CF whereas it is working fine on my computer. I got the error, it is because the set is dynamically getting changed during the recursion.

        void dfs(int i,int p){
            merge(i,p);
            set<int>::iterator it;
            for(it=S.begin();it!=S.end();it++){
                if(M[ii(i,*it)]!=1){
                    int x=*it;
                    S.erase(x);
                    dfs(x,i);
                }
            }
        }
        
        • »
          »
          »
          »
          »
          3 месяца назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          You made a mistake on C++ container iteration. When you want to erase something in an iteration, be sure to update the iterator, or it becomes an undefined behavior. For example, you should change your code to

          void dfs(int i,int p){
              merge(i,p);
              set<int>::iterator it;
              for(it=S.begin();it!=S.end();){
                  if(M[ii(i,*it)]!=1){
                      int x=*it;
                      it=S.erase(x); // it=S.erase(it) would be better
                      dfs(x,i);
                  }else ++it;
              }
          }
          

          All erase in iteration should be done so, see the cppreference of std::set::erase, or any other container's erase function

          • »
            »
            »
            »
            »
            »
            3 месяца назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Yeah, thanks, man..! I got. I fixed it using the following.

            void dfs(int i,int p){
                merge(i,p);
                set<int>::iterator it;
                for(it=S.begin();it!=S.end();){
                    if(M[ii(i,*it)]!=1){
                        int x=*it;
                        S.erase(x);
                        dfs(x,i);
                        it=S.lower_bound(x);
                    }
                    else
                    	it++;
                }
            }
            
          • »
            »
            »
            »
            »
            »
            3 месяца назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            The advantage of my approach to yours is that it works for C++98 also, whereas yours works only for C++11 and above.

            Anyway, Thank you.

      • »
        »
        »
        »
        3 месяца назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        I got it fully now.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Unfortunately, I'm not sure what to write there additionaly.

    The algorithm is just typical DFS, but instead of iterating on adjacency list of current vertex and trying to find an unvisited vertex, we have it backwards: we iterate on the set of unvisited vertices and try to find the one that can be reached from current vertex.

    Perhaps my implementation can help to understand it better.

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I was confused about how we choose next vertex, so you could write about step "try to find the one that can be reached from current vertex" in details.

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      If the question is on a directed graph. I think we have to Iterate on all the edges of the set. Right? However, if we iterate on all the vertices in the unvisited set in this question also, I think the complexity remains the same because atmost after deg(v) (where v is a vertex in unvisited set and deg(v) is the degree of v in the given graph) v will be removed from the unvisited set. So overall complexity will be m*log(n).

»
3 месяца назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Can someone explain G?

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Что за рюкзаковая динамика? В интернете не находится ничего адекватного по этой фразе.

Неужели трудно сделать разбор задачи чуть подробнее, видя что решили её единицы, при том что она на уровне сложности D.

»
3 месяца назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

For Problem E,can the problem be solved in the same complexity if the graph is directed?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    if you cant add edge 1->2 it means you can add 2->1 ,so if the still add the edge 1->2,because the probelm is asking component so it doesnt matter. I think so...

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In first string of problem G you have a little mistake. Not gcd(z, y) = 1 but gcd(z, p) = 1

»
3 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

For F, you can do it with a BIT and a set. Store sums in the BIT, then for range updates, you can store the indices of all numbers that aren't 2 in the range in the set with lower_bound and traversing forward. If you set something to 2, erase it from your set.

The solution is still O(qlog n) but should be easier/faster to code.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks for the idea about set. Got through without a time limit after adding to set indexes of elements, not equal to 2 and 1.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone share their model solution to F ? I am not able to understand most of the codes.

»
3 месяца назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Hi guys, I'm having trouble with problem F.Here is my solution .I did everything that was written in editorial but my solution doesn't fit time limit in test case #69. Moreover, it works on other testcases ~1900 ms. Can somebody give me some pieces of advice?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    I'd finally fixed it. In update procedure added one more verification. If somebody needs, here is my final solution

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain to me G-List Of Integers a bit more detailed? I don't understand the editorial solution

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Well, the main difficulty is that you have to be familiar with inclusion-exclusion principle.

    Let's use binary search to find the answer. Then we need to somehow calculate the number of good integers (good integers are coprime with p) from integer x to integer mid (the middle element in binary search). It's better to rewrite it as count(mid) - count(x), where count(x) is the number of good integers not exceeding x.

    Now we somehow have to calculate this count(x). We need to find all good integers from [1, x]; these are all integers from [1, x] excluding those that are divisible by some prime divisor of p. To find the latter, we use inclusion-exclusion principle: let our sets A1, A2, ..., An be the sets of integers divisible by the first, the second, ..., the n-th prime divisor of p. And then we apply inclusion-exclusion formula as it is — since the maximum number of primes in factorization of p is 7, then we can just iterate through all possible combinations of these sets A1 ... An.

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain, why this solution didn't work? Problem F. The second case broke it. I now, trouble in types of arrays, but I can't fix. SOLUTION

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi, Could anyone explain the last sentence of Problem C solution? Is the solution really possible in O(n)? With the algorithm provided my code gave wrong answer on test 13:
6
1 6 3 4 5 2
01101
Checking just adjacent ones isn't enough right?

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can inclusion-exclusion be used to calculate euler's phi function? Won't it be a special case of it?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Well, actually if we set in A(p, y) mentioned in editorial p = y, then we will get exactly φ(p). So I believe Euler's function can be calculated using inclusion/exclusion, it's just not convenient to do it this way.

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I just wrote the same solution described in editorial and got TLE http://codeforces.com/contest/920/submission/34930869

Is the constant factor bad, or have I misunderstood something?

Nevermind, I'm doing range updates wrong.

  • »
    »
    3 месяца назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    The thing is that you can't just try updating each of the indices from [l, r] if you have REPLACE query.

    You have to use the segment tree for your updates. It is difficult for me to explain. You have to make the queries in a similar manner to mass change queries in segment trees, but instead of pushing some values you need to do the following if you have to update the whole segment:

    1) If the maximum element on this segment is 1 or 2, then just stop updating the segment, you don't need to do anything in it.

    2) Otherwise, if the segment contains more than one element, divide it into two segments (just the way segment tree does it) and try updating these segments.

    I think that our implementation may help. Take a look at how we have written upd function.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How to download Test #15 of 650C Table Compression?

»
3 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Can someone please explain the editorial for problem D. I don't understand it.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem D, how can we handle cases like 3 5000 0 10^15 10^15 10^15 when we cant remove enough water to get V because 1 ≤ cnt ≤ 10^9.

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Why we use "upperbound" in the problem E?By using upperbound,i got AC,without TLE.Could anyone please help me why the author say upperbound for this problem? Thanks in advance :) BledDest,please take a look :)

[UPD: If we take upper_bound,it will help us to detect whether all the numbers in the set are checked or not,isn't it?]

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem A idea is similar to this : http://codeforces.com/problemset/problem/492/B .

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think the SPJ of problem D has a bug, because on testcase 5, an output like this YES 2 6 5 2 6 4 2 6 3 2 2 1 3 2 6 reports wrong answer, but actually it is correct.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is wrong with this for problem F:

https://ideone.com/OtrW2W

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can anybody point out why my code for F TLE'd ?

http://codeforces.com/contest/920/submission/35152778

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

F can be done by just using a BIT and std set. Use the set to keep track of the numbers that have not yet become 1 or 2 (so it serves the same function as the max segment tree) and use the BIT to query range sums.

Edit: Somebody already suggested this

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem F Sum and Replace taught me a lot ! If the update function converges rapidly, then we can just keep a max tree and ignore the nodes which have already converged. In the worst case, we will do 6 O(n) scans !

It's a powerful idea, which can be applied to this SPOJ question too, which also has a rapidly converging update function.