Codeforces Round 389 Div.2 (and Technocup 2017 — Elimination Round 3)
By MikeMirzayanov, 8 years ago, translation, In English

Hello, Codeforces.

Codeforces Round 389 (Div. 2) will start on December 25 (Sunday), 09:05 (UTC). It will be based on Technocup 2017 Elimination Round 3. So, if you are a Russian-speaking high-school student, please take part in the Technocup 2017.

Many thanks to KAN, fcspartakm, Endagorion, Kostroma and Golovanov399 Hope to extend the list soon because of testers. Also some problem ideas are mine.

I hope you will like problems. It will be 6 problems.

Wish you good luck and bugless code

UPD: The scoring is 500 - 1000 — 1500 — 2000 — 2500 — 2500

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

Comments Comments (235)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Unusual time >:( Never seen a contest this early before.

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

Contests are the best kind of Christmas gifts.

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

    I love contests, but so far I've only gotten rating drops for Christmas.

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

      Yeah I've been on a pretty bad downward trend of rating drops lately so hopefully we both go up lol.

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

        Yep, good luck to you and everyone else doing the contest! I hope they have more contests coming during Christmas time.

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

        Dont worry, He's working on it. Just believe! :)

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

        I guess I can say congrats on going up now :)

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

      Rating doesn't matter.. Practice and practice :D :)

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

I hoped div 1 round and another big battle bitween nutela guys and me :D

Anyway thanks for one more contest :)

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

Want a contest for Div.1

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

"Wish you bugless code" I like this wish

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

good time for me. hope interesting problem

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

As usual, the score distribution will be released before the contest starts.

So does the ** ** ***** meme.

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

[user:Kostoma]? I think it should be Kostroma .

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

There are two contests in CF now, one is "Technocup 2017 — Elimination Round 3" and the other is "Codeforces Round #389". I do know that I should go to the official website if I were a Russian-speaking high-school student, but now that both the contests are in CF, and I'm an English-speaker, which one should I participate?

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

    Round #389 of course, since you are NOT a Russian-speaking high-school student.

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

I'm sorry, but I think it will be understandable only for the countries of the former USSR )))

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

Oh, what a pity! This guy is so unlucky! xDD

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

    And that guy has exactly 11 hacks too.

    (Btw are they having a warm-up contest?)

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

Btw, Wont we get our new year gift this year? I mean, wont there be an option of changing handles this year? :( I'm fedup with my handle

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

Terms of agreement were in Russian. Will problem statements be in English?

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

sorry, but what is the difference between these 2 contest?

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

    First contest only for Russian pupils, second contest for participants from Div 2.

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

    Being more precise, the round that is "Technocup 2017 — Elimination Round 3" is a qualifying round for the russian school (Junior) informatics olympiad.

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

why are the terms of agreement written in english? Should i just register or is there anything important?

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

For me this contest will be on the Christmas morning (I am Romanian). I won't be able to participate.

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

Hope there's no "greedy" tag ^o^

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

    Hi Andy.

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

      The last 4-5 contests have had so many greedy problems! xD

      Greedy problems are hard :'(

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

        I agree. They require a lot of out of the box thinking, unlike relatively similar level DP problems. A div 2 C greedy + constructive algorithms is much harder for me than a div 2 D DP.

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

Technocup problems are usually harder than the normal contest questions right? I am new here.

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

If I am a high school student, but not from Russia, it also can I compete for prizes?

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

Too many homework. Who can help me with my homework I really want to take part in it:)=>

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

=)

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

A great way to learn DFS.

Don't see this spoiler)
→ Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Wish to have upward rating as Christmas Gift...LOL But downward rating won't be able to restrain myself from participating rated Contests.

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

when is the winter look of the site coming? :D

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

Just curious, why do you have Div.1 Rated Unofficial Round for Technocup round 2, but not round 3. Is round 3 easier than round 2?

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

    For Round 2 we've added two extra problems specially for D1. This time we do not have enough time, sorry. We expect interesting D2 round, you can join in unrated way.

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

Bugless code would be great but I am happy with less buggy code currently. Thanks Mike.

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

Today is my birthday! I am going to take part in this contest as my birthday gift =D Thanks to codeforces!

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

Merry Christmas to all and wish you a positive rating change...

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

finished 3 problem, look at standing, rank 1200, neat. look again 1200 out of 2700, damn, rating will drop.

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

I did not understand problem C. :( Everyone did that and now problem B is Hacked. :|

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

Pretty scared about system tests. Every problem from B onwards could have some tricky corner-case. Good luck guys!

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

Problem F is similar to 364 Div1 B.

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

How can be hacked B?

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

    aa ab Answer should be -1

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

    ad
    aa
    answer is -1.

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

      Darn I can't believe I didn't realize this during contest.

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

      I was trying to hack other people after I solved your hack, but then I couldn't manage to open other people's solution somehow. Probably something with my browser. What a pity.

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

    Can confirm was hacked by the cases above.

    Edit: Jesus Christ just took a look at the leaderboard. Calm your +18 hacks down mate...

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

Best tests for B:

abb
bab

bab
bba

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

So fail;)

Why high school olymps always goes wrong for me?:D

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

Was pretest 8 of question E some edge case?

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

Problem C is much more easy than B :/ Solved C in 2 minutes, but B took about an hour

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

    Good for you — This sounds promising as you probably didn't get hack.

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

    First, I found it difficult to understand C. How did you solve it?

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

      Ex: RRRU|LU|RURUU|LULLL|DLDD|RDRD|LD| answer is 7

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

        Oh, interesting. Will have to think why that works. Thanks for sharing your solution.

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

      There are many ways to solve it.

      1. Start currX and currY with 0. If 'R' occurs, then currX=currX+1, etc. And now check the distance b/w prevX,prevY) to (currX,currY). If it is increasing, then its ok and update curr. Otherwise it is required point, so count++, and update prev and curr.

      2. First delete all the consecutive duplicate characters (For example, RRLUDDL will be same as RLUDL). If current character is making U-type-turn, then it is the point,so count++. else move forward. (RUL,RDL,URL,RL,UD,etc will make U-type-turn). Solution for this : 23321935

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

Whats the logic for E,please?

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

    Binary search on the number of slices that each person can get .

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

    There are a couple of ways to solve it. I think the optimal way is this one:

    Keep the maximum value at the start, you'll choose only this one.

    Go through all the ones that have more than the current minimum value and split them. You'll do this O(log(max_value)) times, so the complexity is O(log(max_value)*n)

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

Hits for problem D?

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

    Hash and group the strings, then compute the results by taking strings greedily.

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

      u_u I could not found the greedy approach!I had no idea if it was convenient for a string to pair with itself or with his palindrome

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

        You can't be greedy in all the problem, only in the first part of it =P

        Try to separate it in two cases:

        1 — the string is not a palindrome? Than, I can put it on the final string IF AND ONLY IF I put his reverse; you can check if Santa will get happier with it xD

        2 — the string is a palindrome? If so, do I have 2 of it, and it compensates to put two of it on the final string?

        For the not greedy part, you have to look for the better string to put in the middle (it has to be a palindrome); notice that this is the same that removing one palindrome string from the final string

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

          You can greedy all the way if you keep the value correctly.

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

      Did you use trie as a hash or map<> was enough for this problem?

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

        map<string, vector > was enough.

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

          The cost to insert a string with size n into a trie is Θ(n).
          What is the cost to insert that same string into map<string, ..>?

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

            O(nlog(amount of input)), which is still good enough to fit into TL.

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

              I've understood from your previous comment that map<> is good enough for this task :)

              Now I am more interested in general understanding of the situation with keys in map and set.
              When we are inserting strings in map it is not the same as inserting integer values. Internally map has to perform O(log(m)) comparisons to find the place where we should insert the key. For string keys and integer keys this estimate is the same, but not for the comparison. It takes O(1) operations to compare 2 integers, but to compare strings of size n we need Θ(n) operations.

              So, to sum up, according to my calculations the complexity of inserting m strings of size n to map or set is O(nmlog(m)).
              Am I right?

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

                Yes, you are correct. In total m times of query should take O(nmlog(m))

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

What is the test 10 of problem E?

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

    this is it

    50 300

    9293 9540 6585 6756 215 6853 4819 3033 5529 8201 4072 4862 4071 5500 5717 229 7696 5440 4407 1108 1680 1974 5414 9053 8480 1030 5556 5551 4741 452 1045 2553 8944 7627 3737 3876 2846 3563 3246 8436 1075 2974 9410 1127 1968 830 1380 7371 6414 6384

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

Too bad it's not possible to hack own solution. While hacking others I realized, that my code has the same bug, so I could have used the extra 100 hack points, since it will fail systest anyways...

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

    U want to hack yourself?!:d and u want to earn points when hack yourself?!

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

    It is not too bad :D , if I realized that I will fail a test , I will hack my self then I will submit again with an if condition added xD which says if (input == certainInput) print (the right answer) , then I will hack my self again with another test case but the same concept ...... and I will get a lot of points which I don't deserve :D

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

      You can't resubmit after locking solution and you can't hack without locking

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

Best contest ever

but it needs more time to solve all the problemset :\

Good Luck everybody :D

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

5651 registered for contest.
2745 have actually participated.

More than a half decided to skip this round. What happened?

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

wtf, my binary search in problem E was giving wrong answer? testcase 8. anyone please?

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

    You probably didn't do the divisions in half. I had WA test 8 as well until I fixed that.

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

    I got this wrong too, you can't just divide. Pieces can only be cut in roughly halves.

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

Problem C seemed really hard to me. What are some important observations for it that lead to a solution?

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

    Intuitively, we can tell that if the robot changes the vertical / horizontal direction, then the current position of the robot may lie one of the point.

    One of the way to approach this question is by keeping whether the robot is free to change it’s vertical or horizontal direction without declaring an extra point.

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

    OBS1:A path is shorthest path if is true that his length is equal to the manhatan distanse,I mean abs(X)+abs(Y)

    OBS2:Try to get minimum number of intervals where OBS1 is true

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

    The idea is that the robot will not decrease the distance from its starting position when he is moving to the target. That is, the value |x| + |y| should always increase when he is moving to a target. When you see that this value is decreased, that means he has reached a target before that move and he is now moving to the next target.

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

    If he is going from point p1 to point p2, he can't go to Left and Right beyond that path, only to one of then. Same for Up and Down ;)

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

    There are many ways to solve it.

    1. Start currX and currY with 0. If 'R' occurs, then currX=currX+1, etc. And now check the distance b/w prevX,prevY) to (currX,currY). If it is increasing, then its ok and update curr. Otherwise it is required point, so count++, and update prev and curr.

    2. First delete all the consecutive duplicate characters (For example, RRLUDDL will be same as RLUDL). If current character is making U-type-turn, then it is the point,so count++. else move forward. (RUL,RDL,URL,RL,UD,etc will make U-type-turn). Solution for this : 23321935

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

How to solve C ?

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

    Between any two points, to move on the shortest path, you will go only in two directions: {R, U} or {R, D} or {L, U} or {L, D}. You can't go R and after other moves, make L because it won't give you the shortest path. So, all you have to do is to check if you "change" your directions. For example, if you move to R and U/D, and then move to L, it means that you arrived at a point before move to L. In other words, you have to split your string in continuous substrings such that in any substring, there aren't 'U' with 'D' and 'R' with 'L'.

    Example: RUDRDDRUURDRDURDRD ===> RU|DRDDR|UUR|DRD|UR|DRD ==> 6 points

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

      Was thinking along the same lines but made some implementation bugs :(

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

    http://codeforces.me/blog/entry/49251?#comment-333247

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

D hack case :

4 3

aba 4

aba 3

aba 3

aba -2

Answer : 10

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

    Pass your test, but WA8 still)

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

      test 8 must be something with 0. I got four WA on 8 and changed > to >= and got passed

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

    Passed your test but I just realized my solution gives a wrong answer for this:- 2 4 aaaa 5 aaaa 5

    My solutions gives 20 :( .RIP D.

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

free christmas trees for everybody

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

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

Merry Christmas!

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

That moment when you make 11 hacks on B and then recieve Wrong Answer on main tests xD Merry Christmas guys

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

why system test so quickly?

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

    Maybe because only half the registrants participated?

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

Problem E , WA 21 . Anyone knows why ?

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

Problem E statement says: "Santa Claus wants to present to everyone either a whole tangerine or exactly one part of it (that also means that everyone must get a positive number of slices)", that is #tangerines > 0, but in test #11:

total pupils k = 2000000000

total sum of parts of all tangerines = 128135987

Obviously, no solution. Answer in test is 1. Am I wrong?

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

    How could you tell "total sum of parts of all tangerines = 128135987" ?

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

the expected time complexity for E is Nlog2N right ? my Nlog3N solution got TLE.

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

    There exist a O(N) solution. I also got TLE. =(

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

      )= any binary search is TLE?

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

      The sole reason I didn't submit was because I didn't have a O(N) algorithm that would fit TL. I guess we have good enough testcases for the problem! :)

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

    I used binary search and got AC, the complexity is O(log107 * (107 + N)), 23298066

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

Why in java when I defined a HashSet of Pair<Character,Character> and insert (a,a) then insert (a,b), the HashSet only contain (a,b), even the 2 inserted value are different (Obviously (a,a) != (a,b)) ?

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

    Sets by definition don't keep duplicates (duplicate keys in this case). So when you put (a, a) the value a is mapped to key a, and then when you put (a, b), the old value for key a is erased and overwritten as b.

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

      I know that, by I created a HashSet not a HashMap and as I know HashSet contains only keys (not pair <key,value> as you said) and doesn't contains duplicates, now Pair<"a,"a"> != Pair<"a,"b"> and these 2 are not considered duplicates, right ? or I'm messing something there ?

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

      You are wrong.

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

    It only checks for first element in pair. You have to create a custom compare function.

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

      Oh thanks I didn't know that ,it's disappointing that I was aware of the hack but I was wrong with syntax :( !

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

      You are wrong.

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

    Check your line if(a.charAt(i) != b.charAt(i)). You never insert (a,a) into the set.

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

anyone who got TLE on E? sorting the numbers of slices gives me AC.. it's weird..

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

B :O WTF !!

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

In what time does the ediorial come in general ?? I am new to codeforces.

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

taketop150

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

During the contest i've found out that my knowledge of C++ is really awful. I've been writing in Java for so long and changed my language about a week ago so that OK I guees. But could you guys please help me. In my code for D I had map<string, vector > val which meant all the prices of string s. After reading the data, I did the following: for (auto p : val) sort(p.second.begin(), p.second.end()) which, as I thought, sorted all the arrays in val. But actually it didn't because when I accesed val[i], it's elements were in input order. Why so?

23302886 that's the submission to make it clear.

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

    for (auto &p : val) 23308346

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

      Absolutely right solution failed because of only 1 character in code. So cruel. Thank you a lot. But could you please explain if I am right that for (pair<string, vector<int>> p : val) copies it's items, so in fact it works in O(n) ?

      Despite the fact that I could be in top-15 or even better, I'm not sad because finding this gap in my knowledge in CF round is much better than in some important rated olympiad. Also, I believe that the person who does such a stupid mistakes shouldn't be in Div1 :)

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

    Чтобы изменять элемент map'a надо писать: for (auto &p : val), т.к. иначе p только копирует значение.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    for(auto &p : val)
    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

Can anyone help me in D? WA test 14, don't know what's wrong...

http://codeforces.me/contest/752/submission/23309705

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

How the output for first test case

4 RURD

is 2 ?

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

    Robot in (0, 0) First point is (1, 1); Second is (2, 0) OR First point is (2, 1); Second is (2, 0)

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

Where is UPD2???(((

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

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

TLE in div2E because I didn't sort the array :( such case very problem no wow

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

    Actually O(n × log2(n)) is little bit tedious solution for this problem. Mine got AC without sorting(same complexity). I used some bit-wise operations to reduce the time.

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

    Without sorting, solution of O(log(10^7) * (n + 10^7)) is getting AC.

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

    log(10^7)*log(10^7)*n is getting AC. However, I had to do a little optimization like getting rid of long long .

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

Could someone tell me why my code on problem D was wrong on test 11? Is hash unavailable for it?I'm really confused.Thanks! Here is my code: http://codeforces.me/contest/752/submission/23309803

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

How to solve F?

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

    You can always use a single node, the centroid of the tree. Once you find that, find the list of each vertices in each subtree. Then put them in a priority queue and always make a pair one each from the two longest lists.

    Code

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

When will be editorial??

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

    "results will be later". This is written on oficial web-site of TechnoCup.

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

    Here it is, sorry for the delay.

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

      А будут ли написаны победители контеста? И ссылка на разбор с самой записи о контесте — как обычно?

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

Can anyone tell how to solve E using binary search (if possible) ???

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

    Binary search the minimum amount everyone should have. To calculate how many people can receive this amount of slices, just run through every element in the array (since every element is independent). Here's my code (pretty short) 23302187

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

      Thanks a lot :)

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

      could you explain this part of your code? 

      fr(n) {
            int p = 1, j;
            for (j = m; j <= a[i]; j *= 2) {
                p *= 2;
            }
            c += max(p / 2, p - j + a[i]);
        }

      i know here you are finding for each tangerine how many people can get an amount m. I had to spend almost 3 hours to figure out an appropriate way to do this. Check my submission 23315399 (the howmany(wholesize,piece) function). I knew there must be a more concise approach to calculate this.

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

        I discovered it by observation. Notice that j = minimum (m * 2^k) that k is integer and m * 2^k >= a[i].

        If j = a[i] then the amount will be exactly 2^k (equals to p). Otherwise when a[i] is decreased by one, two of the "m" will become m*2-1 and not divisible anymore. The amount will decrease by one until the amount becomes 2^(k-1).

        Like this

        a[i] = 8, m = 2 : {8} -> {4,4} -> {2,2,2,2}
a[i] = 7, m = 2 : {7} -> {3,4} -> {3,2,2}
a[i] = 6, m = 2 : {6} -> {3,3} -> {3,3}
a[i] = 5, m = 2 : {5} -> {2,3} -> {2,3}
a[i] = 4, m = 2 : {4} -> {2,2} -> {2,2}
        → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

My first realization for Problem D to solve using Tries and some greedy approach. But it seems hard for me to code it. If someone thinks like me, please share your logic and code also. Thanks everyone. :)

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

    It's actually quite a hard problem, tbh. I thought I solved it in contest but failed systest. The approach is greedy, but you have to be very careful.

    First, sort the strings in non-increasing order of cost. Then, when we arrive at each string, we have to consider two cases:

    1. The string is not a palindrome. In this case, we want to pair it with the reverse of this string. Also, we want the beauty to be the highest possible, so we will take one of the "reversed strings" that we need to find from an std::set that contains the strings already traversed. Of course, this should be the one with maximum beauty and can be found using lower_bound().

    2. The string is a palindrome. We do the same process as #1, but slightly modified. Consider the case:
      4 3
      aba 6
      aba -3
      rty 2
      rty 4
      If we implement #1 with this test case, regardless whether the string is a palindrome or not, we will get an answer of 9. The actual answer should be 12. We notice that we can always unpair exactly one pair of palindromes that are already paired from #1 and we will put then in the middle of the final answer's string. Greedily, we will choose the one with lowest negative number (in this case it is -3). Let's denote this value as m. Finally, there is also in another case, where there are not matching pairs for the palindrome. In this case, we will put in the middle of the string, but only if the beauty of it exceeds m.

    The answer is retrieved from doing #1 on the whole set, regardless of it being palindrome of not, then along the way take into consideration the cases in #2. Final answer = (answer of #1) + m. Hope this helps.

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

      Thanks. I actually think to map the same string and their beauties. And another variable for putting string in the middle. Variable initialized to 0.

      1. If a string is palindrome, then I could take Even number of string like this and also 1 from putting in the middle. But I will take Even number from this if beauties positive. And if left any positive beauties string, then update the variable I mentioned above, which will maximize my middle string beauty.

      2. If a string is not a palindrome we can took even number of its copy ( I mean from several string). I will take up to it positive donation. Because if I discard it I will not get any positive donation. So, take as many as possible but the donation should be positive.

      For your test case:-

      aba is palindrome. So, it could stay in middle. I can take No even string first. Then, update the variable to 6

      rty is not a palindrome. So, I will take up to its positive donation as possible. So, I will take two from this. Donation: 2+4 = 6

      So, Total = 6 + 6 = 12

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

        If you want my code, 23314454. Try writing it your way and compare the two. Maybe you find that your way easier.

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

      The answer should be 6.

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

      How is the answer 12? Won't the final string be "aba" giving beauty 6. Am i missing something? Thanks.

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

        Optimal answer will be: "rtyabarty" with considering "aba" that has 6 beauty so max beauty will be 4 + 2 + 6 = 12

        Edit: nvm i realized I was mistaken, maybe he meant the second "rty" to be "ytr" then in this case it will be 12

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

      Maybe test should be like this? If you want answer = 12: 4 3 aba 6 aba -3 rty 2 utr 4

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

      the answer for your test is 6, or i didn't understand something.(?) //

      p.s by the way , i don't know why i am getting WA on test #8, if someone had the same problem i will be thankful if he will tell me which problem he had. :))

      p.p.s my code : CODE,PROBLEM D

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

    I don't exactly know, what do you mean when you say "greedy approach" but my solution is smth like greedy approach. Ask smth if you don't understand)

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

Can anyone tell what wrong am I doing here Solution

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

    in strings 38-39 first you do i++ and only then you do st.insert( s[i] );, but it should be like this: st.insert( s[i] ); i++;

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

      That was not expected. Thanks.

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

      Meanwhile, Can you give a hint for D?

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

        Yeah! For each string you should find reversed with best coast. And maybe in center you will have one polindrome string.

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

Who's waiting for Mike's blog on chaning handle like me!? :-""

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

When we can change nickname?

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

hi first thx for the contest... this submission 23355723 is for problem D. i don't know why i got WA#8 :( please help me... thanks

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

    I don't know what is wrong with your code, but you fail in this testcase:

    3 3

    aba 5

    aba -5

    xyx 3

    answer is 5.

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

      thank you so much :) i got what was wrong... now it was Accepted :) thx

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

Can somebody tell me why i got WA in problem D with this solution?

http://codeforces.me/contest/748/submission/23331649

update : i got accepted

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

Could someone tell me why my answer got wrong in problem C in the pretest 14 (the answer was 50306 but i just got 50305) :(
http://codeforces.me/contest/748/submission/23372619

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

    Here is shorter test case that doesn't work:

    4
RLUD
    → Reply