htoj's blog

By htoj, 3 months ago, In English,

Hi Codeforces!

Sorry for being late for the announcement.

I'm glad to introduce to you my first contest Codeforces Round #482 (Div. 2). It will take place on May/14/2018 17:35 (Moscow time).

You will have 5 problems and 2 hours to solve them.

The problems were prepared by me (Quyen Dinh), _Kuroni_ (Trung Dang) and _Shirone_ (Lam Le) with suggestions from FallingStar1709 (Nhat Hoang) and HaiDang2001VN (Dang Huynh). I would like to thank KAN for his great help in checking the problems and giving comments, Tommyr7 for testing all the problems and MikeMirzayanov for the awesome Codeforces and Polygon platform.

Note that the round is rated for everyone with rating below 2100.

In this contest, you will meet Kuro, Shiro and Katie, the three naughty but smart cats who love asking thought-provoking questions. I hope you will find our problems interesting. Good luck to you all!

UPD: Also big thanks to cyand1317 for helping us with the problems and arsor for translating the problems into Russian. Sorry, I forgot you guys.

UPD2: The scoring distribution is 500 — 1000 — 1250 — 1750 — 2250. Have fun!

UPD3: Congratulations to the winners!

Div. 1 & Div. 2:

  1. dotorya

  2. mama_budra

  3. coach.31

  4. nuip

  5. kevinsogo

Our top 5 solved all the problems. Awesome!

Official:

  1. mama_budra (solved all problems!)

  2. coach.31 (solved all problems!)

  3. Illidan

  4. ranwen

  5. iloveUtaha

Thanks for everything! Here is the editorial.

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

»
3 months ago, # |
  Vote: I like it -41 Vote: I do not like it

Div-2 the most popular format of Codeforces round.

  • »
    »
    3 months ago, # ^ |
    Rev. 3   Vote: I like it -56 Vote: I do not like it

    How did you know? Thanks for the information! You saved my day!

»
3 months ago, # |
  Vote: I like it -23 Vote: I do not like it

got inspirations from young problemsetter...hope for the best :D

»
3 months ago, # |
  Vote: I like it -24 Vote: I do not like it

A contest of Vietnamese :)

»
3 months ago, # |
Rev. 2   Vote: I like it -34 Vote: I do not like it

Although I have to study for the final exam, I am looking forward to join the contest because I want to increase my rating.

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

In my semester break...

50566205_unfaithful_homme_embrassant_sa_petite_amie_en_est_la_recherche_les_uns_les_autres_dans_la_rue

»
3 months ago, # |
  Vote: I like it -25 Vote: I do not like it

I think the round will be interesting and intriguing

»
3 months ago, # |
  Vote: I like it -24 Vote: I do not like it

Wow, This is the first time I saw the contest was prepared by Vietnamese people that are same my nationality. Hopefully, everyone will get a high rating.

»
3 months ago, # |
Rev. 2   Vote: I like it -34 Vote: I do not like it

Is It Rated?

»
3 months ago, # |
  Vote: I like it -15 Vote: I do not like it

Expecting a balanced contest....

»
3 months ago, # |
  Vote: I like it +16 Vote: I do not like it

... you will meet Kuro, Shiro and Katie

'Katie' is how felines call a special hue only visible to them, I suppose?

»
3 months ago, # |
  Vote: I like it -32 Vote: I do not like it

Thanks to the new rules! Now I can participate in div.2 contests!

Wish all Candidate Masters (and all participants) can get high rating!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow, Three cats are a hero to asking the question in this round.

»
3 months ago, # |
Rev. 3   Vote: I like it -14 Vote: I do not like it

‌‌

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

Wish u all low ratings like me :(

»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Me, currently, reloading room's page to find someone, I can hack in problem A

»
3 months ago, # |
  Vote: I like it +95 Vote: I do not like it

Candidate Masters These Days..

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

If you think cf pretests are shit, try to get past the pretest 5 of problem B !!!

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

    True Evil

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    please tell me the pretest 5 of problem B!

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

      It's for the case that one of them has a letter all over the string(like aaaaa) then there's only one turn... Amazing that many people passed this on the first try :/

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Why answer of this test is draw?

        3
        aaaaaaa
        aaaabcd
        abcdefg
        
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          aaaaaaa -> aaaaaab -> aaaaaac -> aaaaaaa
          aaaabcd -> aaaaacd -> aaaaaad -> aaaaaaa
          abcdefg -> aacdefg -> aaadefg -> aaaaefg

          1st guy and 2nd, both can win, hence draw

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got it wrong on pretest 10, don't know why.

»
3 months ago, # |
  Vote: I like it +488 Vote: I do not like it

Welp, the cats are smarter than me.

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

    D was trivial, chess is harder :)

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

    D problem was okay.

    but in all honesty . .

    If I ever see anyone playing a game like that , I will make sure they see meet their maker.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    LOL

»
3 months ago, # |
  Vote: I like it +136 Vote: I do not like it

u can fold up the pizza and cut it!i think this round should be unrated...

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Exactly! And keeping that in mind I tried for a hack with n=2 (3 pieces) for which 2 cuts are enough but it showed unsuccessful hacking attempt!

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

    The shape and size of the pizza slices are the same. Therefore no folds are required.

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

      Pizza with 3 slices of same shape and size can be created using 2 cuts if we fold the pizza by its diameter.

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

      u can cut pizza into 8 slices by cutting and folding 3 times

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

      when number of slices is even,one certainly can fold and get same shape

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

На Этот раз задачки были нормассс, правда не успел

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

Hack for B:
3
aaaa
aaab
bbbb
Answer is Draw.(My solution fails this test ;w;(I actually knew of this test but couldn't handle it correctly))

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you explain why answer is draw?

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

      aaaa — aaab — aaac — aaaa

      aaab — aaab — aaac — aaaa

      bbbb — bbba — bbbc — bbbb

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

    From

    aaab

    We can get bbbb obviously, so the score is 4.

    How can we get a score of 4 from the other ones?

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

      aaaa -> aaab -> aaac -> aaaa(second one is same as this one).

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

        Hmmm, from my understanding the letter has to be different than the one which was at the corresponding position at the original string (without any prior modifications). If I am correct, the expected output should not be Draw.

        "an arbitrary color which is different from the unchanged one"

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

          This rule applies only for current turn.

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

            While I enjoyed the other problems, the problem statement was confusing in this case. The word "unchanged" only has a meaning when the context is stated, which was not the case here.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      aaaa aaab aaac aaaa

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

bobo contest gay B suka

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve D?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't solve it completely but I think that segment tree storing divisors in each node + some additional data should work.

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

    My solution kept sets for each possible k, 1 through 100.000. When adding a number u to the array (type 1) I go through all divisors of u, adding that u to each of sets where it qualifies with O(sqrt(n)) complexity (and O(log(n)) for each insert into a set). If the u is already in the array, I don't do anything (not sure if this improves anything but thought it might be a useful optimalisation).

    Then, to answer a question for x, k, s, I check if k divides x with the Euclidean algorithm. If not, return -1, if yes, I check if the set for given k is non-empty and if it contains any number not greater than s-x. If so, I can start searching for the optimal solution within this set.

    When I know which set I'm using and what is the maximal number from this set I can use, I can search bit-by-bit for the best solution, checking for every j-th bit (beginning with the greatest ones) if there exist a number in the set that satisfies both following conditions: 1) Its first j bits are the same as desired (i.e. all different from the x's bits or the same for those which cannot be different, based on previous steps) 2) It's not greater than s-x This can be done in logarythmical time for each bit.

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

      Why do we need Euclidean's algorithm to check if k divides x? I thought mean k|v and k|x?

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

        Yeah, you're right xD I guess my brain stopped for a while.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    maybe it can be solved like this:

    construct a set which will store array values

    since k|gcd(x, v), if this possible then x = p * k and v = q * k,

    if x%k! = 0 then output is -1,

    else, iterate over values of , find in set if set, maximise zor to find answer

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

What should be answer of 3 bbbbaa ccccaa ddddde in B?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    bbbbaa -> bbbbba -> bbbbbc -> bbbbbb

    ccccaa -> ccccca -> cccccd -> cccccc

    ddddde -> dddddf -> ddddde -> dddddd

    so the answer will be "Draw".

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

3 aaaaaacc xxxxkkkk xxxxkkkk ans : Kuro

3 aaaaaa abcdxx abcdxx ans : Draw -> Kuro (Sorry My mistake)

1 aaaaaaAAAAAA aaaaAAAAAAAA aaAAAAAAAAAA ans : Katie

My B hack data!! Unfortunately, I realized I'm wrong after lock :(

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D. Why O(NMlog10^5) gets TLE where N = number of query1 and M = number of query2 ?

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

    For example, if N = 50000 and M = 50000, then N * M is a rather big number.

»
3 months ago, # |
  Vote: I like it +83 Vote: I do not like it

Fuck statement B, how could color segment means a single element!!!

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

    fuck all problems I think :|

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

    I think segment means the interval length >=1

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

      Yes, but not in problem B

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

        When I was hacked, the more I reading PB again, the more content I can't understand, what is "one color segment"'s real meaning......

»
3 months ago, # |
  Vote: I like it +12 Vote: I do not like it

hard to understand the statement in pD and pE :(

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

RIP rating. PS :- bad problem statements and wrong constraints (in C atleast)

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

whats wrong with this solution for B? https://ideone.com/Gbvho1 i just found the string with maximum frequency of a character.

»
3 months ago, # |
  Vote: I like it -26 Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Just a side note: In C, n >= 1 but n = 1 will not be possible according to constraints.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

3 aaaa aaab bbbb

Answer is Shiro right?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could't open the hack page for a long time up to end of the contest!

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

problem B, what is the answer for this test:

5

aa

aa

as

I tried to hack a solution with this test and the solution answer was "Draw" but I got "Unsuccessful hacking attempt" !!!

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it -7 Vote: I do not like it

    Edited

    Everone can make aa.

    aa->ab->aa->ab->ac->aa

    aa->ab->aa->ab->ac->aa

    as->aa->as->ab->ac->aa

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You use only 4 steps

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In my test n = 5, you are making only 4 moves

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's "Draw", right??

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

    you can do 3 steps and the sequence stay same, aa -> ad -> as -> aa

    This doesn't work only if you have to do 1 step

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

      Great, I think I don't have to wait System testing now -_-

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    1. aa -> ab -> ac -> ad -> ae -> aa

    2. aa -> ab -> ac -> ad -> ae -> aa

    3. as — > ab -> ac -> ad -> ae -> aa

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

Can someone explain why my hack with test is wrong: 3 aa bb ca. My solution gives "Katie" because of "Each move each of the friends must change exactly one section of the color in her tape to any other color chosen by her.". And solution that I tried to hack gives "Draw"

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

    aa->ab->ac->aa

    bb->bc->ba->bb

    ca->cc->ca->cc

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you very much. I think this test will help many people!)

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it's kinda obvious that this is "draw" because "aa" and "bb" are exactly the same strings and should give the same answer, so.

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

E: why n = 50 with n3 solution?

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

    Maybe they wanted to allow n4 solutions like mine!!

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

      n = 50 allows n5 solution to pass with small constant..

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

i really hate CF hacking system

a guy that luckily be the first one that could find trivial mistake made by 10 grey/green coder in his room could get more score than a hardworking coder that solve D in last 20 minute.

i think CF should limits the hacking attempt by a person (two or three hacking attempt for each problem)

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

    I would say that pretests in div.2 should cover such obvious (but still easy to miss) cases like n = 0 in task A because, yes, nobody should be able to get +1000 points in a couple of minutes by just typing 0 and clicking "Hack".

    But it doesn't feel right to limit the number of hacking attempts because even multiple hacks for the same problem may require you to read and understand various incorrect solutions and come up with unique testcases against each of them (today this was the case for me: I got 5 successful hacking attempts on problem B but I had to use 5 testcases slightly different from each other). These solutions can be relatively large and tough to understand, so I think that such challenges should be rewarded. After all, it's quite important to be able to read somebody else's code, to grasp the logic behind it and to find a counter example if the underlying logic is wrong. If you want to get a bunch of hacks on harder problems, you will have to sacrifice the time that you could have spent solving other problems (with no reward, i.e. successful hacks, guaranteed), so it's about time/risk management as well.

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

      agreed with you. pretest must cover trivial test case so it won't create unfair advantage to the hacker

      what is the purpose of the problemsetter by not covering trivial case such as n = 0? anyone know that this type of cases will produce lot of unfair hack.

      unfortunately, there are a lot of contest that did not cover obvious test cases. it is really unfair for people that solved ABCD but lost to a hacker that solve ABC.

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

    i think CF should have a hacking point for every problems :)

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

    Even people who haven't solved any problem, and hacked as much as 10 codes in problem A are way ahead in standing than those who have solved even a single problem!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think In solving problem D I was going in the right direction , whenever query of type 1 happens , find all its divisors and then make a trie for all those divisors in which we add the binary representation of the number v , but later read the problem statement correctly and found another condition that v + xi <= si . . now no idea how to solve this further keeping this condition in mind :'(. .

How did you people solve problem D , i think I was kinda going in the right direction

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

    I didn't solve it. But my idea : save array as two dimension bool bit[512][512].

    1) add u to array: bit[ u >> 9][ u & 511 ] = true;

    2) find answer for x, k, s : 2.1) find that 0 <= ID < 512 that , x ^ (ID << 9) maximal. 2.2) for that ID go all 512 elements of ID's sub array.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes you were. when you are searching the trie, keep in mind that the number you are searching (v) is <= si — xi, and you can verify this relation bitwise

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your thought process is correct. Let's assume we have BSTs instead of tries. Split the BST in two parts: (elements <= s — x) and (elements > s — x). Solve 706D - Vasiliy's Multiset on the first part. This takes time. (Note: Since a trie is essentially equivalent to a BST, I think this can also be done in O(logn) time, but I'm not sure how to implement this.)

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

    You mean 01-trie, right? It's a way, but yes, it can't handle the condition : v + xi <= si

    Instead, I used std::set in c++, which is more convenient.

    And you can use the lower_bound function to find the minimal value, And you can solve the problem.


    If you give every node in 01-trie min[] value, you can also solve the condition.

    min[node] means the minimal value in the subtree of the node(if you know what I mean).

    If min[node] + xi > si, the subtree of node will not have any v that satisfy the conditions.

    Sorry, my English is poor. Hope you'll understand me.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I get what you are trying to say but all this did not come to my mind immediately , I just started coding what came to my mind in 5 minutes without even reading carefully , was frustrated because of B , but now that I know my approach was ALMOST correct , I am happy ,

      as ajecc said above , I just have to add very few lines in my 01 trie searching to ensure the condition v <= s — x , . . I can rest in peace now , the contest was a disaster

»
3 months ago, # |
  Vote: I like it +20 Vote: I do not like it

the problem is shit!!!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My honest respect to contest coordinators, setters, testers and to all who worked so hard to arrange this contest. But the contest experience was not good. Lagging from the start, could not submit test case for hacking purpose at the last 10 minutes of the contest. And when I finally submitted the test case before one minute it successfully uploaded but the status keeps loading and loading, even till now. Such an worst experience for me. Maybe it was not my day.

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

I can just hack others to get points in this contest.

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

I suddenly realize in Problem B we have to change per string for exactly n times. No less, no more.Crying...

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D? Some kind of divisors search?

»
3 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Not the best contest =/

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

Can anyone describe how to solve 979B - Treasure Hunt? Thanks!

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I suppose next. Find letter with maximum M appearances (using map for example). It's Beauty before. One can change N letters in the ribbon. So one can increase M with N. But sum should be not bigger than ribbon length. Let T = min(M + N, ribbon length). Special case is M = ribbon length and N = 1, here one have to change letter to another and T = M - 1. Finally, compare T for men.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Holy sh*t I thought that one letter only could be changed to its subsequent on the alphabet. Read over and over again the problem statements guys!

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I lack of special case, probably it 's pretest 5.

»
3 months ago, # |
  Vote: I like it -63 Vote: I do not like it

I had a serious discussion with Mike, I have decided that this contest is made unrated

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Lets make this the most down voted comment

»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

problem B???? what are you saying???

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

Awesome contest, would be much better without hacks :D.

»
3 months ago, # |
  Vote: I like it +50 Vote: I do not like it

Just my thoughts.

For problem A, you could make statement more clear, that two best friends baffled me as n can be 0 or 1. Also this sentence — 'A cut is a straight segment, it might have ends inside or outside the pizza.'. I don't know if I'm only, but it took me some minutes to understand this. I think the word 'outside' here is not needed, it confuses. Or you could give a picture for making everything clear.

I hated problem B. Statement is really bad written. For example, look here: 'For example, the ribbon aaaaaaa has the beauty of 7 because its subribbon a appears 7 times, and the ribbon abcdabc has the beauty of 2 because its subribbon abc appears twice.'. You should clarify what does 'appear' mean here. Also 'one color segment' is really confusing...

»
3 months ago, # |
  Vote: I like it +35 Vote: I do not like it

Unbelievable. I've solved all and have only 300-points advantage concerning the guy who has only solved ABC. I think it isn't fair system, when I can lose the guy who have guessed to hack with the very easy trick, whereas he hasn't solved anything what I even though may try to call "problem", and not "exercise for blue coders".

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

Another hacking contest

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

why did you change the statements of problem B without an announcement?

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

    Could you give more information, please? I didn't notice that.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      They changed If there are at least two cats that share the beauty, print "Draw". to If there are at least two cats that share the maximum beauty, print "Draw". without any notification.

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

        Actually you can't even pass sample test 2 if you follow the original instruction. So I think most people can guess what it really means.

»
3 months ago, # |
  Vote: I like it +7 Vote: I do not like it

why in problem C n can be equal 1???

»
3 months ago, # |
  Vote: I like it +71 Vote: I do not like it

Codeforces is like:

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

single line of mis-coding leads me to WA on C and I couldn't never fix it until the end of the contest.

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

As problem setters, we intended B to be a problem where people may think a bit out of the box (dealing with odd turns). But we made some serious mistakes (unclear statements, bad pretests) and I would like to apologize to all of the participants this contest. We are currently having a discussion about the aftermath of this contest.

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

    Although I did the contest badly, overall problems are good. But it's also true there's some mistakes on statements :'(

»
3 months ago, # |
  Vote: I like it +96 Vote: I do not like it

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

    Thanos : Half of submissions of problem B would cease to exists (snap) just like that.

»
3 months ago, # |
  Vote: I like it +55 Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +11 Vote: I do not like it

I think the statements are open to different interpretations.

That leads to lots of hacks and unhappy participants.

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

No one realizes the case where

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

    When you want to hack because you know people will forget about this case...

    ... but you don't know how to hack.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

but there's one thing...

there's one thing...

it's wrong contest to judge with :)

»
3 months ago, # |
  Vote: I like it +13 Vote: I do not like it

No need to make it unrated.Keep it rated. Problem statements were fine. Many people solved the questions so i dont have any complaints

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    upvoters : did contest with good score

    downvoters : the others

    fight of the most subjective voters

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

    The statements weren't fine. Yes, the author's intended solution is to run back and forth between a->b->a. That's what the sample test case description says. Those who understood this way will be judged correct. But there's no problem at all to use a->b->c->a (or a loop longer than 3) under the given description.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What should be the answer of this test?

2 aabc aaab aaac

I believe that is Kuro, but I'm already confused because so many people's code print "Draw".

»
3 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Maybe CodeForces should disable hacks in Div.2 Only contests. Some experienced and high-rated (not me :P) candidate masters are solving problems, while others are obsessed with hacks. Inasmuch as there can be a lot of hacks, we obviously see that people solved 2 problems gets a higher rank that contestants solved 3, even 4 problems. There are three options. Make pretests strong so in the contest, it takes less time for the testing solution, and disable hacks. Make the contest full-feedback. Make 12/24 hours hacking phase after the contest. Thanks for reading!

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

    Actually there is one more idea. Someone mentioned above somewhere in comments, I felt it was nice. Limit the number of hacks to 3 per question per person.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -27 Vote: I do not like it

    So you can start hacking too. No one is forcing you not to hack. Debugging is also an important asset to have

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

      except that hunting for one if statement is not really debuging

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

      But the motive of contest should not disturbed. Also does it seem good that hacking forms important part than solving. In that way coding clean code for A is important than solving(Or rather attempting) rest??

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

      I also hacked some solutions and understand you that because of your skill is not good enough (do not get offensed from that, I'm just saying it to clarify my idea) you prefer hacking than solving further problems. Thinking on that problems would be better practice, at least it worked for me when I was less skilled.

      Also don't you think getting points with hacks depends on luck?

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

      spamming "0" to 10 coder that make such trivial mistake isn't called as debugging.

      Also, how do you feel when you solved D in the last 20 minute with all complicated code but there are 30 users that don't even attempt to read problem D and get higher score than yourself caused they spammed "0" 10 times.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    http://codeforces.com/blog/entry/59431?#comment-430573

    i thought disabling hacks won't be a solution. in my opinion, limiting hack attempt or covering obvious test is way better.

    there are some coder that seriously debugging other ppl code. but what i saw from this contest, most of the people just spamming 0 and click "hack" to get a free 1000 point because no one have started hacking in their room.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please don't tell me the intended complexity for D is O(Q * 128 * log2(105)) (128 = largest number of divisors of numbers from 1 to 10^5).

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you are right for the complexity

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

Why my solution 38219517 was Runtime error on test 29 for A?
Can you check them please?

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

    return !puts("0"); Your solution returns exit code 1 on n=0.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Don't know why downvotes for my previous comment, but puts returns a non-negative value (on success). In your case puts returns 0 and your code makes return !0, i.e. return 1. Any non-zero exit code from the main process of a solution is treated as a runtime error.

»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

If you fold the pizza it takes less cuts

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

For C, can an input have n = 1 ? If n == 1 then x and y can not be distinct. But the range for n starts from 1 :P

»
3 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Came across one strange detail while viewing results for my room. The problem is said to be locked one second after it was hacked: https://pasteboard.co/HlaAgFu.png. We can't lock the problem if it doesn't have "pretests passed" status when we click "Lock", can we?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I hope he is able to resubmit after that hack and not hack others xD

»
3 months ago, # |
  Vote: I like it +30 Vote: I do not like it

Brute AC on D: 38234986.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

you can use sigma(n/k)*q to solve D,so interesting

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

When I read the problems, I misread a part of problem D's statement. I understood that and not . How to solve that version of the problem?

PS: I have a solution, which is a bit complicated (not too complicated, but still) so any solution you can think of will be appreciated.

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Jonny, they are in the trees!!!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is test 27 in C?

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve this generalization of the problem C:

Given an undirected graph with n nodes and m edges. How many are (u, v) pairs such that there exists a shortest path from u to v that it doesn't visit y if it visited x before? x and y are given.

»
3 months ago, # |
  Vote: I like it +17 Vote: I do not like it

http://codeforces.com/contest/979/submission/38243030

AC on D with O(n^2) and simple cutting..

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Wow! Problem B was a devastation! So many people (me included!) got it wrong on system tests!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone point out why my solution to C fails? Link

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problems, Thanks!

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

Can anyone tell me why LINK is wrong for C?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C TLE. Is this 38236023 not O(n)? Poor python coder!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This solution for problem C yields MLE -> LINK

Please help.

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

    Because of passing vectors and arrays to recursive functions.

    So, you should declare those structures as global structures, to be able to use them without passing them to the functions

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

    I have just looked at your newest submission.

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

      Thanks for keeping a constant check.

      I would never have thought of these optimizations.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Welcome to HackForces! I think letting the round rated for everyone with rating below 2100 is a wrong decision.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If they don't hack you then you are wrong anyway bruh.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I just think "DIV2 only" round is not suitable for purple players.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        And fewer people will take DIV1 round.

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain what main test 79 in problem B was. Since the test case is too big, any alternate small test case with same logic?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I've tried the case

    3 aaaa aaab bbbb

    => Draw

    from an earlier reply which works like aaaa -> aaab -> aaac -> aaaa instead of a->b->a->b

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Got the error ! My answer to this case is Shiro ! Thanks a lot.

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

Why dose this solution (which is O(n^2)) get passed..

http://codeforces.com/problemset/submission/979/38236267

This generator can hack it..

#include<bits/stdc++.h>
using namespace std;
int main(){
	int q=100000;
	printf("%d\n",q);
	printf("1 1\n");
	for(int i=1;i<q;i++)printf("2 1 1 100000\n");
	return 0;
}
»
3 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I would like to point out the test cases of D is too weak. It seems to me most of the cases are random cases and does not target for a specific range of values.

My solution is to use trie for ki <= 400 queries (build a trie for each ki), otherwise, use O(n*si/ki) brute force. 38238355

I tried to mess around the constant 400 to see if a faster runtime will be achieved. And I accidentally found that using a single trie to handle queries of ki = 1 and brute force all other ki >= 2 queries can pass all tests. 38260678 I believe brute force solution for ki = 2 should result in TLE like ki = 1. Consider the brute force part alone, ki = 1 should run about half speed when ki = 2. However, my solution pass with 249ms which is unexpectedly low.

Also, it is reported that some O(n^2) brute force solutions with cutting can easily get accepted. See:

I hope the problem authors can investigate this issue and make stronger cases for future rounds. Nevertheless, I enjoyed solving this problem. :)

Note: My pure brute force solution TLE on 14 38260748

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry for the weak test cases of problem D. We did not think much about brute force solutions with optimization so the test cases were not tough enough. We will absolutely make progress next time. Thanks for pointing it out.

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

Why am I getting TLE for O(n) solution in Java ? (problem C) http://codeforces.com/contest/979/submission/38266793

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    get(int) method of LinkedList is . You should use ArrayList or similar instead.

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

      Yeah! :D I almost forgot this. I can use ArrayList instead.. Thanks alot.

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

s