saliii's blog

By saliii, history, 8 years ago, In English

We were waiting several weeks to setting this contest and hope the problem was good enough.

Events

There was a difficulty with 805E - Ice cream coloring/804C - Ice cream coloring. A little bug in the checker fortunately yields accepting an incorrect solution of only one person during the contest. I should apologize all of you because of this.

For this sentence, Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph. You can find the meaning of "connected subgraph" with connected and subgraph, thus it can be empty as it is more logical. How ever, I should apologize all of the participants because of weak sample tests in the statement.

I will write the full editorial in the few next days, now some hints and short solutions exist here.

Hints

805A - Fake NP

hint1

805B - 3-palindrome

hint1

805C - Find Amir / 804A - Find Amir

hint1
hint2

805D - Minimum number of steps / 804B - Minimum number of steps

hint1
hint2
hint3
hint4

805E - Ice cream coloring / 804C - Ice cream coloring

hint1
hint2
hint3

805F - Expected diameter of a tree / 804D - Expected diameter of a tree

hint1
hint2

804E - The same permutation

hint1
hint2
hint3

804F - Fake bullions

hint1
hint2
hint3
hint4
hint5
hint6

Solutions

Tutorial is loading...

From: saliii, Writer: saliii

Time Complexity:

Memory complexity:

python3
C++
Tutorial is loading...

From: saliii, Writer: saliii

Time Complexity:

Time Complexity:

Memory complexity:

python3
C++
Tutorial is loading...

From: saliii, Writer: saliii

Time Complexity:

Time Complexity:

Memory complexity:

python3
C++
Tutorial is loading...

From: MohammadJA, Writer: MohammadJA

Time Complexity:

Time Complexity:

Memory complexity:

python3
C++
Tutorial is loading...

From: saliii, Writer: saliii

Time Complexity:

Memory complexity:

C++

Time Complexity:

Memory complexity:

C++
Tutorial is loading...

From: MohammadJA, Writer: MohammadJA

Time Complexity:

Memory complexity:

C++
Tutorial is loading...

From: saliii, Writer: saliii

Time Complexity:

Memory complexity:

C++
Tutorial is loading...

From: saliii, Writer: amsen

Time Complexity:

Memory complexity:

Java8
C++
C++

As my good friend, Arpa, did, let me share with you a perfect poem of one of our best poet you might know, Molavi:

.......................................................................................بند بگسل، باش آزاد ای پسر ** چند باشی بند سیم و بند زر

O son,  burst thy chains and be free! How long wilt thou be a bondsman to silver and gold?

.......................................................................................گر بریزی بحر را در کوزه‌‌ای ** چند گنجد قسمت یک روزه‌‌ای‌‌

If thou pour the sea into a pitcher,  how much will it hold? One day's store.

..................................................................................... کوزه‌‌ی چشم حریصان پر نشد ** تا صدف قانع نشد پر در نشد

The pitcher,  the eye of the covetous,  never becomes full:  the oyster - shell is not filled with pearls until it is contented.

.............................................................................. هر که را جامه ز عشقی چاک شد ** او ز حرص و عیب کلی پاک شد

He (alone) whose garment is rent by a (mighty) love is purged entirely of covetousness and defect.

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

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

Auto comment: topic has been updated by saliii (previous revision, new revision, compare).

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

If we had these types of editorials for future contest as well, could be good. Sometimes all you want is hints :)

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

    I totally agree, this is what editorials here need.

    It would be awesome to have hints after every contest, it's really all you might be missing to solve a problem(especially when you're upsolving).

    Thanks saliii !

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

We were waiting several weeks to setting this contest and hope the problem was good enough.

Why didn't you write full editorial for this several weeks?

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

    we were trying different problems, there is near 4 or 5 really good problems, we don't use them here for different reasons. And we wrote a big part of editorial! To be honest, We started preparing the contest from 4 mouth ago.

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

In Div2 E /Div1 C , How to implement what is written in the editorial ??? I realized the hints during the contest but I really could not come up how to implement it efficiently ???

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

    Do dfs from any vertex T and keep set of used colors in each vertex. When you come in some vertex try to set colors for each type in way like:

    int color = 1;
    while (used_color[v].count(color)) {
        ++color;
    }
    

    After you set a color for a type do another dfs from this vertex in every other vertex which have same type and insert this color in their used sets. Total complexity is .

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

    I do not understand Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph in problem. Form a connected subgraph of what graph and in which graph?? ignoring this forms G a forest like structure of cliques.

    tia

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

      Forms connected subgraph in original tree. So all vertices with same type are connected by tree edges. For example 1 to 1,2 to 2 is ok, but 1 to 2 to 1,2 not okay (as 1 and 1,2 should be connected by edge to form connected subtree). It wasn't clear for me too.

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

        thanks, i looked at your comments below, now clear why graph in your ex is invalid. so G will be a disconnected graph of cliques and hence min col is max size of a clique.

        am i right??
        

        no i am not right. i'm being stupid.

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

nice contest

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

In Div1 C Editorial:

The trivial upper-bound should be maximum size of vertices sets.

I think this is a trivial lower-bound of the answer, perhaps it is trivial as upper-bound too but in that case is trivial that this is the answer.

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

Okay, I understand why it's not nlogn.

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

Why All of my submissions show skipped? Though all of them are passed in system test.

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

This was my first contest, can anyone help me with Div2 D problem ? I am not able to figure out the logic from hints.

Thanks.

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

    My approach: consider x letters 'a' in a row and a single letter 'b'. Try to figure out the required number of steps to turn this to (many letters b + x letters 'a') for an arbitrary x.

    For example, x = 3 (x = 2 is given as a problem sample) aaab -> aabba -> abbaba -> bbababa -> bbbbaaba -> bbbbabbaa -> bbbbbbabaa -> bbbbbbbbaaa :)

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

      can you pls elaborate more?? i tried but not able to follow.

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

        Ok :) The fact that can be used to solve this one: should you have x letters 'a' and a single 'b', this will soon turn to a string of y letters 'b' and x letters 'a'. What's the value of y? :) As given in samples, aab will turn to bbbbaa.

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

          i followed someone's solution sol and what it does is: iterate from right and find answer for index where a's are present and update number of b's right to this. is it not miscounting as in your above ex if we follow this pattern then in 4th step(bbbbaaba) leftmost a has to wait 1 more step to be interchanged. how is it compeseted overall??

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

    The end of changes is string s like b....ba.....a, because you can't find substring ab.

    Okey, let's try to do this string, as we can see when you meet ab it replace with bba, so a and b swap, but if we have aab it became abba, so we can find new ab and after two moves it becames bbbbaa and so on...

    So, when we find new ab, it will not changes smth after it, just previous string, because of that we can iterate from left to right, count all a, and, when we find b, swap all found a with this b.

    If you modulate this process, you see, that if you have n a before b you will make 1 + 2 + 4 + ... + 2n - 1 moves or 2n - 1.

    And we got solution:

    int counta = 0;
    int ans = 0;
    for (char c: s){
        if (c == 'a')
            ++counta;
        else
            ans += (2 ^ counta) - 1;
    }
    

    just use precalc or bin_pow with module

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

Ice coloring: Could someone explain how following given tree topology — colors it correctly? Which part of problem guarantees it?

For example not following tree, just processing by tree vertex index, would fail on test 143 that is a custom hack.

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

    Did you understand why processing by tree vertex index is wrong?

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

      I understand why it's wrong. But I don't understand why processing by tree edges is correct.

      For example 2 3

      1 1 1 2 2 1 2

      1 2 2 3 Would fail when processing by tree edges, but why this input is incorrect?

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

        Umm, is the input correct? I think the edges should be 1 3, 2 3 due to each icecream being in a connected subgraph.

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

          Ok, thanks, now I understand that each type of ice cream must form connected subgraph in a tree.

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

            I don't know why processing by tree vertex index is wrong though. I think there should always be enough colors to avoid clashes, which means it should work. Hopefully someone clarifies.

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

In 805F — Expected diameter of a tree, may I ask how to get the maximum path of each vertices in a graph? Is it run from a vertex to all vertices in its graph to get that vertex maximum path or is there a better way to do it? Thanks.

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

    Prove me someone if I am wrong, but we can find center(es) of tree and half of diameter + distance to closest center is maximal distance

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

    As I finding and try to learning from the provided solution, finding the diameter for each vertices in graph needed 3 times doing the dfs, the first one is finding the farthest vertex from a vertex (V), the second is calculate the diameter of the vertex from vertex V and also finding the farthest vertex again, and the third is to calculate the diameter from the other farthest vertex from second dfs. Is my understanding true? Thank you :)

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

      In editorial, there is a code with 3 dfs! but I think we can do it by a simple dp_up down in 2 dfs maybe!

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

804E — The same permutation Hint 1: Should be 4*k + 2 instead of 4*k + 4.

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

Ok. Obviously stupid question, but still I don't know how to prove that: sum sz_i = n => sum min(sz_u, sz_v) log(max(sz_u, sz_y))=n sqrt(n) log(n)? I suppose, we should prove that sum min(sz_u, sz_u) <= n sqrt(n)... Thank you

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

    .

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

    Imagine you have a graph where each vertex represents one of the components and has weight equal to the size of that component. Your task is to draw n-1 edges weight of each is equal to minimum among vertexes it connects in order to maximize the total weight of edges. It's obvious that the worst case happens when you form a clique of x heaviest vertexes (such that (x — 1)x = 2n since multuedges aren't allowed). That gives you that each vertex has no more than sqrt(n) edges. That's it :)

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

    As I didn't see anybody explaining the simple solution I decided to do so.

    Well it's not exactly what you ask but I think you will understand my solution better (and it works in ). First you must be able to solve the problem for two trees in O(szu + szv) time. In the editorial there is a . If you do the one described in the editorial your solution will simply run in time.

    So now lets solve the other part of the problem. Lets consider 2 case:

    1) For a query (u, v), . For such queries we simply run the or O(szu + szv) solution. The overall complexity for such queries then will be or .

    2) For a query (u, v), . Lets assume that szv ≤ szu. How many trees u such that exist? Well you can simply prove that they are at most , because . Then we can precompute for every "heavy" tree u answer with every other tree v. For a fixed tree u this precompute will have complexity O(N) or depending how you solve the problem for 2 trees. Then this part will be done in time (or ) and will take memory.

    So then the whole solution will take or and memory.

    Here is my Accepted code: 26851219

    PS: You can see a constant B which I use as . Idk why during the contest I thought . It's actually about 315.

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

      Separating big and small components is useful for analysis but in code you can just solve for each query separately and reuse the answer in case of duplicate queries

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

        Oh nice. I actually thought about that during the contest but that the complexity seemed O(N * Q) to me. Now when I thought for a bit it actually is easily provable that the complexity will be . Thanks for sharing :)

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

      How do you solve two trees without log? You do still need to sort verticies with farthest distance from them, right? (And then two pointers)

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

        Read your code and got it, thx.

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

        We will use the following observations:

        1) If we have a tree the furthest vertex away from any vertex u will be one of the two ends of any diameter of this tree. You can easily prove this. Let's define d(u) to be the maxiaml distance from vertex u to any other vertex in its tree. Using this observation we can find d(u) for every u in by preforming a couple of DFSes (first we find a diameter of the tree and the we do one DFS from both its ends).

        2) When we add the edge between the two trees we will have dimeter equal to max(diamT(u), diamT(v), d(u) + d(v) + 1). Let's define D = max(diamT(u), diamT(v)). Obviously we can solve the problem independently for one of the trees. By this I mean we pick one of the trees and then for every​ vertex of the other tree we get the expected diameter if we have chosen it as one of the ends of the edge we will add. Then we if that vertex is u we need to find the count of vertices v such that D > d(u) + d(v) + 1 because for them it is optimal to save our previous diameter. This inequality equivalent to D - d(u) - 1 > d(v). From right we have a constant. How can we find the number of vertices v satisfying the inequality? We can use partail sums. Same goes for the case when D ≤ d(u) + d(v) + 1 but there we do partial sums of d(v). You can reffer to my code.

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

805D-Minimum Number Of Steps what is wrong with this solution somebody help me.

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

Auto comment: topic has been updated by saliii (previous revision, new revision, compare).

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

For Div1 C / Div2 E, would it be possible to get input data used for #17 ?

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

Hi, here is one question, for 804C Ice cream coloring. Will this algorithm work? During inputting tree T, record every pair of ice creams in every set of T's vertex as an edge of G. For example, if there are k ice creams in the set of a T's vertex, then we add k(k - 1) / 2 edges for G during its input(eliminating duplicates). After the construction of G, run a traditional colouring algorithm for it. Such solution doesn't use T as a tree and there is no dfs. But wrong at test case 3. I wondered what is wrong for the whole day:(

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

    There might be O(n^2) edges on G, that doesn't fit memory/time. Edit: also, iirc coloring a general graph is np-complete (might be wrong).

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

    me too have same problem. can't figure out what's the use of input tree T.

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

Auto comment: topic has been updated by saliii (previous revision, new revision, compare).

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

I am getting TLE on test 25 for Div2 F/Div1 D. Can anyone tell what the problem is I can't seem to find it thanks in advance. Code : http://codeforces.net/contest/804/submission/26910532

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

Auto comment: topic has been updated by saliii (previous revision, new revision, compare).

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

Can anyone plzz explain me why my solution is wrong?? http://codeforces.net/contest/805/submission/26964381 actually it gives correct answer for test case#13 on my machine..

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

    The calculation of xb*(a[xa]-1) overflows if int is 32-bit.

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

A bit simpler solution for the problem 804E (DIV1E).

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

I want to ask some questions about Div1 F.I can't understand the last part that is calculating the ans knowing mincnt[i] and maxcnt[i].For every j(j+bigger+1<=A), your code adds C(upper,j)*C(bigger,b-1-j) to the ans.But j is the number of mxs that are bigger or equal to mx[j] while the problem said "if there are no more than a - 1 gangs with power strictly more than p".Then there may be some situations you do not calculate such as many mxs are equal then your j if not about the number of strictly more than p,but is about mxs that are bigger or equal.Can someone help me?Am I right?

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

I have a question about Div1.F.

Look at this case:

5 2 2
01011
00011
11000
00100
00110
10 1110100101
1 1
7 1001000
4 1001
10 0110001100

As the whole graph is an SCC ,the mn and mx are:

mn[1]=6,mx[1]=10
mn[2]=1,mx[2]=1
mn[3]=2,mx[3]=7
mn[4]=2,mx[4]=4
mn[5]=4,mx[5]=10

if we set the score as follow:

score[1]=6
score[2]=1
score[3]=4
score[4]=4
score[5]=4

then we can choose any 2 gangs from gang 1,3,4,5, so the answer should be 6.

But the std code gives 4.

I wonder if i understood the problem incorrectly.Thanks!

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

In the question A (fake np) the answer in the second example (which is 3) is different from the answer that is tested during compiling the program on the website , why did the author do such a thing??

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

    both 2 and 3 are right answers

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

      what should be the answer if l and r given is 26 and 27?.... acc. to me it should be 3 ..correct me If I m wrong?

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

I think in solution of problem C, there was a kind of mistake (python)

(int(input())-1)//2 just '/' instead of "//" maybe

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

what would be the answer in question A ...if l and r given is 26 and 27... answer should not be equal to 3 instead of 2...correct me if I m wrong !!

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

Am I only one who doesn't understand div1C/div2E problem statement???