dhirajfx3's blog

By dhirajfx3, history, 6 years ago, In English

Hello Codeforces,

Manthan, Codefest'18 will take place on Sep/02/2018 17:35 (Moscow time) with a duration of 2 hours (tentative). The round is rated for both Div1 and Div2 participants and will consist of 8 problems.

The Department of Computer Science and Engineering, IIT (BHU) is conducting Codefest from 31st August-2nd September. Manthan (मंथन in Hindi, meaning Brainstorming), the algorithmic programming contest under the banner of Codefest, is being held as a special Codeforces round. The round follows regular Codeforces rules.

The round has been prepared by hitman623, karansiwach360, GT_18, Ezio07, Enigma27, csgocsgo and me (dhirajfx3). Special thanks to TooDumbToWin and DeshiBasara for their contribution in the preparation of the round.

We express our heartiest thanks to KAN, vintage_Vlad_Makeev, 300iq, isaf27 and cdkrot for their help in preparing the contest and MikeMirzayanov for the awesome Codeforces and Polygon platforms!

Prizes

Overall 1st place: INR 25000, Overall 2nd place: INR 18000, Overall 3rd place: INR 12000

1st place in India: INR 10,000

1st place in IIT(BHU) Varanasi: INR 4,000 1st place in freshman/sophomore year, IIT(BHU) Varanasi: INR 1,000

About Codefest: Codefest is the annual coding festival of the Department of Computer Science and Engineering, IIT (BHU) Varanasi, which is held online and is open to participation by all! Register on the Codefest website now! Total prizes worth ₹500,000/- up for grabs with events covering domains from Math, Machine Learning, Natural Language Processing and Capture The Flag style competitions. Go to the Codefest website to find out more!

As usual, the scoring distribution will be announced just before the round.

UPD1: Scoring 500-750-1000-1500-2250-3000-3500-4000

UPD2: Following are the winners of the contest

1. tourist

2. DearMargaret

3. LHiC

Best in India

amit_swami

Good luck and have fun!

UPD3: Link to editorial

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

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

The best part of Codefest <3...

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

I hope it will be easier than last year

Last year problem B was a DP :((

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

    so it was your 5th contest last year.

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

    Yeah, it's relatively easy than last time.

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

    Last year problems were harder than problems of the year before last year :)

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

    Dude i don't know how, but you got to div1 in only 1 year. Last year's B was very hard for me too back then. I read it now and solved it instantly. I am sure it will be the same way for you. It's actually just playing with prefixes and sufixes.

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

    Just solved B from last year, DP was definetely overkill.

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

I hope for better problems and better statements than the last year's contest.

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

    People remember an year old event -- the scar must have been real.

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

Here it comes 2-SAT on splay trees of 3D persistent segment trees of dynamic convex hulls tasks.

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

National day of vietnam <3

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

Is there a place in the CodeForces website, showing your division? I know division boundaries don't change frequently, but it would be nice to see.

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

Email says that duration is 2.5 hours but here I see 2

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

    lol, mail says 7 problems, here it's written 8 problems!!

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

      Just confirming: there are 8 problems to be solved in 2 hours.

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

I hope for more problems that can be solved by the amazing SSE/AVX algorithm.

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

    then a matrix multiplication will suffice

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

Manthan in hindi is " मन + थन " which means " mind + boobs ".

So, I guess it means boobs on my mind :P

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

Is it rated for division 3?

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

So is it 2 or 2.5 hours finally?

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

It's my first Manthan,hope to become blue!

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

Can anyone tell what मंथन (manthan) actually means in Hindi? My Hindi is too bad...

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

    It actually means Brainstorming, but if you're looking for something funny, then the words can be broken to get an another, very interesting meaning. Click

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

      lol, this can't have been accidental...

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

Hope the problem statement will be too much interesting and funny. :)

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

I didn't see 4000 problem before this round.

»
6 years ago, # |
Rev. 2   Vote: I like it -36 Vote: I do not like it

.

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

    It probably pertains to when the height of tree is at least 4, such that there is an erroneous nesting while doing the traversal. For e.g.

    INPUT:

    6
    1 3
    1 2
    2 4
    3 5
    4 6
    1 2 3 4 5 6
    

    EXPECTED OUTPUT: Yes

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

For Problem D, what should be the output for following input:-
4
1 2
1 3
2 4
4 2 1 3

Should it be "Yes" because as stated in announcement, a[1] is not necessarily 1?

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

    Announcement states that a[1] is not guranteed to be 1 in tests.

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

    According to the first step in BFS algorithm, vertex 1 is always chosen as root for the algorithm, but a1 is not guaranteed to be 1.

    In this case, answer is "NO".

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

      Oh Thanks. Reading the announcement carefully, I too think that the answer should be "No". But why did they explicitly announce that? I was initially checking a1 to be 1, and then removed that part of code after the announcement. :(

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

        They have probably seen the downvote storm in round 505 because of many FST (failed system test) and learnt the lesson from there =))

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

 4 problems under 10 mins, who said 2 hours isn't enough for 8 problems???

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

Hack for D?

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

    My hacks were:

    200000
    1 2
    1 3
    1 4
    ...
    1 200000
    1 200000 199999 199998 199997 ... 2
    

    (TLE)

    3
    1 2
    2 3
    2 3 1
    

    (WA)

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

How to solve E?

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

    Let's first consider slow solution. Let deg[v] be the current degree of vertex v. Add (deg[v], v) into set, delete minumum degree vertex while it's degree < k and update degrees of vertices. Answer will be this set's size. Now to support queries, we can just do everything from backwards, instead of adding you will delete edge, and now it is easy to implement in O(n*log(n)).

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

      Does your solution still work if the graph consisted of 2 disconnected components?

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

      update degrees of vertices.

      How fast does this update have to be? Because if I understood right, each node is deleted only once, but you have to get to all node's "neighbours" to decrease their degrees before deleting. Wouldn't it be something like O(n^2logn) or O(nmlogn) in total? I know how to optimise it, but can this program pass without any optimisation?

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

        "Naive" implementation is fine.

        The number of neighbour accesses is bounded above by the total number of edges (ie. m), so it comes out to something like O(n*logn + m)

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

    Hint: Reverse the process (instead of adding edges from 1 to m, erase edges from m to 1).

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

      Would be grateful, if you could help with why this code gives Runtime Error on CF compiler.

      Works fine on Local Compiler as well as Ideone.

      https://ideone.com/B8dFH9

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

        You shouldn't erase while iterating:

        for(auto c:gr[x])
        {
            gr[x].erase(c);
            ...
        }
        

        See this.

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

          Yup! Thanks a lot mate!

          After all this time, you still keep learning something new :)

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

    We can answer the queries backwards.

    We build a graph based on the relation, and maintain the degree of each vertices in a set.

    When we answer a query, we remove the vertices with degree < k, and remove their corresponding edges recursively. Then, all vertices has atleast k neighbours. The answer is the number of remaining vertices. After computing the m-th query, we need to remove the m-th edges given in the input.

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

Pretest 4 for D ?

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

    I got caught there too, I think you have to check (when iterating over guys with depth d-1 as parents) to skip over leaves.

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

    I think something like traversing nodes in level i in some order but their children in level i+1 are traversed in a different order (node k appeared before node l in level i but children of node l appeared before children of node k).

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

    Just looking at the levels will not be enough. For example if 4 is the child of 3, and 5 is the child of 2, then 1 3 2 5 4 also comes out to be correct whereas the correct order should be 1 3 2 4 5.

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

      Basically what this is saying is, if parent(a) is visited before parent(b) then a must be visited before b.

      Am I right ?

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

    I guess that test might be checking for naive solutions which only check all nodes in one level, which is not sufficient. It is important to check nodes in each depth in groups based on the node on depth — 1. Compare these two cases:

    7
    1 2
    2 3
    2 4
    1 5
    5 6
    5 7
    1 2 5 3 6 4 7
    

    ANS: No , because 3 and 4 have to be next to each other in the traversal path, whereas

    7
    1 2
    2 3
    2 4
    1 5
    5 6
    5 7
    1 2 5 3 4 6 7
    

    the answer to this test is Yes. Unfortunately, I didn't finish my solution in time...

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

Can someone please tell me what is wrong with this solution: 42389932

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

I'm trying to submit now, but it redirects me to this blog. Why?

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

    You'll have to wait until system testing is done. Only then the problem will be added for practice.

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

https://pastebin.com/71wMF7nP Could someone help me figure out what's wrong> failing pretest 4.

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

    7

    1 2

    1 3

    2 4

    2 5

    3 6

    3 7

    1 2 3 4 6 5 7

    Your code says "yes" to this, while it should be "no". Children of a node in BFS would be printed together. So, correct order is 4 5 6 7. or 6 7 4 5. Depending on 2 3 or 3 2.

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

Can anyone help why does this code give R.E on CF? For Problem E.

Works fine on Local Compiler as well as Ideone.

https://ideone.com/B8dFH9

[Resolved]. I was iterating and deleting the set simultaneously.

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

Great problem statements! No fluff and extreme clarity.

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

How to solve F?

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

    The problem is equivalent to counting for every vi = 1 + i * (k - 1) the sum .

    Assume that with two equal numbers, the one with higher index is larger.

    To solve this, find for every i the values prev[i] and next[i], where prev[i] is the minimum index i such that maximum value in [prev[i], i] = val[i], and next[i] the maximum index such that the maximum value in [i, next[i]] = val[i]. Now:

    Let cou[i] =  the number of intervals [a, b] such that len([a, b]) = vj for some j and prev[i] ≤ a ≤ i ≤ b ≤ next[i]. We can calculate this with inclusion-exclusion: let count(len) be the number of intervals [a, b] such that len([a, b]) = vj for some j, and 1 ≤ a ≤ b ≤ len. Now cou[i] = count(next[i] - prev[i] + 1) - count(i - prev[i]) - count(next[i] - i).

    The answer is .

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

      Oh, how can I not figure out how to do the last step.... it is so neat a solution...

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

        same with me.I don't know why i didnt think of inclusion exclusion after doing the hard part.

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

      Chic Explanation!

      Also, mango_lassi, your named look quite cool, with yellow/orange :P Now red seems to go a bit awkward. Nevertheless, Congrats on becoming a GrandMaster.

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

      You have to run this for each i and for each j, right? Then if the sequence is strictly decreasing and k = 2. Wouldn't this TLE? Or do you combine calculation for all j's together?

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

I tried to hack someone but I got "generator crashed". Can someone tell me what that means?

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

my D will fail because I forgot about that a[0] condition :(

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

    Well I explicitly removed the a[0] condition because I misunderstood the announcement, smh

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

What's intended solution for H? My O(n log2 n) solution got TLE on test 10. :(

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

    Could you please share your idea with me? I tried to solve it with Suffix Automaton and Link-cut Trees but didn't manage to finish debugging in time.

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

    I can suggest the following solution:

    Build suffix automaton for string s. Append symbols to s one by one and answer queries whenever we reach their right border r. To answer the query with string x: feed symbols of x to automaton one by one and iterate over the next (bigger than current in x) symbol. Now we need to check is last occurrence so far of suffix of particular length of current state of automaton  ≥ l. It could be done in the following way: consider the tree of suffix links of automaton, call it T. Then you append new symbol to s, update biggest right border for the state corresponding to the current prefix of s (we must also update right borders for all suffix links of that state, but lets don't do that and ask queries for maximum in subtree of T instead).

    This is in a way I implemented it during the contest (and had wa2 due to some typos). I think it should pass (you will make much less queries than n·A).

    UPD: it passed in 405 ms 42402008

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

      Thanks.

      In fact my idea is very similar to yours, but I used Link-cut Trees to maintain maximum value in a sub-tree.

      Due to the slow data structure, my solution is .

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

Username russianpig get hacked 6 times in a duration of 13 minutes, which sound suspicious to me.

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

How to solve... A?

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it -11 Vote: I do not like it

    solution =

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

      No, it is not. Your solution would fail if n = 2. log2(2) = 1, while answer = 2.

      real solution = (int)(log2(n)) + 1

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

        Edited. The wierdest part is that I actually solved the task :P

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

          Hope it also passes the system tests.

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

        I think the tricky part is not solving the problem but interpreting how you solved it :D

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

    Same. I solved B and C, wasn't able to solve A. I feel like an idiot as everyone got the logic within 5 minutes.

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

    Every number has a primary representation. And never does it happen that you use some power of 2 twice. Thus get all powers of 2 lower than this number! That is (int)log2(n)+1.

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

      So, again, does this problem actually has something to do with prime numbers? I was dancing around those bastards, and almost got an idea, but it seems that it's just powers of two, right?

      Why tho? Some link from that "acquisition" (Aha!) effect is missing and I don't understand which exactly.

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

      I really don't get the intuition behind using powers of 2. Why powers of 2 only, Why not other numbers ?

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

        Because every number can be written as sum of powers of 2.

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

          But it can be written as powers of 3 too.

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

            No. Try writing 6 as sum of powers of three using each power of three only once.

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it
            How many power-of-three packets do we need to cover all numbers up to 222(base 3)(It is 26(base 10))?
            
            The answer is 6. Two 1-coin-packets, two 3-coin-packets, two 9-coin-packets.
            So, if we take only power-of-three packets we will need  2*(int)(log3(n)+1) = 6 packets.
            If we take power-of-two packets we'll need (int)(log2(n)+1) = 6 packets.
            
            As you see answer is same.
            
      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        Because you have 2 options for each packet, either use it or not.
        Edit:
        The idea can be generalized. For example, Say, the question was to find the number of packets required to represent every number upto n, and each packet with value x had 3 optional values (we could only use one option for each packet) -
        1) 0,
        2) x,
        3) 2x.
        Then, we would require log3(n)⌉ packets to denote every number < n.

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

          Hmm that makes sense. Maybe that's why we can't use powers of 3 right ? Where exactly would using powers of 3 or some other would fail ? I can't seem to imagine.

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

            if you want base 3 you need 2 pack each size to get 3 choices. so it would be larger no. of packets.

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

            I edited my comment for a general case, where using powers of 3 would be applicable.

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

              Finally understood your update. Misunderstood it at first.

              Now that i got it. It refreshed my number systems knowledge with a different view.

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

    int(Log2(n))+1. By induction, a packet of 1 gives you 1. and for packets 1, 2, 4, ..., n, you know that this combination gives you from 1 to 2n-1. So adding 2n will give you 2n itself, and 2n+1, .... all the way to 2n+2n-1 = 4n-1 = 2(2n)-1

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

      How do we know that this combination guarantees minimum number of packets. What's so special about powers of 2 ?

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

        Every number can be represented as its Binary equivalent, so think of 13 as 1101 in Binary, ie one packet each of 1,4,8. Splitting in powers of 2 ensures that every number can be made using at most one occurrence of each power.

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

          The question was: can you prove optimality for this construction? What if for some n there is a better split than binary?

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

            The only other way I could think of splitting (in such a way that every number below x could be produced by using at most one occurrence of each packet) is by splitting into multiple packets of 1. I guess these are the only two ways which satisfy the conditions, and among them binary one would use less packets.

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

              Well, no, seems like there can be many other optimal answers: for example, 5 units can be split into (1,1,3), and (4,3,1,1) make 9. I hope for someone to publish a formal proof.

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

                Yeah you're right, there could be multiple ways

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

                yes we can prove that it is optimaly to use powers of 2 as a base to generate 1 to x, consider you have n buckets of number(1,2,4,..2^(n-1)) those numbers can generate 2^n ****different numbers**** and all this numbers are between 0 and 2^n-1 so if we get the binary representation of x and let d is the highest significant bit so let x=1000010101 if we want to generate all number less than x and the highest significant bit is less than d we want n-1 number and these number generate 2^(n-1) different numbers and finaly to get x we only need one another number wish is 2^d and like this you get all number between 0 and x with least size of bucket

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

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

      How do we know that this combination guarantees minimum number of packets. What's so special about powers of 2 ?

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

    In Java, it's one liner: out.println(32 - Integer.numberOfLeadingZeros(n));

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

      Can you explain please ? How's that working? Seems like some play without counting the bits.

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

        The answer is basically minimum number of bits to represent n (which is also sufficient to represent any value smaller than n). Integer is 32-bit and you count the number of zeroes in the beginning of the binary representation of n, 32 minus that count gives you the number of bits needed.

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

        2^3=8 now if u want to make any value which is <=8. Than you will need only 2^0,2^1,2^2,2^3. You need each of those 4 value at most 1 time for making each value which is <=8. For example 7 can be made by 2^2+2^1+2^0. We can use this property to solve problem A. Sorry for bad explanation.I can't explain well but I tried my best.

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

      also, out.println((Integer.toBinaryString(n)).length());

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

    Here is my intuition. At each step we can generate everything from 0 to x. We start with 0 as we can always generate. The next packet we should add is x+1. Now using all these packets we can generate everything from 0 to 2x+1. If we can't add x+1 as it exceeds n, just add the rest and it will be the last packet.

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

((Sorry for my bad english ㅠ~ㅠ I'm not englisher)) I have two question. 1. I didn't lock during Round. than I can't hack?

  1. What is ?? at page [Standing]? ( http://mirror.codeforces.com/contest/1037/standings )

  2. i solve A and B during Round and failed C. than what is in [problems]? ( http://mirror.codeforces.com/contest/1037 ) I am now A red-B none-C red

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it
    1. I guess, yes.
    2. Your program is not checked yet.
    3. I didn't understand. I suggest you using a translator at this point.
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just wait a little (15 mins), all the colors will settle and everything will be much clear,

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

    Thankyou Everyone. I get know about my question!

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

I was wondering why I did well this contest, and then I realized that most of the really good people are at IOI right now.

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

whats wrong with my solution for problem D? I check distances from vertex 1 to a[i] it gives wa4. Who can help? Thanks in advance.

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

    Check this:

    Input:

    6
    1 2
    1 3
    2 4
    2 5
    3 6
    1 3 2 5 4 6
    

    Output:

    No
    
  • »
    »
    6 years ago, # ^ |
    Rev. 4   Vote: I like it +2 Vote: I do not like it
    I think you maybe do the same thing as me.The childs of a node, will be visited together.
    like this case:
    7
    1 2
    1 3
    2 4
    2 5
    3 6
    3 7
    1 2 3 4 6 5 7
    the answer is No
    and 
    1 2 3 6 7 4 5 
    //the answer is Yes (wrong)
    the answer is No
    and for 1 3 2 6 7 4 5
    the answer is Yes
    test it on your solution.
    
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Output for the second case

      1 2 3 6 7 4 5 , should be "No"

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

        yes, you are right, maybe second can be : 1 3 2 6 7 45

        thanks for your help

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

In problem D, can the answer be YES if a[1] is not 1 ?

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

    No. It is told "valid BFS traversal of the given tree starting from vertex 1".

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

can you please tell me what mistake i am making http://mirror.codeforces.com/contest/1037/submission/42395202 i am getting WA on test 11.

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

For problem D is it sufficient to check if for the given order, the levels are increasing and the parent indices are increasing?

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

    Parent indices aren't bound to increase:

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

      I'm sorry if there's any other definition of parent indices, but according to what I mean, the parent indices are increasing in this case because 3's parent's index is 1 and 2's parent's index is 2. I am referring to the index of the parent in the given traversal.

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

        Then you seem to be right, plus you'll have to check if a[1] == 1.

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

    They need to be level wise, as well as in same order as their parents. So, for input like-
    5
    1 2
    1 3
    2 4
    3 5
    "1 2 3 5 4" is wrong, as 2 came before 3, so children of 2 should also come before children of 3.

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

Aside from D's pretests, this year's problemset is much better compared to the last year.

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

Easy solution for D: for each vertex sort the neighbour list by the order they appear in the given sequence.

Then perform a standard BFS from node 1 on the tree and check if your BFS sequence is equal to the sequence in the input.

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

    Used the same approach keeping priority_queue as adjacent list but got hacked. Can you please explain this case, 2 1 2 2 1

    why this should give "No"? mine gives "Yes"

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

      It is told "valid BFS traversal of the given tree starting from vertex 1". In your example BFS is starting from vertex 2.

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

I was using binary search without sorting the vectors in D...corrected the bug in last 10 seconds,,,couldn't submit it...The world doesn't want to see me purple :(

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

There should be auto refresh of problem statement whenever it is updated.

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

First time I managed to solve 4 problems, feels amazing :D

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

Today I encountered an extremely strange behavior of std::stack. I managed to fail today's F problem because of the vector of stacks (42392892). What is strange: I've got an MLE verdict. After the contest I changed the vector of stacks to the vector of vectors and got AC with 20 MB (42402332). Does anyone know what's wrong. Don't I know something about std::stack? Why does it consume so much memory. Or maybe it's just stupid me and I don't know how to use it?

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

    Cppreference on deque (stack uses deque as underlying container)

    deques typically have large minimal memory cost; a deque holding just one element has to allocate its full internal array (e.g. 8 times the object size on 64-bit libstdc++; 16 times the object size or 4096 bytes, whichever is larger, on 64-bit libc++)

    Hope that helps

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

      Wow, at least I've got a valuable experience. Thanks!

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

    Well...

    "The standard container classes vector, deque and list fulfill these requirements. By default, if no container class is specified for a particular stack class instantiation, the standard container deque is used."

    Why tho?

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

Any hint for my solution 42402189 of problem D ? I got Wrong Answer on testcase 11 .UPD: Accepted

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

    Your code gives "No" on following input-
    4
    1 2
    1 3
    3 4
    1 2 3 4

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

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

Who is DearMargaret? LGM in 8 contests. Seems like a fake account, but I wonder whose.

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

    There's no fake account when it comes to being LGM :)

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

it was a good contest,i could have become candidate master today if i had solved D more fastly

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

Seems like there are three groups of problems in this contest. [A-D], [E,F], and [G,H]

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

1 2 1 5 2 3 2 4 5 6 1 5 2 3 4 6

How is this not a BFS Traversal of the given tree?

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

    You start at 1, visit the neighbors 5 and 2 and put them in the queue. Then you are at node 5, visit the neighbor 6 and put it in the queue -> Error

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

    Following the BFS,

    • You arrived at 1
    • You push 1's neighbors into the queue using your order
    • Queue is now 5 2
    • You pop queue's head and thus arrive at 5
    • You push 5's neighbors into the queue
    • Queue is now 2 6
    • This means that after processing 2, you will definitely have to process 6, while your sample order says 3.
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved D by comparing the precedence of parents of ai and ai + 1.

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

Got TLE in F because cin ( even with sync_with_stdio ) I'll never use cin again in my life.

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

    You didn't add cin.tie(0), cout.tie(0);, with which your code ACs in 1653 ms. Click

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

      His code would have got AC if he used >= C++14, probably because of the compiler version.

      I always used cin.tie(0); but I used to think that it made difference only when reading/writing alternately. Omitting it seems to hurt his solution's performance by no more than 100ms on >= C++14, but it hurts just enough on C++11.

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

        You are right. In C++14 it passed with 1500 ms

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

          By the way, nice idea of iterating through the smallest side to avoid the math work :)

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

Problem D. a [1] must be equal to 1. I missed it( I'm crying (

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

D problem : Don't know why it is giving wrong answer on 11th test case. My idea is I will keep on matching parent of an array element with front element and when all children of front element get finished I will pop first element of queue and start the whole process with new first element. Someone please look into it. My submission : http://mirror.codeforces.com/contest/1037/submission/42406584

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

How two learn trees and graph implementation and algorithms for competitive programming ? Any help would be highly appreciated !

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

Can someone tell me why i am getting this error in my code it is working fine in my compiler 42407188

please help me i am not getting what is wrong

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

    Didn't test or really check the code but i can see right away that your MAX is wrong, it should be twice as that, and since you got an overflow error that might be the cause

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

why this testcase for D should be NO? Can someone explain?

6

1 2

1 5

2 3

2 4

5 6

1 5 2 3 4 6

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

    You visited 5 first, so you should visit 5's children first.

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

Can somebody tell me what is wrong with my code (42403836) for 4th problem.Actually I am getting WA on test case no.11 which is a large test case that is why I am not able to debug it.

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

    Your code gives "No" on following input-
    4
    1 2
    2 3
    3 4
    1 2 3 4

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

    You overwrite k and that's why check correctness only on even levels. I'd rewrite your code with a simpler single counter loop, sets are an overkill. Here's another hack:

    7
    1 2
    2 3
    2 4
    3 5
    3 6
    4 7
    1 2 3 4 5 6 7
    
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      HI,shrubb i improve my code now i am not overwriting k,now your test case is also working fine but still getting WA on test case no. 11 , 42416659

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

In problem E Trips , If we had to find the largest group of friends which could go for a walk, Given the condition that at most 1 group can go for walk. (Extra condition added to the question is that all people going on walk should be connected by some links (possibly greater than one link) , the at least k friends of each person condition also remains there).

Then how can we solve this question?

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

    You said that at most one group can go for a walk but think about it. If you had 2 groups that matched the criteria and you combine them, isn't the new group still correct? :) And about how to solve it. Think of the problem as reversed. If you know the group after all the m edges (friendships) are made then you can substract one edge at every step and calculate the new group. If you want the detailed solution you can look at the editorial but I suggest trying it yourself before.

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

      It is not necessary that we can combine two groups. The intersection of the two groups can be a null set. And they both independently would be satisfying these conditions.

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

        You can always combine 2 groups.

        The rule is that if someone is in a group he has to have at least k friends in the same group.

        Now if we have 2 valid groups and we combine them, every person will still have at least k friends because he already had those k friends in the small group.

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

          Yaa right but if the question was to find the largest connected friends group. (The largest among all small group) then how can we find it?

          We cannot combine 2 groups if they dont have any common person.

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

But Is It Rated?