By vovuh, 7 years ago, translation, In English

Hello Codeforces!

On December 12, 18:05 MSK Educational Codeforces Round 34 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for Div. 2 again. It will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were prepared by Mikhail awoo Piklyaev, Ivan BledDest Androsov and me.

Good luck to all participants!

I also have a message from our partners, Harbour.Space University:

Scholarship Information

We are offering a Scholarship for each of our three tech programmes: Data Science, Computer Science and Cyber Securityfill out the Form for the January 2018 programme start period or the September 2018 programme start period. We will contact you soon. Can't wait to see you here!

Go to form

Congratulations to the winners:

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

Congratulations to the best hackers:

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 successful hacks and 786 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

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 Editorial

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

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

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

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

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

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

Thanks for another rating round for div2 :)

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

Hope the queue is fixed.

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

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

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

really rated again??? I just Love CodeForces

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

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

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

    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.

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

Unrated educational rounds please!

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

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

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

a chance to recover from yesterday

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

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

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

    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.

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

A fast queue plz.

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

There will be any points on hacking?``

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

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

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

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?

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

    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

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

      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.
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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)

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

I hope every girl will downvote this :(

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

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

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

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

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

Rating baadme surakshit hogi pahle Codeforces Servers surakshit karwao :p

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

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

image

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

    It's also not guarenteed that answer fits into long long (((

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

      2 mins of silence for the c++ codes :/

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

    A contest about speed of resubmit? Cant accept this ending.

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

    I apologize, i was wrong.

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

    It's time for Codeforces to support __int128.

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

    A moment of silence for those who read it "It it's guaranteed.."

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

    The final answer donesn't exceed, but the answer during calculation can exceed!

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

    It hurts more when you try D before solving B

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

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

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

exclude the ans > 10^18 tests maybe?

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

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

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

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

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

      Yes

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

        So, you don't want to make it unrated? How I think you need to point on the exceed in the task

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

          Why it should be? Statement is correct, tests are correct. What's the problem?

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

            Actually yes. It is the job of problem solvers to figure that out.

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

    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.

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

    Does apologies make any sense?

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

      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.

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

    Will it fit in unsigned long long ??

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

      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.

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

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

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

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

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

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

            OK

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

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

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

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

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

    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.

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

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

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

        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.

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

          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 .

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

            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.

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

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

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

                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.

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

        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.

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

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

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

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

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

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

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

    I used int64_t in D still Hacked! :(

    update: fixed it!

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

      it can be negative so u need more than just 64 bits. Two int64_t's would do it.

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

    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?

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

Did need a BigInteger in the problem D?

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

    yes if you were using c++

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

      You'd need BigInteger for Java too.

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

    I think, if first half 1, second half 10^9. It will overflow long long, but not unsigned ll

    I have changed long long to unsigned ll. So I got accepted.

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

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

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

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.

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

Hello :D

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

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

    Didn't see it carefully but maybe because you have four nested for loops?

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

Nice problems, I really enjoyed the contest.

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

How to solve E ???

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it
    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.

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

      How can we prove this always works?

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

        What is the complexity ???

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

        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)

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

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

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

      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.

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

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

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

      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.

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

      How do you calculate the new hamming distances ?

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

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

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

    You didn't read the announcement carefully :D

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

    It was announced that the answer can exceed 1e18.

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

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

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

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

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

    They put hack cases into system tests though so solutions without BigInt should still fail.

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

    memcpy How did you arrive at that value?

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

    How did you calculate that? In my opinion if there are cases where the answer exeed 10^18, it is not fair, because some languages support big numbers, but c++ doesn't...

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

    you're wrong max answer is actually 20000000000000000000:

    consider the case where n = 2 * 10^5 and first half are -10^9 and the rest are 10^9

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

      Dalisyron numbers >=1

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

        Yep I guess I didn't notice that :/

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

          The first half is 1, the rest — 10^9. Answer is 9999999990000000000.

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

        first half 1, second half 10^9 definitely overflows long long, but not unsigned ll

        awoo said, it can be up to 10^20, which would overflow ull (I don't know how)

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

          How to do with unsigned? answer can be negative

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

            You can keep a sign value. I did it using unsigned ll. But I don't know if I could be hacked.

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

            33184706 handle positive and negative parts of the answer separately each in one ull

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

    It's an ACM-ICPC Style, so if the first solution gets accepted there's no penalty.

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

How to solve D??? :(

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

I just read the clarification about D :(

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

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

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

Hack for D?

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

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

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

lmao that D

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

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

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

Hints for E please.

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

    maybe dynamic programming with bitmask

    UPD: i mean about problem F sorry

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

    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.

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

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

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

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

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

      And You Can write Ai <= 1e5 :)),moreover you only need removing and printing

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

      sounds even more ridiculous :)

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

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

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

      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.

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

        Java and python have higher speed(time) limits

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

          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.

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

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

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

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

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

              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.

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

    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!

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

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.

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

Strongly suggest make it unrated

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

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?

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

D D everywhere

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

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

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

Nice language-dependent contest...

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

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

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

    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)

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

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.

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

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

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

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

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

    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.

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

      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

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

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.

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

    I tried this too

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

      Great, thank you. Im glad I didnt have time to code this solution, because it would consume for me so much time, and then i would get hack because of bigint.

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

        Number of people who solved d in the contest is decrease from over 1000 to about 100, so don't be sad :D

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

    I use index compression and BIT, but I got hack due to long long.

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

      Nice, I also knew it can be done with BIT, but I dont have too much experience with coding it, thats why i thought to code segment tree.

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

    My submission: 33193137

    I solved D with compression + BIT. I have used pair, so the first value is the sum and the second value is how many values are in the interval.

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

    Hii.. I am new and learnt BIT sometime ago.. Can you please explain me what does compression means in this context?
    Link to any resource too would be much appreciated. Thanks :)

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

    I used compression+segtree, got AC but failed due to long long. Here's my solution: 33182205. It's probably way too complicated, but it works.

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

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

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

    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.

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

      But can you use something coded out of contest? Except for defines and stuff like that.

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

    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

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

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.

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

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

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

      omg! I read "it's guaranteed" when notification had come! This is sad :(

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

        Me too!!! I didn’t realize until I found that almost every one is being hacked!

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

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

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

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!

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

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

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

AC in D with long double 33191777

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

Everyone's switching to Python on D after getting hacked

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

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.

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

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

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

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

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

      What about those who tried D first?

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

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

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

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

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

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

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

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

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

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

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

        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.

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

AkiLotus

anyone higher than this?......

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

    For now I can assure that nobody surpassed my record of 18 unsuccessful attempts in this contest xD

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

      81 hacks in a rated contest!

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

        hacks is effectless in educational contests. :)

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

          It's rated for Div 2. People will lose rating because they placed lower because they got hacked.

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

            Not really. In Educational rounds, all hacks are included in the final system test, which runs after the hacking phase.

            So nobody could evade the hacks eventually. The hacking is kind of a mechanism to test your ability to generate tests and exploit weaknesses from other people's codes.

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

            I mean who hack someone else don't get lower penalty. so 81 hacks isn't good for him.

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

              Everything happens for a reason. Maybe he'll find his own good in doing this (not obliged to be ratings/penalties) ;)

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

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

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

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.

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

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

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

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

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

How to solve E ?

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

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

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

    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)

»
7 years ago, # |
Rev. 3   Vote: I like it -9 Vote: I do not like it

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?

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

    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.

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

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.

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

when the rating update will be published ?

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

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

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

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

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

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

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

      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

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

        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.

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

          But next_permutation is easier to code than bigint lol :D

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

            How about nth_element :D

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

            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.

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

When will the editorial be published?

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

lolpic

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

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!

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

How to solve F?

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

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

My solution

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

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

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

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.

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

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

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

when will rating change take place?Hacking period is over

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

    I don't think they've run the system tests with the hacks yet.

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

RIP rating :'v

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

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

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

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

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

    You are molodchina

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

      molodchina Means ??

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

        This is a Russian humor. "Molodhina" = "молодчина!".

        This phrase can be translated as "Congratulations!" (and also as "Good job!" or "Well done!").

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

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

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

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

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

    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

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

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