Автор vovuh, 6 лет назад, По-русски

Привет, Codeforces!

12 декабря в 18:05 по Москве начнётся Educational Codeforces Round 34.

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд снова будет рейтинговым для Div. 2. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в один день, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной готовили Михаил awoo Пикляев и Иван BledDest Андросов.

Удачи в раунде! Успешных решений!

У меня также есть сообщение от наших партнёров, Harbour.Space University:

Информация об обучении

Мы предлагаем записаться на курсы по одной из трёх наших программ, связанных с IT: Data Science, Computer Science и Cyber Securityзаполните форму для того, чтобы принять участие в программе, начинающейся в январе или в сентябре 2018 года. Мы свяжемся с вами вскоре после заполнения формы. Надеемся увидеть вас среди участников наших курсов!

Перейти к форме

Поздравляем победителей:

Rank Competitor Problems Solved Penalty
1 dotorya 6 209
2 JustasK 6 228
3 dreamoon_love_AA 6 248
4 ivan100sic 6 273
5 Shayan 6 308

Поздравляем лучших взломщиков:

Rank Competitor Hack Count
1 Artmat 109:-9
2 gigabuffoon 81:-1
3 ssor96 61:-1
4 Danylo99 61:-8
5 AkiLotus 63:-18

Было сделано 1528 успешных и 786 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Problem Competitor Penalty
A AkiLotus 0:01
B MrDindows 0:04
C Kitorp 0:02
D mdippel 0:20
E dotorya 0:27
F step_by_step 0:38
G dotorya 1:03

UPD Разбор

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

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

Rated round again with lots of problem :) .Hope good rating to all

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

I hope that the statements will be as short as those from last div2 and as interesting

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

Thanks for another rating round for div2 :)

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

Hope the queue is fixed.

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

Since registration opened before the previous contest's rating changes, this bug happened again. Will this guy be rated?

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

really rated again??? I just Love CodeForces

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

How do these help educate differently to normal contests? is there solution descriptions afterwards or something?

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

    Well these rounds were unrated before and thus were 'educational'. You could participate without your ratings being changed and learn from the contest. (How to attempt the real Div contests or learn to hack etc). Or its just a fancy name for it anyways it looks like they'll be rated now which isn't too bad too :P. But I'd rather know how the ratings change for these contests as last time there was a lot of confusion.

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

Unrated educational rounds please!

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

I hope the computation speed of the evaluation system could faster.

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

a chance to recover from yesterday

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

WasylF, Can you fix it so that the predictor will work well for the Educational rounds?

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

    Yeah, I suppose it's not very complicated & I'll fix it for the next educational round. BTW, it is a bit weird that div 1 participants doesn't marked as "unofficial" like always in div2 only rounds.

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

A fast queue plz.

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

There will be any points on hacking?``

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

You said it is rated for Div 2. But is it rated for Div 1???????

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

How Div. 2 participants of this educational round will be sorted in "Standings"?
Is there the algorithm description available?

I tried the related (New: Educational Rounds on Codeforces!] blog post but I failed to find this information there.

My guess (based on the Educational Codeforces Round 33 results):

  • First, sorted by = (the number of problems solved), descending.
  • Second, sorted by Penalty, ascending.
  • Penalty is the sum of penalties for each problem.
  • Penalty for a problem is the sum of:
    • the number of minutes after beginning of the round when the last successful submit was sent;
    • penalty for additional submissions (20 minutes for each).

Is this information available somewhere?
What am I missing?

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

    Ranking is exactly as per ACM rules. You've got it right except for the penalty part

    User's penalty: sum of penalty of all 'accepted' problems

    Penalty of an accepted problem: Time taken to get the problem accepted + 20 mins penalty for each wrong submission

    You can check ACM style ranklist rules here

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

      Thank you very much!
      A subtle point is still this one:

      + 20 mins penalty for each wrong submission

      As I understood,

      • there is no penalty for re-submit (several Accepted solutions from one participant for one problem),
      • of multiple Accepted solutions the earliest one counts, the others are not considered.
      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        I believe submissions only till the first accepted solution is considered when calculating penalties. Actually in an ACM styled contest, submission verdicts are generally final, if you get an AC then it is indeed AC, and does not change later on. Since it's not the case here, I believe it is as you say, and if a previously correct solution is hacked, penalty is changed to reflect the next correct solution (maybe, not so sure on this one)

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

I hope every girl will downvote this :(

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

Why you don't made div-1 participants out of competition like normal div-2 contests ?

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

CF rated rounds are just like addiction.. If you try it once,you would want them again and again and even more frequently.

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

Rating baadme surakshit hogi pahle Codeforces Servers surakshit karwao :p

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

That moment you know you are fucked up and you also know everyone is fucked up.

image

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

I literally spent 41 minutes to do this
int->long long in exactly one place -_-
I guess I can't trust my own template

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

В задаче D надо было использовать длинную арифметику?

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

exclude the ans > 10^18 tests maybe?

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

We're extremely sorry for requiring BigIntegers in D, we didn't really mean it firstly. Neither authors, nor testers pointed this bug to us. :(

We would like to apologize for that. I hope codeforces will be able to process all the hacks...

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

    Will you consider the test cases for which answer exceeds 10^18?

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

    Now plz don't say u won't consider >10^18 because some people who were in middle of 5th problem had to leave that problem, learn new language and code into it (java in my case).

    If u announced it in the contest, kindly use that only.

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

    Does apologies make any sense?

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

      Doesn't it? I don't believe this is fine for contest in 2017. It would be ok in the beginning of 2000's but not now for sure.

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

    Will it fit in unsigned long long ??

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

      I don't think so. And it can be negative.

      Well, I was mistaken. ull is fine since the answer is up to 10^19 and not 10^20.

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

        I took care of -ve values I need to know if |ans| fits in ull

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

          Answer can be up to 10^20 in absolute value.

          Ok, sorry, I definitely miscalced this, should be 10^19

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

            OK

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

            33184706 so far nobody could come up with such a test case it seems, so will there be more tests by you after the hacking phase? (or is the final test just pretest + hacks?)

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

            In my opinion, max test is that first half is 1 and the second half is 10^9 It will overflow long long, but not unsigned ll I have changed long long to unsigned ll. And I got accepted :)

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

    I don't think you really need to excuse. It is a practical educational point here. I think it is a good skill to estimate max answer and use proper types/methods. Such things happen and it is better to meet them on educational round than any other official contest.

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

      Yeah but it is rated for div2 and c++ users need bigint and thus nearly eliminates a language.

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

        In innumerable number of problems С++ has the advantage. It is OK to have rare problems on Educational Rounds showing the other side. Also it's a good skill to be able to choose the appropriate language for programming depending on the task.

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

          It is very unfair for the beginners who can't write else c++ !! what is the purpose of problem else to impossible the beginners for not trying for solve !! I think there are a lot of us who are very very angry and ask you to edit the test cases to not exceed 10^18 .

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

            I'm sure beginners weren't able to solve F either, but we're not getting rid of F because they don't know how to.

            There's nothing in the problem statements that limited the answer to < 10^18. Figuring out the bounds of your solution and using appropriate data types (and they even told you that the answer was not limited to 10^18) is part of problem solving.

            Of course you don't know how to do everything at first, but after seeing it once, a beginner can learn and might be able to do it next time.

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

              Of curse it is very good to know but I think in rated contests you should avoid the differences like this

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

                Rated contests are meant to be a measure for the contestant. In my opinion, it actually tests our knowledge about answer interval and data type. Pascal doesnt have a sort built-in function, but you can make one. C++ doesnt have bigInt data type, but you can make one.

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

        You could use:

        1) long double (64 bit precision is enough)
        2) unsigned int64_t for sum of positive and negative elements
        3) two int64_t values

        It is really not difficult to use any of these techniques.

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

      I think it's unfair for beginners, especially people who only know C++

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

    so if it was not intended, Why can't you just edit the tests?

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

      It was intended by problem statement, and it's bad idea to edit problem statement after the contest end.

  • »
    »
    6 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится -8 Проголосовать: не нравится

    I used int64_t in D still Hacked! :(

    update: fixed it!

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

    i think it can be solved using unsigned long long the worst answer can go up to |1019| you just need to handle that carefully : 33192580

    also i would like to ask does the judge solution use big integers?

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

Did need a BigInteger in the problem D?

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

When I'll be able to submit code if I didn't participate in the contest?

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

Should we talk about solutions in this phase (hacking) ? Because I have idea for D so I just wanted to ask if anyone solved it that way.

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

Hello :D

Can someone see my code in problem E and tell me why am I getting TLE ?

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

Nice problems, I really enjoyed the contest.

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

How to solve E ???

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится
    1. the frequencies of every character must be the same in all strings.

    2. calculate the hamming distance between the first string with all other strings.

    3. for every swap (i,j) of characters of the first string, calculate the new hamming distances. If all distances are less than or equal than 2, then swapping (i,j) in the first string gives the answer.

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

      How can we prove this always works?

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

        What is the complexity ???

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

        The string that we are finding can be obtained by swapping exactly two characters of the first string. So we are brute-forcing all possibilities. If we swap two characters the resulting string will be different in at most two positions. Complexity is O(n^2*k)

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

      What should be the output for the case : 2 2 aa aa

      I think it should be -1 because in the question it's mentioned they have different indices but here you can swap only (1, 2), so in the next string there's nothing left to swap ?

      Am I missing something ?

      UPDATE I think I misunderstood the question :(. That's why I was failing test case 4 :(

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

      Also if you swap some characters (i,j) and the new hamming distance for some string is 0, there needs to be a duplicate character somewhere in all strings for that pair to work.

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

      Does it work for this test case ?
      2 3 abc acb

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

      If you make a swap then at most two or at least 0 character will change its position (if the swapping characters are same). So for the hamming distance 1 ans should be -1.

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

      How do you calculate the new hamming distances ?

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

I'm sorry, I made a mistake. How to write a 65-bit signed integer?

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

It isn't guaranteed that the answer doesn't exceed 10^18 by absolute value.

You didn't know that before the beginning of the contest, right ? :D

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

Well, nice troll for D :D

BUT, NO PANIC! max answer is 2666666666600000 which fits long long. RIP who resubmitted

I got this value with greedy test case, but I see hacks, not sure T_T

Seems like answer fits in long long but we should do — operations first, still not sure.

OK GUYS! SAY GOODBYE TO YOUR RATINGS AND GO TO SLEEP. WE ARE FUCKED UP :(

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

Ох сейчас взломы по D полетят

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

How to solve D??? :(

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

I just read the clarification about D :(

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

I thought i had solved D with this alghorithm,but it failed on first test.It was right on sample cases too.Whats the problem with this?

First,i thought threre were no rules at all,for every i<=j you increment your answer by a[j]-a[i].You compute beforehand how many times you add and subtract one element,so you can get answer for no rules in O(n)

We now have to think about rules.They only say that for any a[i] you have to consider a[i]-1, a[i] and a[i]+1 values beforehand.Their counts are important here,so we have to store them in a place.Arrays arent suitable since a[i] can go up to 10^9 so i used multiset and even map to update their counts as i iterated through the values.

Even after the warning i used long long values.They could overflow in C++ as maximum ans could be 10^5*10^5*10^9 for an input consisting half zeros and 10^9s after

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

Hack for D?

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

why you are so bad in problem D ? why long long in c++ isn't enough for you ?

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

lmao that D

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

I just realized that problem E had a O(nk) solution, but isn't O(n2k) supposed to get AC as well?

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

Hints for E please.

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

    maybe dynamic programming with bitmask

    UPD: i mean about problem F sorry

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

    First of all frequency of all the strings should be same. Then imagine your initial ans is the first given string. Now generate all the possible strings by swapping two characters of that string. Now you have to calculate the hamming distance with all other strings.If the calculated hamming distance for all the given string is 2 or 0(if there is a duplicate character) then you got your ans.

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

A language-dependent problem in a rated contest, sounds ridiculous tbh.

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

    Well, you can write bigints in c++, moreover you only need addition and printing

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

    but its not fair that C++ waste more time to write big integer while jave only define it

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

      Same with next_permutation. It's not fair that cpp gets it handed to them while Java coders need to waste time to define it.

      Or with cpp's speed. It's not fair that cpp is many times faster than Python. Python coders can write more optimized algorithms that still end up running slower than cpp code.

      Languages are different. You have the choice of picking one that suits your needs or learning to do things not natively supported in your language.

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

        Java and python have higher speed(time) limits

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

          He's also talking about implementation time not running time. As in next_permutation that is implemented in C++ but not in Java.

          And also: Sometimes, with the same solution, Python gets TLE and C++ doenst.

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

          Do you mind sourcing that? I didn't know that CF did that.

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

            Every website does it. Try submitting a TLE (infinite loop) solution to a question in both c++ and python/java to see it.

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

              I really dislike anecdotal evidence.

              You can see the time limit at the top of every cf problem, and that's given before you choose what language you're submitting in, so it should be the same for all languages.

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

    All contests are language-dependent... A lot of times the same solution implemented in Python gives TLE while solutions in C++ don't... Is that unfair too for you? Or that next_permutation exists in c++ but not in java. Is that unfair when a contest requires it?

    I think you all have the conception c++ is the best in everything but it has its limitations too obviously... You are a good coder if you know them and can adapt. Congratulations to all who solved D. If you didn't better luck next time. Keep improving everyone!

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

Yo , please make it unrated dudes, i solved D at the same time as C and B and it so correct but because of the fact that you wrote unclear only about 100 people from 1300 will get AC on D. Please don't atleast decrease the rating of others not cool.

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

Strongly suggest make it unrated

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

I look at the statusboard and I found there're a lot of people get a WA in the 29th case of the D problem,and I also found that nearly all of them have a same wrong answer, so is anybody able to detail the test data? I want to know where I'm wrong? please?

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

I look at the statusboard and I found there're a lot of people get a WA in the 29th case of the D problem,and I also found that nearly all of them have a same wrong answer, so is anybody able to detail the test data? I want to know where I'm wrong? please?

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

D D everywhere

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

Oh, no its rated. I was heedless about the name. As usual seeing the name as Educational round I start contest though 30 minutes left. I saw this part (Rated for Div. 2) while its 10 minutes left only. :( :( Then there's left a cheap situation for myself. :/ :/

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

Are you people really asking to remove test cases from D or declare it unrated because you didn't know how to solve it? C++ is good for somethings and bad for other things. It's normal... Python sometimes gives TLE in a solution that is ACP in a c++ implementation. Should I complain when it happens? If you didn't get the correct answer next time try harder and learn more.

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

Nice language-dependent contest...

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

    Granted its nice to have problems not dependent on specific languages. But when you have so many languages with different characteristics, its very hard to design such problems. Yeah it was not the author's intention to include big integers, but that doesn't make the problem wrong. I have seen plenty of problems requiring big integers but not mentioning explicitly in the statement. Sometimes you should be able to figure out what data types you need and in this problem it was quite straightforward to do so.

    If its unfair for C++ users, think how many problems are unfair for python or java users? I know some of you are pissed, but put aside your personal feelings and think neutrally.

    And its also not that it can't be solved in C++ at all...

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

    All you C++ coders complaining, you've never coded competitively in other language... many many many contests are 'language dependent' in favor of C++, but nobody complains, because we are used to it. This is the first contest where C++ is at a disadvantage and there's so much complaining. (and it's still very possible with c++, while sometimes other languages are literally too slow to pass)

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

If you think (like me) that answer on D > 10^18 is a bit unfair for c++ users, upvote this in the idea that CF responsalbes will see this and will see how many we are. It was a nice contest, short statements and beautiful problems, but this thing on D deteriorate the value of the contest.

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

random_shuffle(ranklist.begin(),ranklist.end());

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

Should've ensured that answers were less than 1e18. Sorry to say, but very careless question making.

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

    Did they change the statement for D? It doesn't say in the statement that the answer would be less than 10^18. I don't see why it would be the fault of the problem setter instead of a fault of an assumption of the solver.

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

      I'm not saying I'm not at fault, but I feel such variables should not been involved in such contests. The fact that they had to clarify mid contest clearly indicates that they had not prepared to trick people and instead it was something they overlooked, which I repeat, is very careless

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

How to solve G?

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

Anyone solved D with index compression + segment tree? I had this idea, I know its much harder than other solutions, but its just the opposite way of what everyone did. If anyone solved this way, please write me.

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

So next time I read a problem, I first decide what language to use, then learn the language from scratch in contest time, and then if time permits, find out the logic and eventually code the solution. Thank You CF for teaching me a new approach today :)

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

    You can implement your own BigInts in cpp. It would just be something else you prepare before a contest like your other templates.

    Although I guess learning a language in 2 hours would be another viable strategy.

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

    You really only know C++? That's a really bad habit. Mainly when cases as this appear... It's like only knowing javascript or python

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

The hack been used to for D is incorrect I guess, cause it shows answer to be -9999999990000000000 =-9.9 * 1018. Please check.

Update: My bad. The update post mentions "It isn't". I overlooked.

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

    The clarification just said: It isn't guaranteed that the answer doesn't exceed 10^18 by absolute value. Really sad.

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

    I didn't even look at that "isn't", i just read "...guaranteed.... doesn't exceed..." , and i was like "ok, no problem!"

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

All contests are language-dependent... A lot of times the same solution implemented in Python gives TLE while solutions in C++ don't... Is that unfair too for you? Or that next_permutation exists in c++ but not in java. Is that unfair when a contest requires it?

I think you all have the conception c++ is the best in everything but it has its limitations too obviously... You are a good coder if you know them and can adapt. Congratulations to all who solved D. If you didn't better luck next time. Keep improving everyone!

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

The announcement "the output > 1e18" doesn't make sense because LLONG_MAX > 9e18.

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

AC in D with long double 33191777

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

Everyone's switching to Python on D after getting hacked

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

Why you announced like "Output can exceeds 10^18"? You should use maximum range of long long data type instead of 10^18. Making this round rated will really unfair to many contestants.

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

    Why? Pretty much everyone got hacked, so no harm was done.

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

      Well, who solved D before solving some other problems, will get more penalty than others, it's not a unfair?

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

      What about those who tried D first?

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

      Announcing the hack test is not unfair? Why did they have to to that? -_-
      If they didn't announce that "Output can exceed 10^18" then it would be totally fair to get hacked for that case :)

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

        They announced that during the contest so people had time to fix their code.

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

    Making this round unrated would also be really unfair to many contestants.

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

      Don't worry. It seems to be rated, you are gonna be blue.

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

        As long as nothing bad happens in the next 10 hours. :)

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

        I wasn't talking about me originally though. There's many people who did D and did it correctly, and it would be unfair to them if the contest was made unrated.

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

AkiLotus

anyone higher than this?......

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

Why was the clarification "isn't" instead of "is NOT"?

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

my algorithm for D is first sorting the given array and then keep a map for every i and then use a fenwick tree for find the answer. To compute the number of elements 1 greater and 1 less than this element and update the answer. Also insert in fenwick tree. My submission is 33181133. Is there an easier method to solve this. Although i got hacked for not using big int of unsigned ll.

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

    yeah, prefix sum and map of occurrence only, got hacked too 33189540

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

    A nicer way is to compute all the differences between any pair of elements, then find all the differences that are equal to 1 or -1 and subtract them from the answer. this can be done easily with a map.

    Of course, bigint got us all :)

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

Будет ли раунд для второго дивизиона рейтинговым, ведь реально не справедливо к задаче Д

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

    Странный вопрос от человека, который не участвовал в раунде.

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

How to solve E ?

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

    Someone mentioned calculating hamming distances for string, idk if that's true.

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

    my idea inside the contest was using hashing , first in O(k*n^2) find the hashes of all the strings except for the 1st one and store all the hashes in a set for that string.. (make a set s[K] , k == no. of strings)..

    After this , for the first string , in O(n^2) find all the swaps , get the hash corresponding to the NEW first string in O(1) ( we calculate the hash from the 1st string's orignal hash,because SWAPPING 2 characters means we have to just add and subtract 2 values ).. So for all possible swaps of 1st string , check in O(klogn) for all the other (k-1) strings if they have the hash in their set.... if they do have the hash , then print the current NEW(after swap) first string...

    Implemented this in contest because had 1:30 hours on hand but somehow gave segmentation fault , then I quit , it was getting very late,went to sleep..I havent corrected my bug yet .. so if please someone finds fault in my way please correct me , I am learning, also I would like to know how others did this.. , again , if my way is wrong please correct me and tell me why :)

    TOTAL COMPLEXITY = O(k*n^2)

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

Wanted to know rating predicted by CF-Predictor: Predicted <= Rating_Increase (Because Div1 would be removed), Predicted > Rating_Increase (As seen in last round)

Which would be true. If 2nd one, why is it so?

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

Wanted to know rating predicted by CF-Predictor:

Predicted < Rating_Increase (Because Div1 would be removed)

Predicted > Rating_Increase (As seen in last round)

Predicted = Rating_Increase

Which would be true. If 2nd one, why is it so?

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

    It would depend on your placement. If you are currently beating a lot of Div1 people, then it would overestimate. Otherwise, it would be closer to accurate or maybe underestimate.

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

I hope that the problem about problem D ended, but I prefer to share an idea with you as a lesson to us: let us assume that the function d(x,y) give 1 instead of y-x when the condition |x-y|>1 is setisfied. Then the problem come up to be: [calculate the number of pairs ai,aj (where 1<=i<=j<=n) that setisfy the condition mentioned upove]. In this case, we, as problem solvers, will say in our minds: [the upper bound of the answer is the number of all that pairs ai,aj, so it is n*(n-1)/2+n, and since n can be equal to 2×10^5, we surely need to use long long int data type.]. All what we said was a result of our habit that the answer is either int or long long, but this is not enough for a problem solver.

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

when the rating update will be published ?

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

    After System Testing with the all the hacks that have been submitted during the hacking phase.

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

Errr, may I ask why my rating haven't changed? I'm sure I'd played this game.

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

the answer in problem d can exceed 10^18 It is very unfair for c++ coders

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

    How so? You shouldn't be able to slap long long onto every answer that will be an integer and expect it to work.

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

      but there are a lot of languages like java that has big integers so , I am talking about the judge should avoid the differences between the languages

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

        That's like saying we shouldn't have any problems that use next_permutation because cpp has it built in, but Java doesn't.

        Languages are different, and Codeforces lets you pick from a variety of languages to solve problems. It's up to the coder to pick the best language for the problem or to know how to make an inferior one (for that problem) work.

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

          But next_permutation is easier to code than bigint lol :D

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

            How about nth_element :D

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

            You didn't even need bigint. You could get away with two unsigned long longs or even just use a long double and call it a day.

            There are many ways to do a bigint very simply if you do not need to hold values that large.

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

When will the editorial be published?

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

lolpic

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

Thanks for problem D! I got to learn something new from it. If anyone knows any problem related to it can they please comment the link? Thanks!

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

How to solve F?

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

The integer overflow problem in Div2 D can be solved by using long double instead of long long in c++.

My solution

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

I am surprised that there are so few discussions about how to solve problem G.

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

I feel like the statement about ans exceeding 10^18 should not have been made public. As a programmer, it's our responsibility to estimate ans and use data types accordingly. That announcement assisted all the hackers who were unaware about it at first. Only the one's who actually knew that the ans would exceed long long were the ones who deserved the points gotten by hacking.

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

    Completely agree. Moreover, people who had a correct solution from the beginning lost rank due to other people's resubmissions.

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

when will rating change take place?Hacking period is over

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

RIP rating :'v

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

Problem D reminded me the painful memory with problem Prize from IOI 2017. I made the same mistake in both of these problem: making false assumption because of 'it has never happened before'. For this problem, I made an assumption that BigInteger is not needed because 'Codeforces problem rarely required that'. For the IOI, I made the assumption that the checker is not adaptive because 'I haven't seen an IOI problem with an adaptive checker before'.

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

I got AC in D with c++ without bigint.

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

Will you make a list of the top Div 2 competitors? :D

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

In problem D, why double gives WA on test 13 while long double gives AC ?

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

    because double can not represent numbers up to 10^18 with precision of at leat one (that is, the diference starts to be, for example 2 or more, if the current number is 99...93 the next can be 99..95, skipping 99...94), long double, due to its bigger representation, has a better precision

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

Can someone please explain F ? I do not understand it from the editorial.