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

Автор htoj, 11 дней назад, По-английски,

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.

 
 
 
 
  • Проголосовать: нравится  
  • +91
  • Проголосовать: не нравится  

»
11 дней назад, # |
  Проголосовать: нравится -41 Проголосовать: не нравится

Div-2 the most popular format of Codeforces round.

»
11 дней назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

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

»
11 дней назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

A contest of Vietnamese :)

»
11 дней назад, # |
Rev. 2   Проголосовать: нравится -34 Проголосовать: не нравится

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

»
11 дней назад, # |
Rev. 2   Проголосовать: нравится +82 Проголосовать: не нравится

In my semester break...

50566205_unfaithful_homme_embrassant_sa_petite_amie_en_est_la_recherche_les_uns_les_autres_dans_la_rue

»
11 дней назад, # |
  Проголосовать: нравится -25 Проголосовать: не нравится

I think the round will be interesting and intriguing

»
11 дней назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

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.

»
11 дней назад, # |
Rev. 2   Проголосовать: нравится -34 Проголосовать: не нравится

Is It Rated?

»
11 дней назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

Expecting a balanced contest....

»
10 дней назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

... you will meet Kuro, Shiro and Katie

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

»
10 дней назад, # |
  Проголосовать: нравится -32 Проголосовать: не нравится

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

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

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

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

»
10 дней назад, # |
Rev. 3   Проголосовать: нравится -14 Проголосовать: не нравится

‌‌

»
10 дней назад, # |
Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

Wish u all low ratings like me :(

»
10 дней назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
10 дней назад, # |
  Проголосовать: нравится -50 Проголосовать: не нравится
Комментарий удален по причине нарушения правил Codeforces
»
10 дней назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится
Комментарий удален по причине нарушения правил Codeforces
»
10 дней назад, # |
Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

кекс

»
10 дней назад, # |
  Проголосовать: нравится +95 Проголосовать: не нравится

Candidate Masters These Days..

»
10 дней назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

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

    True Evil

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

    please tell me the pretest 5 of problem B!

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

      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 :/

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

        Why answer of this test is draw?

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

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

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

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

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

»
10 дней назад, # |
  Проголосовать: нравится +488 Проголосовать: не нравится

Welp, the cats are smarter than me.

»
10 дней назад, # |
  Проголосовать: нравится +136 Проголосовать: не нравится

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

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

    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!

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

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

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

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

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

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

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

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

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

задания В упадет у многих ,я так считаю. напр тест n=3 aaabb aaaaa bbbbb отв 1

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

    нет, не один, тк второй делает aaaaa->aaaac->aaaad->aaaaa, третий так же. Найс задачи

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

    задача А тоже упала у многих) хд long long

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

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

»
10 дней назад, # |
Rev. 6   Проголосовать: нравится +33 Проголосовать: не нравится

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))

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

    can you explain why answer is draw?

    • »
      »
      »
      10 дней назад, # ^ |
      Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

      aaaa — aaab — aaac — aaaa

      aaab — aaab — aaac — aaaa

      bbbb — bbba — bbbc — bbbb

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

    From

    aaab

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

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

    • »
      »
      »
      10 дней назад, # ^ |
      Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

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

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

        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"

        • »
          »
          »
          »
          »
          10 дней назад, # ^ |
          Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

          This rule applies only for current turn.

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

            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.

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

      aaaa aaab aaac aaaa

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

bobo contest gay B suka

»
10 дней назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to solve D?

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

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

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

    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.

  • »
    »
    10 дней назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится

    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

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

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

»
10 дней назад, # |
  Проголосовать: нравится +79 Проголосовать: не нравится

Ну все, теперь-то, когда контест закончился, точно можно (http://codeforces.com/blog/entry/59431?locale=ru#comment-430511)

Задача D — худшая задача на моей памяти в истории спортивного программирования. Давайте я ее переведу на нормальный язык:

Изначально дан пустой массив a. Игр состоит из q запросов двух разных типов. Запросы первого типа просят Кэти добавить число ui в массив a. Запросы второго типа просят Кэти найти такое число v, принадлежащее массиву a, что (выполняется х**ня 1), (выполняется х**ня 2), и (х**ня 3) максимальна, или же вывести -1, если таких чисел в массиве нет.

Координаторы, вам серьезно нравилась эта задача? Может, пора более ответственно подходить к своей работе?

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

    Мне кажется, ki | GCD(xi, v) — самая забавная вещь в этой задаче. Это примерно если бы вместо a + b попросили найти GCD(a2 + a, a2) + ln(ab) / ln(a)

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

    А в чём проблема с этой задачей? Вас в каждой пятой просят найти что-то, обладающее сразу несколькими свойствами, так почему, если эти свойства даны в условии, а не выведены на листочке аккуратно, то задача сразу становится "худшей"? К тому же вы всё же забываете, что это второй дивизион, для первого там была, судя по монитору, задача Е.

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

      А не под фейком слабо то же самое написать?

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

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 :(

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

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

»
10 дней назад, # |
  Проголосовать: нравится +83 Проголосовать: не нравится

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

»
10 дней назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

hard to understand the statement in pD and pE :(

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

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

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

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

»
10 дней назад, # |
  Проголосовать: нравится -26 Проголосовать: не нравится

»
10 дней назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

del

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

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

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

3 aaaa aaab bbbb

Answer is Shiro right?

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

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

»
10 дней назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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" !!!

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

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"

»
10 дней назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

E: why n = 50 with n3 solution?

»
10 дней назад, # |
Rev. 2   Проголосовать: нравится +138 Проголосовать: не нравится

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)

  • »
    »
    10 дней назад, # ^ |
    Rev. 2   Проголосовать: нравится +32 Проголосовать: не нравится

    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.

    • »
      »
      »
      10 дней назад, # ^ |
      Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

      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.

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

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

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

    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!

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

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

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

    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.

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

    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

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

    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.)

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

    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.

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

      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

»
10 дней назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

the problem is shit!!!

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

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.

»
10 дней назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

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

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

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

How to solve D? Some kind of divisors search?

»
10 дней назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Not the best contest =/

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

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

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

    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.

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

      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!

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

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

»
10 дней назад, # |
  Проголосовать: нравится -63 Проголосовать: не нравится

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

»
10 дней назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

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

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

»
10 дней назад, # |
  Проголосовать: нравится +50 Проголосовать: не нравится

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...

»
10 дней назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

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".

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

Another hacking contest

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

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

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

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

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

      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.

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

        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.

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

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

»
10 дней назад, # |
  Проголосовать: нравится +71 Проголосовать: не нравится

Codeforces is like:

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

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

»
10 дней назад, # |
Rev. 2   Проголосовать: нравится +59 Проголосовать: не нравится

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.

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

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

»
10 дней назад, # |
  Проголосовать: нравится +96 Проголосовать: не нравится

»
10 дней назад, # |
  Проголосовать: нравится +55 Проголосовать: не нравится

»
10 дней назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

I think the statements are open to different interpretations.

That leads to lots of hacks and unhappy participants.

»
10 дней назад, # |
Rev. 2   Проголосовать: нравится +51 Проголосовать: не нравится

No one realizes the case where

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

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

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

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

but there's one thing...

there's one thing...

it's wrong contest to judge with :)

»
10 дней назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

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

    upvoters : did contest with good score

    downvoters : the others

    fight of the most subjective voters

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

    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.

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

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".

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

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!

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

    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.

  • »
    »
    10 дней назад, # ^ |
      Проголосовать: нравится -27 Проголосовать: не нравится

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

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

      except that hunting for one if statement is not really debuging

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

      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??

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

      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?

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

      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.

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

    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.

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

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).

»
10 дней назад, # |
Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

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

»
10 дней назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

If you fold the pizza it takes less cuts

»
10 дней назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
10 дней назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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?

»
10 дней назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

Brute AC on D: 38234986.

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

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

»
10 дней назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

»
10 дней назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Jonny, they are in the trees!!!

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

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

What is test 27 in C?

»
10 дней назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

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

Всю жизнь писал рекурсивный Dfs и прекрасно работало. Тут вдруг упало со StackOverflow. Помогает увеличение памяти стека потока. Реально, проклятый контест какой-то...

»
10 дней назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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

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

»
10 дней назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

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

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

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

Nice problems, Thanks!

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

Can anyone tell me why LINK is wrong for C?

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

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

»
10 дней назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Как по мне, не очень хорошо в задаче A писать, что Кэти и Широ ЕЩЁ не пришли, и давать (позволять) тест n=0.

И вообще раунд плоховат в плане вычитки условий.

Тем не менее, спасибо. Делать всегда труднее, чем критиковать...

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

This solution for problem C yields MLE -> LINK

Please help.

  • »
    »
    10 дней назад, # ^ |
    Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

    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

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

    I have just looked at your newest submission.

    Spoiler
»
10 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 дней назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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?

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

    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

»
10 дней назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

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;
}
»
10 дней назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

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

    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.

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

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

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

s