By TLE, 5 weeks ago, In English,

Hi!

I'm glad to invite you to participate in Avito Cool Challenge 2018 which starts on Dec/16/2018 17:35 (Moscow time). The round will be rated to participants of both divisons.

img

The problem setters are fjzzq2002, yjq_naive, fateice, yanQval and quailty.

We would like to thank:

This round is conducted on the initiative and support of Avito. Avito.ru is a Russian classified advertisements website with sections devoted to general good for sale, jobs, real estate, personals, cars for sale, and services. Avito.ru is the most popular classifieds site in Russia and is the third biggest classifieds site in the world after Craigslist and the Chinese website 58.com.

Avito presents nice gifts for participants. Top 30 participants and also 10 random participants with places 31-130 will be awarded with a special T-shirt.

You will be given 8 problems and 2.5 hours to solve them. As usual, the score distribution will be revealed shortly before the contest.

This is the first contest on Codeforces for most of us. Hope to see you participating! Good luck!

There will be an interactive problem in the round. If you have never solved interactive problems before, please read this.

UPD: The scoring distribution is standard 500-1000-1500-2000-2500-3000-3500-4000.

UPD: Congratulations to winners!

Also, you can find the list of T-shirt receivers here.

UPD: Editorial

Announcement of Avito Cool Challenge 2018
 
 
 
 
  • Vote: I like it  
  • +557
  • Vote: I do not like it  

»
5 weeks ago, # |
  Vote: I like it +79 Vote: I do not like it

a round setted by 3 legends!

it is gonna be a legendary contest

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

Can't wait for this cool contest :D

»
5 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

Reminds me of "Aviato" from Silicon Valley Series XD

»
5 weeks ago, # |
  Vote: I like it +51 Vote: I do not like it

img

Chinese Round!

»
5 weeks ago, # |
  Vote: I like it -50 Vote: I do not like it

choutii for playing a crucial role in the contest. (you'll see.)

Both of you choutii and fjzzq2002 studying in Fuzhou No.3 High School. And I am not blind

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

I need a lot of math in this contest.

»
5 weeks ago, # |
  Vote: I like it +99 Vote: I do not like it

There will be an i̶n̶t̶e̶r̶a̶c̶t̶i̶v̶e̶ binary search problem in the round.

»
5 weeks ago, # |
  Vote: I like it +70 Vote: I do not like it

Traditionally, we publish algorithm of selecting random winners before the round.

randgen.cpp
get_ranklist.py

The seed will be the total number of points of three best participants of this contest, length is 100 (130 — 30) and nwinners is 10.

»
5 weeks ago, # |
  Vote: I like it +77 Vote: I do not like it

tourist I think this contest will be the best revenge Radewoosh

»
5 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

rua!

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

I am looking forward to participating this legendary contest created by fjzzq2002!Three Legends! %%%Fjzzq2002!!

»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

I like Chinese rounds.

»
5 weeks ago, # |
  Vote: I like it +68 Vote: I do not like it

Chinese Round but a little bad time for Chinese high school students...

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

    Sorry about that, but an opencup will end half an hour before the contest, so we can do nothing :(

»
5 weeks ago, # |
  Vote: I like it +32 Vote: I do not like it

when reading the Avito

»
5 weeks ago, # |
  Vote: I like it +207 Vote: I do not like it

Will problem setters get T-shirts too? :D

»
5 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

previous Avito code challenge is a good one for me(+100) hope this contest will also give a lot of increase in rating and for other also.

»
5 weeks ago, # |
  Vote: I like it -49 Vote: I do not like it

Will we get rating from this contest?

»
5 weeks ago, # |
  Vote: I like it -34 Vote: I do not like it

IS it ICPC rules ? and are the 8 questions too much?

»
5 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

I am wondering watching gritukan profile . Won't you ?

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

Good Luck! :D

»
5 weeks ago, # |
  Vote: I like it -63 Vote: I do not like it

Is It Semi-Rated?

»
5 weeks ago, # |
  Vote: I like it -60 Vote: I do not like it

That silly registration process is annoying, fuck hacking, fuck rooms

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

zzq and fateice!the proud of fzsz!

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

In CP, You get T-shirts in winter XD

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve D?

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

    Think in terms of mst. Consider all the edges which directly or indirectly connects any 2 special nodes. Among all such edges find the one with maximum wight. This passed system test for me.

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

      I did but what to do after that? How to find maximum distance for each special node after constructing the tree?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it -12 Vote: I do not like it

        I have updated my comment. Try proving the solution yourself. It is interesting.

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

    Find the MST, and then choose the relevant subtree that contains all the special nodes. The answer is going to be the maximum edge weight in this subtree repeated k times.

    The MST has the property that it minimizes the maximum edge between in a path between nodes a to b.

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

      I think it will not be maximum edge weight for ex: 4 3 2 3 4 1 2 10 2 3 1 2 4 1 Here the answer will be : 1 1 Correct me if am wrong.

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

        We have to choose a SUBTREE of the MST that contains all the special nodes.

        The 1-----2 edge will not be part of this MST subtree

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

          Yes you are right, I did not read your comment properly, my bad.

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

    I did using a binary search to find the maximun edge that is necessary to contains all special nodes. The answer will be this maximun edge for all nodes.

»
5 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

I wasted too much time on A-E and couldn't find time to code problem H :(

My approach would be something like this:

We may calculate number of distinct palindromes and . First estimate would be , but there will be some pairs which we counted twice. What are those strings which may be obtained in several ways? They always may be viewed as where , , and are palindromes. This immediately implies that is the period of both and and this is one-to-one correspondence. Good news is that we may find all possible minimum periods of all palindromes in both strings and . Now we should calculate number of strings which may be glued with where is one of minimum periods we found, seems like an easy task to do with eertree and some hashes, given that you have enough time to code it.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -49 Vote: I do not like it

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

    I tried something similar.

    I made the pallindromic tree for both strings, now, to find the number of such y's, I calculated, for each reversed suffix links in A, the number of suffix links in B, so I made hashes of all these suffix links and inserted them in a multiset. But I had a bug in the code. Also, I cannot prove the suffix link idea is correct, so most probably it's wrong since it has 0 solves :p.

»
5 weeks ago, # |
  Vote: I like it +62 Vote: I do not like it

G is awesome. Could anyone share his/her solution?

As for the others. I found the contest quite nice overall. I failed on D and saw that only after locking. I'd say the biggest issue that I could see with the contest was the very weak pretests in D. Basically you'd pass them if you compute the maximum distance between any 2 points, not necessarily special. Then, regarding the same issue, this left plenty of space for hacks. And apparently rooms are very badly calibrated. In my entire room, there were only 5 (4 until 10 mins ago) people that even tried D (me included). So not only have I locked D and couldn't get a later AC, but my gain from hacks was only 100 points, whereas others had 4-5 hacks on D. I was close to having a good performance, but trying not to be biased, I think I'm not lying when saying that nobody likes having weak pretests. Basically you might misunderstand the problem, solve a wholly different problem and still pass the pretests.

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

    Basically you'd pass them if you compute the maximum distance between any 2 points, not necessarily special

    Really? Why would you even do that? I saw people getting hacks on D but nothing happened in my room...

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

      That's what I submitted too...

      It's the answer if you read it as "for each special vertex, find the farthest (not necessarily special) vertex from it".

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -38 Vote: I do not like it

    If there is a person to blame, i think it should be you. You should blame yourself for not reading statement carefully. Many people solved it, so you shouldn't blame the pretest.

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

      Was I blaming anyone? I just said that it's shitty when this happens and nobody particularly enjoys it. I thought the purpose of the pretests is to help you get rid of silly/obviously unintended mistakes. If this is not true, then why do we have pretests at all? When there are some poor pretests, there are 2 categories of people: those that fail, definitely didn't enjoy failing on some easy problem because of a corner case, and those that don't, that still shit their pants when seeing so many hacks and WAs and double-triple check their sources, wasting time, instead of focusing on the beauty of the contest: thinking about the other problems. So I was just claiming that it's not a nice thing to do, and that nobody actually enjoys the fact that the pretests are weak (to be noted, that in this problem, the most random tests would've shown the bug, so the pretests were especially designed to hide this sort of wrong interpretation)

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it -72 Vote: I do not like it

        I don't care about the pretest. You just use the reason to satisfy yourself that you may still better than someone who solved the problem you failed, when the fact that you ruined your work yourself, while they were not. If i were you, i would accept the fact that i read the wrong statement and try hard next time, instead of leaving a complain.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
          Rev. 2   Vote: I like it +11 Vote: I do not like it

          Hmm so now I wasn't blaming anyone anymore, was I? Now I was complaining. Next, I'll be whining and so on. My point was: good contest, liked the problems, would've liked the overall experience more if the pretests were better and I'm sure I'm not the only one. This is not complaining, but stating a fact to remind the setters that nobody enjoys it.

          If you're so much willing to support an opposite point of view, then better try to add some arguments. If you don't care about pretests, then obviously something's wrong with you. I wonder why IOI and ICPC are full feedback. Ahh maybe, because they want to emphasize the idea, and not the code? Neah, can't be that

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

            Okay, i think that blaming is similar to complaining. Anyway, i'd like to think that when we fail and other people aren't, then the failure should because of our mistakes. Pointing out the weak pretests is necessary for Codeforces community, as it helps improving the contest quality. i just don't like when you said that the weak pretests affected your perfomance. This is the fact, but there is also another fact that you ruined it before the pretests by reading wrong statement. What you said is like prefer the first fact than the second one, which is what i wouldn't like. So i tried to tell you this, but it became a bad argument.

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

              Dude you blamed all your FIFA opponents for rekting you and you are here being hypocritical about what lmao???

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +11 Vote: I do not like it

    Not only pretests were weak, but system tests too, which makes it more fair.

    Here is O(m*k) accepted solution, which I did not manage to hack within contest.

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

      Isn't that solution O(M * logM)? It looks like he baited you with bad indentation.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it -18 Vote: I do not like it

        I guess that because of your comment I got downvotes, for bullshit and blaming strong tests :) Well this is O(m*k) as I wrote and here is the test exposing this:

                printf("100000 100000 50000\n");
        	REP(i, 49999)
        		printf("%d ", i + 1);
        	printf("50000\n");
        
        	printf("1 2 1\n");
        	REP(i, 49997)
        		printf("%d %d 1\n", i + 2, i + 3);
        	FOR(i, 49999, 99999)
        		printf("%d %d 1\n", i + 1, i + 2);
        
        	printf("1 50000 2\n");
        	printf("1 50000 2\n");
        
        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          You're calling bs but I copied the test and the solution and it runs in under 2 seconds in my (slow) computer... ? Did you care to try the test?

          Edit: In fact, I ran that test on custom invocation with the input hardcoded and it got 30ms

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
            Rev. 5   Vote: I like it +18 Vote: I do not like it

            You must have a very fast computer or use a different test. Here is the result on a fast computer:

            It took me 3398 clicks (3.398000 seconds).

            Edit. I also run it on cf and it runs in 15 ms. I don't understand that. I even added counter inside inner for loop

            for (j = 2; j <= k; j++)
            

            The value of that counter is 2,5*1e9, which proves that it runs in O(m*k). I don't understand how is it possible on cf to run so fast...

            Edit. I even multipled constraints by 10 and on my machine it runs as expected — extremely long. On CF it runs in 93 ms and outputs very small number of total iterations. I completely do not understand this weird custom invocation behavior:

            Expected number of iterations during local testing: 249999999999

            CF custom invocation: 1666656

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
            Rev. 3   Vote: I like it +26 Vote: I do not like it

            I found the issue. Please replace sort with stable_sort to get huge TLE or use different weights on edges. In case the values are the same the order can be arbitrary and it happened that first edge with 50000 appeared in the end instead of being in the middle.

            Edit. I think that KNB. might be interested, as he also noticed that and tried to hack that solution.

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

              I see, that's true. Nice catch.

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

      Tests on E were also weak. Solutions which can set x_i = 0 like: 47142808 or 47119126 by mnbvmar were accepted. This fails for example on:

      4
      600 600
      
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +35 Vote: I do not like it

        Added test for the upsolving

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Have you added perf test to D too?

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            There was some discussion going about it, give me the last version and I will surely do :)

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

That was really interesting and close.

if V--o_o--V got just one successful hacking attempt, he would have become the first.

Edit: nvm :(

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

How to solve E?

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

    for each number you have the sqrt of the sum of numbers before it bf, and number next to it nxt. now you need to find an x such that ll(sqrt(a * a + nxt)) == sqrt(a * a + nxt) and a = bf + x . I don't think binary search would work, so I iterated while ((a + 1) * (a + 1) - a * a <= nxt) which means that the difference between the next perfect square is already bigger than nxt and we have no answer if that happened, and nxt <= 1e5 so that will fit in the time limit. Tho I don't have any proof whether the first number that fits will be the only one that does.

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it +40 Vote: I do not like it

      We can prove that we want to always greedily take lowest possible square for any prefix. Lets consider 4 numbers, first and third of them we can choose. Consider the case when multiple prefix sums can fit the prefixes of sizes 1-2, but only one value fits prefixes of size 3-4.

      In this case we can take any of lower values for 1-2 and adjust 3-4 up to needed numbers by adjusting value of number 3.

      Formally:

      • a1 = A
      • a1 + a2 = B
      • a1 + a2 + a3 = C
      • a1 + a2 + a3 + a4 = D

      And we have two different values for A and B: (A1, B1) and (A2, B2). So we can satisfy them with proper values a1 and a2. And then choose a3 = C - a1 - a2.

      The only limitation is that a3 > 0. So choosing minimum B is not only valid, but also optimal.

      Consider this geometrical interpretation. From up-left to right-bottom: green area is a1, yellow is a2, blue is a3 and pink is a4. On both pictures areas of yellow and pink are the same (up to my drawing skills quality), but we can freely choose green and blue areas to preserve total area of C and D unchanged.

      And this idea can be easily generalized for higher number of prefixes.

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

      wewark I think you meant a*a = bf + x and not a = bf + x .

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

        sorry, bf is the sqrt of the sum of the numbers before, not the number itself. Fixed.

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

    I did it with a greedy algorithm. For every odd i find such an a[i], so sum (a[1..i-1]) + a[i] + a[i+1] is a correct square, using the fact, that we can make any correct square from sum (a[1..i]), that is less than sum (a[1..i-1]). So every time i seek for the minimal square. We can stop seeking, when a[i+1] is less than 2 * sqrt (sum (a[1..i])) + 1.

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

    I did it with a greedy algorithm. For every odd i find such an a[i], so sum (a[1..i-1]) + a[i] + a[i+1] is a correct square, using the fact, that we can make any correct square from sum (a[1..i]), that is less than sum (a[1..i-1]). So every time I seek for the minimal one. We can stop seeking, when a[i+1] is less than 2 * sqrt (sum (a[1..i])) + 1.

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

Can we do F deterministically? If yes then what is the approach?

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

    In general, we can't. For example, see array with size 2. 01 and 10 are indistinguishable.

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

Is pC C(m,n/(n-k))

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +49 Vote: I do not like it

    It is

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

      I managed to find the formula during contest and submitted exactly the same. But it gave WA on pretest 5. I guess I messed up ordering of modular arithmetic. :(

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

      Can you please explain?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it +16 Vote: I do not like it

        So there are k + 1 blocks. Choosing the sizes of the blocks and the colours are independent of each other, and the answer is the product of the two.

        • colour arrangements: For the first block, we have m options, but for the other k blocks, it must have a different colour than the previous one, so there are m - 1 options for those. This gives m(m - 1)k.

        • Block sizes: Every block must be of size  ≥ 1, so let s1, ..., sk denote the starting positions of the second, third, etc. block. Then we have 1 < s1 < ... < sk ≤ n, so . Thus we are picking k 'balls' out of n - 1 'items'. This is .

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 3   Vote: I like it +1 Vote: I do not like it

      Is it the correct one ? I submitted the same but got WA on pretest 4 !! and then applied DP seeing the constraints :(

      Edit — I made a modular arithmetic mistake :3

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

      Completely misunderstood the problem. I thought there are k different bricks in total with color different from each brick except the last one.

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

What are the hacks in D? I see a lot of hacks.

»
5 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

i couldnt solve b. Can anyone please telll the solution?

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

    please?

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

      Here is my solution, but I feel like there's a simpler one out there. I recommend waiting for the editorial.

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

      I'll tell you how I approached it. First, Observe that all people who are wearing the same type of hat will have the same value of a[i] i.e. people differing will be the same. Although vice versa is not true.

      Maintain a hat ID variable starting from 1.

      FOR ith person who is not assigned any hat number:

      count the number of people having the same values in a as a[i]. let's call them SAME and count the people having different values in a, other than a[i].let's call them DIFF.

      if DIFF is greater than a[i] that means sequence b is not possible.

      if DIFF is equal to a[i] then all the people counted in SAME will get the same hat number. Assign the same hat ID to all people counted in SAME.

      if DIFF is less than a[i] then (a[i]-DIFF) people counted in SAME will not get the same hat number. Hence assign same hat ID to ( SAME-(a[i]-DIFF) ) people counted in SAME. Don't assign any Hat ID to the rest.

      increment hat ID variable.

      END FOR loop.

      Here's my code.

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

    For each people we can say the number of hats of his kind — it's n - a[i]. Then we can count the number of people, the number of hat's of whose if n - a[i]. X people for Z hats. If for each number from 1 to n X % Z == 0 — we can answer. Otherwise, it's impossible. We can choose the types from 1 to n in this order:

    int ttype = 0;
    for (int i = 0; i < n; i++)
    {
    	cin >> a[i];
    	if (numb[n - a[i]] % (n - a[i]) == 0) 
    	{
    		ttype++;
    		type[i] = ttype;
    		numbtype[n - a[i]] = ttype;
    	}
    	else type[i] = numbtype[n - a[i]];
    	numb[n - a[i]]++;
    }
    
»
5 weeks ago, # |
Rev. 2   Vote: I like it +182 Vote: I do not like it

Please stop using l (lowercase L) as a variable name in problem statements.

On problem 1081F - Коварный интерактор, I thought "the interactor will either flip [1, r] or [l, n]" was "[l, r] or [l, n]" and spent over half an hour solving the wrong problem.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +27 Vote: I do not like it

    I think l is similar to 1, but l is not similar to 1.

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

      Looking similar doesn't justify the use of wrong characters. Don't you think?

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

holy terrible implementation on F

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

    +1, I spent like 40 minutes trying to figure out when to invert the value of s[i]...

    PS: I still think the problem was awesome

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

what was test 15 in E?

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

It was great being purple for a day. :(

Will probably fall about 30 rating points.

EDIT: WTF Got hacked and failed two problems. RIP pretests.

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

really nice problems !! it was fun to think about :D even so C made me confused with probabilities and couldn't solve it

See problem setters we don't get mad because we didn't make good result it's because the problems aren't fun to think about

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

My solution of C failed on pretest 4. But i didn't find the right case. Can somebody, who failed at pretest 4 first, please, explain, where is mistake?

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

    I had ifs:

    if (k==0)return cout<<m,0;

    if (k>m)return cout<<0,0;

    I removed them and got ac, formula is: d[i][j]=d[i-1][j-1]*(m-1)+d[i-1][j];

    Before processing this formula i put every d[i][0] to m (1<=i<=n)

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

      Thank you! I did't think about dp. But I haven't got the problems with this cases...

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

Tourist is going to take back the first spot!

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

How to solve B?

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

    I'll tell you how I approached it. First, Observe that all people who are wearing the same type of hat will have the same value of a[i] i.e. people differing will be the same. Although vice versa is not true.

    Maintain a hat ID variable starting from 1.

    FOR ith person who is not assigned any hat number:

    count the number of people having the same values in a as a[i]. let's call them SAME and count the people having different values in a, other than a[i].let's call them DIFF.

    if DIFF is greater than a[i] that means sequence b is not possible.

    if DIFF is equal to a[i] then all the people counted in SAME will get the same hat number. Assign the same hat ID to all people counted in SAME.

    if DIFF is less than a[i] then (a[i]-DIFF) people counted in SAME will not get the same hat number. Hence assign same hat ID to ( SAME-(a[i]-DIFF) ) people counted in SAME. Don't assign any Hat ID to the rest.

    increment hat ID variable.

    END FOR loop.

    Here's my code.

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

    Here a[i] is the number of persons who wear different hat from him.
    Hence, n-a[i] is the number of persons who wear similar hat to him.

    Now, group the indices whose n-a[i] is equal. Insert i in the group[n-a[i]].
    If for any group[i], size of the group is not divisible by i, then print Impossible
    Otherwise, maintain a id starting from 1. For each group[i], iterate through all the indices in
    it and for every i indices, set their value of b[] to the counter value and increment the counter by 1. Then print Possible and the array b[].
    Update: Here is my code: https://pastebin.com/QWf0gbsB

    Sorry for my poor English. Feel free to comment, if you don't understand the solution.

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

      one this i don't understand. please explain...

      Depending on what condition , counter value will be increment by 1. And one more this,Why divisible is require for Possible or Impossible. please explain conceptually.

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

why are other's submission still not public ? :(

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

If we say in C that k is not just for left bricks, but to all bricks (every brick can be painted with m colors, but all bricks in the end need to have k different colors), what is formula for dp[n][k] then?

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

    DP[0][0] = 1;

    DP[i][j] = m*DP[0][j] + Sigma(x from 0 -> i-1) (m-1) *DP[x][j-1] (if j > 0)

»
5 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

Best chineese contest i've ever seen

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

    As a general rule, no one solved H. But I still think the problems are perfect.

»
5 weeks ago, # |
  Vote: I like it +55 Vote: I do not like it

How can pretests be so weak that for problem D a solution which outputs the biggest distance between the furthest vertex, not the furthest special vertex pass pretests?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 6   Vote: I like it -19 Vote: I do not like it

    I was hacked by khokho with this same idea. Luckily for me, he gave me the opportunity to correct my code.

    EDIT: my corrected code didn't pass system tests. Damn it, I spent twice the time for less than worse results.

    EDIT: Why the downvotes?

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

nice 9th test on B just kills me.

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

    i think it's will be something like 2 1 1 or 4 2 2 2 2 or 7 5 5 5 5 5 5 6

»
5 weeks ago, # |
  Vote: I like it +46 Vote: I do not like it

How come tourist was able to hack on A...

Btw, I see only one FST among all 63 submissions in our room. What a smart room!

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

    You should try to be bad-at-luck like me, constantly jumping into rooms that nobody makes mistakes even other rooms are full of such people :D
    Also, nicely done hacking one D :D

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

    What is FST?

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

    aactually I have seen the code of problem A which tourist hacked . that fellow's code gives output 2 for input 6. here's the code https://codeforces.com/contest/1081/submission/47132351 and hacking that code is too easy for someone like Tourist!

»
5 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

Why I'm unable to see other's solutions?

»
5 weeks ago, # |
  Vote: I like it +43 Vote: I do not like it

Why can't I submit problems though systest is over? Submit button still redirects to same page with notification 'contest is over' .

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

How can I upsolve the problems of this contest?

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

    The problems should be able to submit by now. However, they're not at the top of the problemset, so be careful to find them.

»
5 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

Why am I not able to submit solutions even though the systests are over?

»
5 weeks ago, # |
Rev. 2   Vote: I like it +61 Vote: I do not like it

Imgur

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

why I faced problem while submitting ans of problem after contest ?

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

Anyone got an idea what was pretests 6 in E? Can't wait anymore

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

back to div2 it is

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

When the Editorial will be published ?

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

In problem C, can anyone explain meaning of this line "he found there are k bricks with a color different from the color of the brick on its left (the first brick is not counted, for sure)".

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

    If color[i] is the color of the i-th brick, then it's talking about the number of bricks such that

    color[i] != color[i-1].

    I agree that it could have been worded better.

»
5 weeks ago, # |
Rev. 5   Vote: I like it +5 Vote: I do not like it

https://codeforces.com/contest/1081/submission/47141835
My submission is O(n) but you can easily achive O(1) with factorial preprocessing for calculating nCr.
O(1) sol for C. 1). How many ways to divide n into k+1 segements. (x)
2). How mnay ways we can color k+1 segements such that no adjacent color is same. (y)
ans = x*y

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

    But thats O(n) solution.

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

      Mine is O(n) but with factorial preprocessing you can do nCr part in O(1).

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

many have crached task D on test 18, does anyone understand why?

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

    Taken such test for example:

    3 2 2
    1 2
    1 2 3
    2 3 4
    

    The answer should be 3, but since many solutions output the maximum weight of the MST of the entire graph (not just the subgraph including all special vertices), they outputted 4 and failed system tests.

»
5 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

I just want a T-shirt~QAQ

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

Problem D is so close to this one: The Child and Zoo

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

int s1=(b-a)/2;

For E, why do we need to divide the difference by2. Can someone provide a intuitive explanation for E? Thank u v m!

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Guys ! for problem D you also can use simple Dijkstra algorithm starting from any special vertex. The answer is the maximum of cost of all special vertex. check my solution. Using wrong comparator function was the reason i had to try submitting so often.