GreenGrape's blog

Codeforces Round #471 (Div. 2)
By GreenGrape, 7 years ago, In English

Less than 24 hours till the round?
And still no announcement?
How come, Mr. Grape?

Codeforces Round #471 will take part on Friday at 19:35 MSK. Note that the duration is a bit longer that usual.

The round will be rated for all division 2 participants. Division 1 is welcome aswell :)

My gratitude to Grisha (vintage_Vlad_Makeev) for round coordination, Ildar (300iq), Nikita (FalseMirror), Azat (ismagilov.code), Eugene (rek) and Oleg (xen) for testing and Mike (MikeMirzayanov) for awesome Codeforces and Polygon.

There will be six problems with the following scoring:
500 — 1000 — 1500 — 2000 — 2500 — 3000

UPD. System testing is over. Editorial

Congratz to the winners!

Div. 2:

  1. 08163268
  2. heello
  3. KNB.
  4. flower
  5. NotGuy
  6. HarveySpecterGoiano
  7. seo
  8. JorreS
  9. zhabo
  10. Osama_Alkhodairy

Div. 1 (unofficial):

  1. uwi
  2. Taube
  3. dreamoon_love_AA
  4. mjhun
  5. chemthan
  6. Hasan0540
  7. tfg
  8. cerberus97
  9. mixnuts
  10. Lo_R_D
  • Vote: I like it
  • +210
  • Vote: I do not like it

Comments Comments (193)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

A BIT longer

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +32 Vote: I do not like it

Why are registrations starting so late?

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

i hope a lot of Hacking <3

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

It is raining contests...!!!

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

It is at night in China. I will feel sleepy at that time.

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

    It means that it is time to take higher rank for other country's participants!!!

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

Shoot...this contest start at midnight?

→ Reply
»
7 years ago, # |
  Vote: I like it +39 Vote: I do not like it

I don't really mean anything, but I remember your previous 2 rounds were all hackforces :p

Wish for better balance this time :D

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

I know what you did last contest, Mr Grape

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

My God !It is China's midnight~

→ Reply
»
7 years ago, # |
  Vote: I like it -23 Vote: I do not like it

hope problem statement as short as this post .

→ Reply
»
7 years ago, # |
  Vote: I like it -22 Vote: I do not like it

Ooh no the old harsh start time 1:30 AM....

→ Reply
»
7 years ago, # |
  Vote: I like it -45 Vote: I do not like it

Who is hero in this contest?

→ Reply
»
7 years ago, # |
  Vote: I like it -50 Vote: I do not like it

Can you set the contest without any huge statement?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -60 Vote: I do not like it

Your last contest blog you said,

"The main character of this round will be Imp the playful monster. Yet the statements are guaranteed to be short :)".

But you said nothing about statement in this blog...
Please tell about statement clear!!!

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

So late! But I will do it.

→ Reply
»
7 years ago, # |
  Vote: I like it +49 Vote: I do not like it

I really liked your past rounds. :) Excited to see the problems.

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +31 Vote: I do not like it

Good luck for everyone in owls contest. :)

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

wait this channel will solving every A and B problems After every div2 contest in (Arabic). https://www.youtube.com/channel/UCmWvb73kIq_oRThWd05Mtfg

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

the thing that pushes me to participate in this contest is just the writer"GREEN GRAPE",problems written by him are amazing and involves brain storming as can be seen from previous ones..:)moreover he is among top contributors ->12

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

I have just advanced into div1 after the previous educational round, but I registered this round before the rating change. Will I become unrated in this round?

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

Can we expect 6000 participation. :)

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

5 minute until start the contest this is my first contest and i hope that will be good.Pray me please :)

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

I can't register?

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

can some body explains the meaning of problem B???

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

    it's not fair, i solved A in ten minutes but after 30 minutes i couldn't understand the meaning of B!!!

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

      Same as you.

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

      Basically the problem is divided into two statements. First is which string is adorable. The string which contains exactly two characters is adorable. for example cx, aabba is adorable. And secondly the question asked whether it's possible to divide the given string into two adorable strings.( taking some character in first string and rest others in second string.)

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

Just after locking B and seeing the first B submission in the room, I realized that I screwed myself up.

Heck. Life just can't get any better than this.

→ Reply
»
7 years ago, # |
  Vote: I like it +16 Vote: I do not like it

IT IS difficult to understand B. :)

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

    I feel sad for my pool understanding of English.

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

B is just unreadable

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

What would GreenGrape do with the time that he/she gained from problem B statements ???

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

Why in task B in the second test zzcxx,but in the example zzxcc?

→ Reply
»
7 years ago, # |
  Vote: I like it +16 Vote: I do not like it

C is horrible

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

I think we all had this during the contest

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

[deleted]

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

Problem A: What is end time of discount?

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

    Discount is valid from 20:00 to 23:59.

    → Reply
»
7 years ago, # |
  Vote: I like it +104 Vote: I do not like it

I think GreenGrape should write problems for Div 1, not Div 2.

→ Reply
»
7 years ago, # |
  Vote: I like it +81 Vote: I do not like it

Very nice strategy by Mike and GreenGrape, Make problems so hard, so that server load will be very less...

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

can someone seriously explain problem B? i thot i understood then i got confused again are v supposed to divide the group in such a way that it can be divided again? like aabbb -> aa and bbb -> a|a and b|bb and yeee -> y|eee -> no solution

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

    Yes, we need to divide the group in such a way that it can be divided again. For example, in the test case ababa, we can group it to ab(which is adorable) and aba(which is also adorable). For zzxcc, we can group it into zx(which is adorable) and zcc(which is also adorable). For yeee, we can't group it into 2 adorable strings.

    → Reply
»
7 years ago, # |
  Vote: I like it +58 Vote: I do not like it

I think you should win the worst problem statement ever for problem B

→ Reply
»
7 years ago, # |
  Vote: I like it +118 Vote: I do not like it

GreenGrape stop making rounds please

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

    problem B any idea?

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

    It would have been better if problem statement for second question was in Russian(even though i don't know Russian) I would have still solved the problem cause English here is much Understandable

    → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +30 Vote: I do not like it

When someone forget to take english classes properly what happens? Something like Statement of PROBLEM B

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +23 Vote: I do not like it

I find it quite funny how GreenGrape always has some very nice ideas for rounds, but the rounds themselves don't turn out as nice as the problems, either because of hacks or difficulty spread (or both) :p

And yes, I do agree statement for B wasn't very clear, before anyone points that out for me.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +34 Vote: I do not like it

My 2 year old brother is speaking english better

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -31 Vote: I do not like it

kya hi chutiya problem statement banayi hai isne,brother you should stop making rounds.

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

Problems are not A, B, C, D, ... They are B, C, D, E, ... |^_^|

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

This is why you should implement your own sqrt function.

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

    True, I was getting WA on test 5 with sqrt() all the time, when I changed it to sqrtl(), I got AC :)

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

    you can check if the answer is correct or not by multiplying the result.

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

    If you use long double instead of long long the sqrt() function will work fine

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

    yes its true cos the sqrt function returns the double value by rounding it

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

Can someone please go through my C submissions (there are about 5-6 of them, here is one.

Got 5 TLE's and wasted 1.5 hours of my life :(

Edit: the logic is surely correct, I really have no clue where I messed up despite so many constant optimizations.

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

    My soln is very similar to yours. I also got TLE on 3rd pretest. I think this is not the intended soln.

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

I appreciate the contest, even though the problemset might have been a little to hard for Div2.

Problem C especially was a very nice problem.

Keep making rounds, and don't get discouraged by the haters.

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

Got idea for C in last 15 minutes...didnt have time to implement it :( is it binary search for every exponent from 2 to 30 ? complexity is about 30*log( 10^18) * Q.

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

how to solve problem C ?

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

    For each number <= 1000000 insert to a set all the powers greater than 2 of the number.

    Make sure to erase all perfect squares in the set.

    Then, the answer is the number of items in the set in the range <l;r> + the number of squares, which is floor(sqrtl(r)) — ceil(sqrtl(l)) + 1.

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

      I Implemented the same idea but still got a WA on test 1 36549275

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

      your solution will fail for this input 1 10968163442 10968163442 ans should be 0 your code will give 1 ps :- sorry my wrong

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

      CF checker is too fast?

      The following code of someone is accepted in C.

      f(j, 3, 63)
    {
       for(int i = 1; i <= 1e9; i++)
       {
           if(pow(i, j) > size) break;
           int t = 1;
           f(k, 1, j+1) t *= i;
           s.insert(t);
       }
    }
      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i am only guessing, although there may a pattern if someone wrote a brute force to check.

    my guess: it sum kind of sum of pow(r, 1/j) + pow(r, 1/(j+1)) + pow(r, 1/(j+2))..

    lets just guess, all of us collectively.

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

C was too hard, and with lots of ways to go wrong. I think if it was changed to a D it would've been a better contest.

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

The problem statement of B was unclear, it took me an hour to understand it correctly.

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

This contest cried me :'(

Whatever, new problems to learn new approaches

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

What is test #3 of problem C?

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

Problem B is just shit!
I cannot really understand it after reading it about three times.
Questions? "Read the problem statement"
What the hell is this answer?

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

    they told me the same. it is like our teachers in high school. 1 + 1 = 2 is shown in classroom and in exam they give 1000000000*1000000000000 — ABC + worst contest = ? -_-

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

36552101

it took 1.5 sec in codeblocks but showing TLE (takes more than 10 sec on CF compiler). by debugging i found out that the problem is in siv() function. but i cant find why. I also added this condition (if (temp <= 0 or temp > 1e18)break;) still not working. can anyone help?

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

    You can use "costum innovation" to see what's going wrong .

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

      I did but found nothing. working fine on codeblocks. it showed TLE on test case 1 but is working perfectly on codeblocks. custom invocation shows TLE (10 sec) -_- .

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

      The problem is in siv() function but i cant find it...

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

I've got lots of wronganswers in C Maybe the accuracy problem Sad...

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

Could D be solved with binary search + hash I mean we go i=0...n-1 and we find maximal d such that s[i...i+d-1] = t[0...d-1],then we store all values in some vector, same for the right side but we do on suffix instead of prefix. and then we brute force for the length of first part we use in solution,greedily picking leftmost valid choice?

→ Reply
»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it
  • Critical info missing in A.
  • Poor wording to understand B.
  • Impossible to solve C.

As you can guess, didn't get any further than C. I bet english PS must be translated one.

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

    if it is impossible to solve problem C How did many people solve it ?

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

    "Impossible to solve C" More like, "Impossible to optimize C"(i'm still mad at my 2136 ms solution getting TLE)

    → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +4 Vote: I do not like it

I could have got an AC in C if I didn't spend much time in understanding B...

I think logic for C is iterate through p=2 to p=floor(log2l(R)) and calculate for log2l(L)<=p*log2l(a)<=log2l(R) and then do inclusion exclusion for 16 which can be written in two ways pow(2,4) and pow(4,2) .

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

[submission:36553906] 0.136 seconds too slow...(not sure if correct)

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

Div 2 B says: "Check whether it can be split into two non-empty subsequences such that the strings formed by these subsequences are adorable. Here a subsequence is an arbitrary set of indexes of the string."

This doesn't imply that all characters of the string must be used or that they must be necessarily distinct. It simply defines the subsequences as an arbitrary set of indexes of the string. Thus a problem such as "asrewsafdv" allows you to choose the subsequences "as" and "re" to form a valid "split into two non-empty subsequences such that the strings formed by these subsequences are adorable".

→ Reply
»
7 years ago, # |
  Vote: I like it -56 Vote: I do not like it

This amount of clarification requests turned out to be a real surprise for me.

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

How to solve F?

My solution idea was as follows:

  • for k = 1, we can calculate part of answer using depths of subtrees.
  • for 2 <= k <= MAXK=547, dp_k(u) <= MAXM=18. So calculate part of answer through calculating isKHeap[u][m] -- if there's heap of depth m rooted at vertex u.
  • for k > 547, dp_k(u) <= 2. Again, use that fact to calculate part of answer using number of children for each vertex.

This works in about O(MAXK * MAXM * n), which is too long. But I hoped, through stricter bounds on MAXM(k) and non-asymptotic optimizations, solution could be made fast enough. Unfortunately I got stuck at TL 10 =(

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

    u could optimize this if u keep dp_k(node) = the maximum depth of a k-ary tree rooted at node

    and u obtain O(sqrt(N) * N) but this tle too

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

    Iterate through 1..k..n. Solve the problem rooting the heap at every vertex with >= k children (< k children has answer 1). There are n / k such vertices. Delete the edges that go to vertices with < k children (so you don't visit them again). The cost for this part is O(n*log^2n) because N / 1 + N / 2 + ... = O(nlogn) and you need an extra log to get the k-th element of the children. Now, sort the answers in increasing order of values and use something like HLD to see how many ancestors have this answer. For each "chain", keep the maximum height where you enter this chain. You only need that since you just go up. The total complexity is O(n*log^2n).

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

if i want to write the problem B:

can we divide a string into 4 nonempty part , in a way that each part contains only one kind of letter?

what did you want to do with just writing that things???

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

CF predictor shows -99 but there is no codeforces HOT NEWS or any option to share it

→ Reply
»
7 years ago, # |
  Vote: I like it +36 Vote: I do not like it

And Would waiting for the editorial return back the 3 hours we wasted :((?

You're certainly missing a point there,People aren't mad because the problems are hard,but because they are misplaced..(and the Bad english in B)

If you were to place Problem C as D and Get a better translation for problem B,no one would be mad right now..

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

    agree with you and already down voted the idiot.

    Stupid B. Real Piece of Shit. And fucking stupid replies.

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

      So rude of you. Does calling me an idiot makes your life better or anything?

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

        well if i am getting up votes, that means people are agreeing with me. Seriously, my rating increased 5 times in a row until this. And i know i could have solved B if you could have explained it better. -_-

        No, calling you stupid, idiot does not make my life better. If idiots like you stop making contests and other people dont suffer — that will make my life better and EVERYTHING...

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

          People Agreeing with you doesn't make you correct.. also it's rude to call him an idiot Psycho,the problem set might have been a little unbalanced with some mistakes,but it doesn't make it bad..

          Anyway Sorry Grape about saying the wasted 3 hours and good luck on next rounds..

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

          Weak point. If you're stuck with B, what prevents you from skipping it and proceeding to C and further?

          If you are so vulnerable and cannot control your nerves, ain't it better for you to abstain from participating in rated rounds?

          Such childish behaviour...

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

            i think what prevents he from skipping B and proceeding to C was :

            problem C in fact was a D problem, not C!!(in my opinion)

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

              It wasn't a D, it was maybe C.5 but not D. (I didnt solve it either but it was not D)

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

                maybe an easy D

                i've seen a lot of D problems that they were a lot easier than this one

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

                  It would've been a lot easier for me if the time limit was 3 seconds instead of 2.

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

            skip is not working, I can't solve C, then it goes worse(DEF is even worse) :p

            of course nothing will happen except rating -87

            in fact if get 6 AC then +300 (but not possible for me now)

            which means I'm too weak to solve these problem now

            but this round's problem is really not suitable for Div.2 :p

            I want to solve Div.2 problem to improve myself but not Div.1 now ;w;

            after all, waiting for your next round.

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

    I'm always open to whatever feedback I receive, but this time it's hard for me to agree. Could you please explain what remained uncovered in statement of B?

    It's clearly stated that you have to figure out whether you can split the string into two adorable ones. What's the issue?

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

      How can you redefine the meaning of sub-sequence?

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

      I can't speak for others but this was the problem I had with the description:

      Div 2 B says: "Check whether it can be split into two non-empty subsequences such that the strings formed by these subsequences are adorable. Here a subsequence is an arbitrary set of indexes of the string."

      This doesn't imply that all characters of the string must be used or that they must be necessarily distinct. It simply defines the subsequences as an arbitrary set of indexes of the string. Thus a problem such as "asrewsafdv" allows you to choose the subsequences "as" and "re" to form a valid "split into two non-empty subsequences such that the strings formed by these subsequences are adorable".

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

        This doesn't imply that all characters of the string must be used

        The word "split" does imply that all of the characters should be used.

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

      What does it mean by the phrase: equal symbols
      Does it mean equal number of symbols or number of distinct symbols?

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

      While I really liked Problem C, I just wish the time limit was a little more liberal as many of us had an alternate thats just up by a constant of around 5. It was efficient in it's own way too (O(1) Memory). That and perhaps an easier D would've made it a great contest for me, Thanks!

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

      Here are the questions i asked myself while reading Problem B(which you didn't cover)

      1-Why is 'ababa' adorable but 'cccc' is not? Your explanation:you can transform it to aaabb, where the first three letters form a group of a-s and others — a group of b-s).but cccc is not since in each possible consequent partition letters in these two groups coincide.

      My thinking:You can simply divide 'cccc' to cc-cc

      My Alternative thinking:Maybe it should be distinct letters?

      After reading the sample explanation: 'In sample case two zzcxx can be split into subsequences zc and zxx each of which is adorable.'

      Like Wtf? why is zzcxx adorable and cccc isn't?

      The alternative thinking turned out to be wrong..Then my eyes dropped on

      subsequence..and how was aaa,bb a subsequence of ababa..

      I hope this is enough for you to reach how i thought while reading the statment

      Until now,i cant understand what it asks for

      --upd adding symbols there was also mislead,should've been letters

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

        You didn't read the actual question.

        The statement doesn't ask whether the input string is adorable, but whether we can split it into two adorable strings (not substring, but subsequence)

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

      carsonbradshaw, generally the meaning of "split" is to divide something into non-intersecting parts so that the union of these parts forms the entire object. I assumed this is quite obvious and seemingly failed.

      win11905, this question is quite strange. a and a are equal, a and b are not, for example.

      Ragnarok22, if you ever look through the clars as an author, you would probably change your mind.

      shash42, 5 is quite a huge constant. There were similar solutions during the testing phase, but they all passed in 1.5-1.6 seconds.

      Zaee, it seems that you misinterpreted the entire task :(

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

        A tongue twister might has no syntax error,but it's really hard to read.You could say it in another way easier to understand,thanks. Besides,you might be angry,but think of it,few people here means to pick a quarrel,and most people here is just wrote a feedback.A feedback like this shows that many people really cannot read B's statements well,and persuade the feedback-providers is in no use.

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

    Well for me and my friends C is far easier than D,thus the placement has no problem.But B is totally unreadable.I don't think it right to call that poor thing English.

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

The scoring distribution be like 500 — 1000 — 2000 — 2500 — 3000 — 3000. :P

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

"You'd rather wait for the editorial before downvoting :)" I think even though someone didn't wanted to down vote but after reading this from official comment GreenGrape, we are inclined to downvote. This has just increased the down vote.

→ Reply
»
7 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Fastest System Test EVER!!

→ Reply
»
7 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Add one more problem and this could have been Div1+Div2 combined contest.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -24 Vote: I do not like it

Problem C from the contest has already been used before: http://ws.kh.ua/media/sbornik/Sbornik2012.pdf, (page 111, Problem perfect powers) there is even an editoral in the book. (This problem at e-olymp online judge: https://www.e-olymp.com/ru/problems/2890). I believe that due to this reason concerning bad English statement of problem B round should be made unrated.

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

    How was I supposed to figure this out? :) I've never solved problems at E-Olymp.

    Moreover, the solution uses a different approach which is hard to squeeze when there're lots of queries.

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

      I tried 18 submissions, but inclusion-exclusion approach does not pass whatever I do.

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

    @vova_rakal Even though it was used before,there were very less submissions in contest. It means that no one has found it out and it is very difficult to find.

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

    The constraints of A and B in the second link is 10^14 while in this one it is 10^18. That makes some difference in solution, I think.

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

I'm surprised that there are only two AC on problem E. It is just to understand the statement :)

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

Thanks 471, my black streak of failure is over)

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

Great contest with good problems. Ignore the negative comments. :-)

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

Why this source didn't get hacked on test abcdefghijklmnopqrst http://codeforces.me/contest/955/submission/36549772

It should have got killed by signal on this test and thus succesful hack

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

    GreenGrape

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

    You really should read the solution more carefully.

        else if(num==4)
    cout<<"Yes"<<endl;
    else
    cout<<"No"<<endl;

    The case you gave was handled correctly.

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

      It would have gotten killed by signal?

      Isn't this wrong?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Ouch, now it was I who didn't read carefully. Sorry about that (pretty ironic feeling to me anyway).

        I've just submitted one of my solutions, with the return 0; command removed. It works with all C++ compilers. (36555214, 36555218, 36555221, 36555227).

        So I'm going to a conclusion that if no return command is called with in a non-void-returned function, it will always return the convertible-to-zero value.

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

it's really shame that some people want the round to be unrated because

they couldn't solve the problems

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

I liked problem C despite not being able to solve it :)

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

B is too hard to read

at the beginning I think adorable means a stirng with even kinds of letters

submit, pp, hacked

I going crazy after read it many times but still can't find anything wrong.

I guess maybe the "group" of adorable string should contain only one kind of letter.

resubmit , pp (now it's AC)

besides, after I locked my A just 3 min later my B get hacked

(I'm so lucky not locking B first)

and maybe Problem C's time limit is too tight ......?

after all, hopes next round will be better

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

it's really shame that some people want the round to be unrated because

they couldn't solve the problems, B has a lot of AC so what??

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

Problem statement of B is horrible. Even now I don't know why my solution is wrong (fails on test 35).

The least that could be done was to explain a few examples to make this statement clear. Very very bad contest, considering only 2 problems were solvable for most Div 2 participants and here also, the problem statement is so hard to understand for one of them.

GreenGrape, learn to accept your mistake (maybe your problem statement wasn't ambiguous in Russian, but in English it's a mess).

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

    This part in your code is not correct:

    if (count.size() > 3)
{
   cout << "Yes" << endl;
}

    Input: abcde — correct answer is No , but you output Yes

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

      That's exactly what I missed in my solution as well. I only realized it after locking, so I hacked with abcde once instead :)

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

      My bad — I missed the part of the problem statement where it says "equal symbols".

      I didn't even check the problem statement after I got hacked, because I had passed pretests. Pretests are becoming useless nowadays in contest.

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

Problem B was poorly stated, very difficult to understand. Unfair round.

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

can anyone please explain the problem B. :'(

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

    adorable strings are strings with 2 groups, each group have > 0 same characters. (ab, aab, abb, aabb).
    given a string, you have to find out if you can make 2 adorable strings using all the characters.

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

    It's kinda simple.

    First: An adorable string is anyone that has exactly 2 different letters inside.

    Second: If we want to get a subsequence of the starting string S such that it's adorable, then this subsequence must have exactly 2 different letters.

    Third: With Second observation, we realize that if we have 5 different letters or just 1 the answer is immediately "No".

    Fourth: Now, we only have the cases with:

    2 different letters: - Let (x,Qx) and (y,Qy) be the 2 letters with their frequency. Then, we can get 1 from x and 1 from y and create a adorable subsequence, with the rest of letters being the other one. Now, the other one must be non-empty, and thus, have size of at least 2 (1 x and 1 y). So the answer will be "Yes" iif Qx >= 1+1 = 2 and Qy >=1+1 = 2

    3 different letters: - Let (x,Qx), (y,Qy) and (z,Qz), so that Qx >= Qy >= Qz. Then, since Qx is the maximum, it's the best candidate so that we take 1 from it and what's left would be > 1. So, we can create an adorable subsequence taking 1 x and all y's, and the other one would be Qx-1 x and Qz z's. So the answer will be "Yes" iif Qx >= 1+1 = 2.

    4 different letters: - We can split the 4 letters into 2 subsets of 2 letters each, so the answer is always "Yes".

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

    Problem statement is so hard though solution is very easy . 

    S -> P | Q -> m | n || r | s

    Here S is for main string . P and Q is for after splitting first time . Then P will be splitted into two parts m and n . Q also follow the rules .

    All the distinct characters of m must be same . But m and n's mustn't be same . r and s also .

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

I liked the concept of this contest. The problems weren't hard in comparison to the usual CF Round, but the dificulty difference between each consecutive problem was kinda unusual (greater). It reminded me of CSAcademy rounds. GL & HR for everyone in tomorrow's contest :D

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

when will the rates changes ????

→ Reply
»
7 years ago, # |
  Vote: I like it +39 Vote: I do not like it

Please stop complaining about the statement or the difficulty! Don't blame other thing to make yourself think that your failure is not due to your weakness!

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

    sigh Finally the point has been made.

    Must admit, if I had ranted about my performance, heck, it should have been even worse than matthew99's incident...

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

Your problems are easy to solve but difficult to understand.

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

It's not really "mature" to blame other for your own mistakes, the round was good maybe C was a litlle bit harder than usual but look to the bright side after the editorial you will learn new approachs and techniques, there is never a "bad" round ... there is a good/bad performance and in both cases it's always an oppurtunity to learn new things and better ways to attack futur problems

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

GreenGrape editorials are only in Russian.

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

    I know :(

    I'll translate them tomorrow.

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

      OK thanks and there is no editorial for D, E and F. Hope tomorrow they will be published too :)

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

Can anyone tell me why my submission got TLE? Because I use python? http://codeforces.me/contest/955/submission/36549700

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

in the problem statement he says -> "For example, ababa is adorable (you can transform it to aaabb, where the first three letters form a group of a-s and others — a group of b-s), but cccc is not since in each possible consequent partition letters in these two groups coincide" what does mean by forming a group of a's and b's (aaa | bb) and how this thing is adorable ? and also zx | zcc adorable how?

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

    ababa = exactly two different letters (of two type) in string means string is adorable. but cccc doesn't contains exactly two different kind of letters (only one type)..

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

      Okay so we were needed to figure out what exactly adorable here means or u just deduce it by problem statement?

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

        I deduce it by problem statement. Obviously in actual world the word adorable is not coonected to problem. First in problem statement we need to understand what adorable means and then we need to check whether its possible to split the given string into two adorable strings.

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

          no i mean u came up with the logic itself? because what examples stated here were totally ambiguos one is aaa|bb, zc|zxx and ye|ee doesn't make any sense and also nowhere in problem it was stated that each adorable string should have two different symbol.

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

            "two consequent groups of equal symbols (note that different groups must contain different symbols)."

            equal symbols means same character. different group must contains different symbols means different groups must contains different characters.

            It can also be written again as "two consequent groups of same characters (note that different groups must contain different characters...

            I hope it's now clear....

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

Editorial is not opening.

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

Why does it say "You are not allowed to view the page" when i click on the link to the Editorial?

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

Here is my approach for problem C.

1) I stored all divisors of range [2, 64].

2) Now, for each L-R query, I ran loop for powers from 64 to 2[reverse loop].

3) According to inclusion-exclusion principle, if any number having power p is included in the range of L-R than it will be included by the power divisor too. We need to subtract the overcount by this power. Suppose the number is 2^8, than 4^4 will result in the same value. So, we need to subtract the overcount. 2^8 value is same for 4^4, 16^2. We will subtract the value 2 from ans.

I am getting WA on test 2 999999999999999999. My output is 1001003331, the expected output is 1001003330.

Can anybody explain me where am I making the mistake?? Link to my solution.

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

    Your approach seems correct, but when working with integers/longs,it's recommended to keep all your calculations in integers/longs and do all functions such as square root, log... manually, as all default functions in most programming languages works with floats/doubles, which can potentially lead to WA, when converting back to integers/longs, due to precision errors. So for the ceil of nth root of a number, you can try binary search it instead.

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

      Can you suggest me how to do this? I tried StrictMath library of Java. It is still giving the same error. I am unable to get your idea of binary search.

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

        Here's how, we get our mid, w raise mid the nth power, if it's bigger than x, then all values bigger than mid will eventually give bigger results, and there's not need to test them, thus right = mid, and the same thing if mid to the nth power is a smaller the x, following the same reasoning, left = mid.

        In case it's not clear, here's the code, it's easier to follow with.

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

hm... matter of my life : solve a problem or hack someone's code?

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

editorial not yet

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

why so hard.................. log in , find i can't solve C, goodbye & sleep

when i get up....

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

Please FIX the tutorial link...it says 'You are not allowed to view the requested page'

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

Sorry for the late of comment, but is there anyone could plz explain about problem D? I have some questions about the time complexity. I have seen some code that compute the array (the left most position to get a prefix of certain length and the right most position to get a suffix of certain length) using a "for" including a "while" inside. I can't figure out the complexity of this, I just know that it isn't worse than O(nm), but a solution with O(nm) is surely not an expected one. I just can't figure out how this "for" with "while" inside can be less than O(nm), and if so what is its complexity? Could someone plz explain that?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

I've done this contest later as virtual contest. I've been reading the comments of the forum here and have seen many people angry with the author. I've found the contest difficult for me, and perhaps problem B a little bit difficult to read, although it is correctly written, but as we know, something can be correctly written and difficult to read simultaneously. Anyway, it would be a pitty if the author feels discouraged to prepare a further contest. The problems are very beautiful from any reasonable perspective, so they are a great contribution. Writing in an accessible way and measuring the difficulty of a problem is a very challenging task that requires a lot of effort and experience. Even experienced writers fail from time to time. Practice makes perfect.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

.

→ Reply