Tinkoff Challenge — Final Round (Div. 1 + Div. 2 Combined)
By zscoder, 9 years ago, In English

Hi all!

On May 13, 12:35 MSK, Tinkoff Challenge — Final Round will be held. Standings of the official finalists are availiable here.

The authors of the round are me (zscoder, Zi Song Yeoh), AnonymousBunny (Sreejato Kishor Bhattacharya), hloya_ygrt (Yury Shilyaev).

Special thanks to KAN (Nikolay Kalinin) for coordinating the round, winger (Vladislav Isenbaev) and AlexFetisov (Alex Fetisov) for testing the problems. Also, thanks to MikeMirzayanov (Mike Mirzayanov) for the Codeforces and Polygon system.

There are seven problems and the duration is two hours. Scoring will be announced before the round.

Top 20 participants of the Elimination Round will compete in the Tinkoff Office.

The round is rated. Division 1 and Division 2 will have the same problemset with seven problems.

We hope everyone will find interesting problems and get high rating!

UPD : Scoring Distribution : 500 — 1000 — 1750 — 2000 — 2500 — 2750 — 3500

UPD2 : The editorial is out!

UPD3 : Congratulations to the top 10 :

  1. V--o_o--V

  2. LHiC

  3. Um_nik

  4. Petr

  5. Shik

  6. Syloviaely

  7. Seter

  8. SirShokoladina

  9. matthew99

  10. DBradac

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

Comments Comments (202)
| Write comment?
»
9 years ago, hide # |
 
Vote: I like it +24 Vote: I do not like it

Is everyone allowed to participate in this round, besides not having participated in the previous round?

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

Isn't timing unusual from normal codeforce rounds ? .... Do not want to miss it but have semester exam :(

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

:|

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

Thank you)

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

    Like someone said it's probably held at the same time as the on-site contest, and different countries hold APIO at different times so it's hard to avoid anyway.

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

zscoder Congratulations for becoming red :D

I remember last time you prepared a round you was purple

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

Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).

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

Are the finalists gonna be in one room?

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

I have an exam, but I'll participate :"D

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

Hopefully,there could be data structures related problems in this challenge......

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

hopefully there will be short statements !!!

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

zscoder is this the round you mentioned here ?

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

Codeforces determining whether or not there will be a delay

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

Hope there won't be delay before the contest.

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

1 hour delaying would be better...

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

Hot Day and cool codeforces!

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

I predict there will be a question on permutations.

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

I predict that problem C will be easier than previous contest.

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

I'm esemoooooo.

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

I just spotted this lucky cheater sepanta I hope that Mike will take care of him.

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

31 hacks on the same one!! What a cheater!!

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

my solution for problem C is showing "running test case 5" for the past 10mins.

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

I am waiting for explanation why it was not possible just to get Problem C AC at the first attempt.

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

How to solve B?

P.S. I feel like either A or B is getting harder than C nowadays. Last contest, I solved C easily, but unable to solve A. Today, I solved C (not so easily), but don't have any idea at all to solve B. It feels just weird...

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

How to do F? I hope expected solution is not

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

    I had N^1.5*10, didn't passed 16'th test. But I hope it can be optimized in the way to pass.

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

      I think NlogN*10 should pass. Just hold the information for lazy propagation as a permutation: all digits i became P[i]. Unfortunately, somehow, in an hour I've got 15 WAs, TLEs and runtime errors. However, it makes sense to work, it's just that I had a lot of bugs. You can propagate something like P[son][i] becomes P[node][P[son][i]]

      LE: of course it got AC immediatly after the contest

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

        Implementation is rekt

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

          Neah, it was easy. I don't know what happened to me. I used to have 0 bugs till a week ago and now every source that I code has the stupidest bugs ever. I had the right idea just after half of the submission I made: initially I though that it's enough to hold all relevant moves on some node and then traverse them and push them to the sons, as I thought there are at most 10 relevant moves (through relevant I mean they change something). Ohh, and of course I spent about 10 minutes to find out that there could be operations that change digit x in x... I think this should've been mentioned. Anyway, the problems were nice but I hurried a lot and wasn't careful because I had a lot of WAs (even on C, I still have no idea what I'm doing wrong as I have a complete proof of my solution, even though I think I overcomplicated the problem)

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

          That was a joke

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

        Damn, my solution passes if I switch to size of block exactly sqrt(N) and submit on MS C++ instead of GNU. Such a pain.

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

Can someone please explain C?

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

    xyz abc => answer is xcy

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

    So first observation is that you will only use the smallest (n+1)/2 elements of the first string and n/2 largest elemets from the second. If all chars from s1 are smaller then it would be easy, you would simply use a greedy to fill the word putting it at the leftmost position. Now, lets have the case where the elements from the first set are larger than the second. You would want to put your largest chars to the right most position, as that minimizes its penalty. So now in these case, you go from largest to smallest and put them in rightmost position. Same is true for the second player

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

      I did something like that, but got WA, could you tell me what's wrong with this code?

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

        I'm not sure if I understood the code correctly but perhaps its this. So first observation is that you will only use the smallest (n+1)/2 elements of the first string and n/2 largest elemets from the second. So you should never add the last element from a set

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

          I should't ever be adding the last element in the set, if it looks that way it is because I sorted the second set and am taking letters from the back

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

      I followed this strategy, this didn't work for me on testcase 5

      reddit abcdef

      This strategy gives dfdede but answer is dfdeed

      Can someone explain why? is answer for (dexy, abde) is also deed ?

      edit[2] : corrected the starting of the output

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

    My solution consisted in the following points :

    • First, you can know which letters will Egor play, because, as he wants to minimize lexographical order, it's not worth playing its «worst» letters, i.e. he only plays his (n+1)/2 lowest letters.

    • Same for Igor, who always plays his n/2 biggest letters.

    • Now, suppose it's Egor playing : his goal will be to minimize the lexicographical order, and thus he wants the lowest letter to be in front. If he has got at least one letter with lower rank than one of Igor's letters, he immediately puts it in front, because it will give him a better score than if Egor plays a largest place instead at the front. However, in the rare case where all his letters are bigger than Igor's one, he wants to play at the back of the string his biggest letter, by a similar argument.

    • Same for Igor : he will play his biggest letter at the front, except when all his letters are lower than Egor's, in which case he will play his lowest letter at the back.

    Implementation isn't really hard, it's simply important not to forget to use sets to quickly retrieve lowest and biggest letters from each player.

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

How to solve Problem D?

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

    i think graph should be linear line of compressed cliques and vertices of degree 1 and 2. i.e if deg>2 it should form a clique in combination to other nodes. else -1. but not able to code in time.

    Edit: i got the mistake. it need not be clique.
    → Reply
»
9 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

How to solve B ? My geometry is weaker than the weakest's

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

when I will be able to view answers

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

[Problem D] I needed just 5 more minutes to solve D. Anyway I solved it as follows:
1. For each city, add itself to its adjacency list.
2. Using hashing, we will use DSU to make clusters of cities with exactly same adjacency.
3. Nodes in a cluster will have the same label value.
4. For each city, modify its adjacency list by replacing all cities in it by their representative i.e for (int v: g[u]) replace v by rep(v).
5. Now if there are more than 2 cities in any adjanceny list, its impossible.
6. Do a dfs, and carefully assign values :)

I hope this is a correct solution.
UPD: Here is the code that I missed by 5 mins.
UPD2: It got AC.

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

Can anyone please share the idea to solve problem D?

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

problem C looks complicated any simple solution ?

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

Very interesting C task :D

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

Failed to handle cornercases of k={n-3, n-2, n-1} in E on last two minutes of contest having correct ideas, such a pain.....

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

    What is general idea for E?

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

      By picking element from the beginning or from the end of array you simply move its center by 0.5. Thus for fixed array answer is for even length and for odd length.

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

      Maybe I am wrong (got WA on pretest1) but:

      • if n is even then the answer is max(a[n / 2], a[n / 2 + 1])

      • if n is odd then the answer is min(max(a[n / 2 - 1], a[n / 2 + 1]), a[n / 2])

      and this twist with k is very easy to handle. [edit: to slow]

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

There's this guy in this contest whose id is sepanta and he hacked 35 times successfully..and most amusing fact is the person he hacked is Mr.Fox and he hacked him 35 times!!! the guy sepanta has solved 2 problems (A and B) and is currently standing on 42 :| what the hell???

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

rating: rest in peace

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

what is the 4th test case of problem C?

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

Explain please how can i solve B.

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

    Basically the whole triangle's area is h/2. So, each the n parts' area should be h/2n.

    So, for every cut i, you should find h(i) so that the resulting triangle has area i*h/2n. Note that if such a triangle has height h(i), that the base has length (h(i)/h). Therefore, you have to solve (h(i)^2) / 2h = i*h/2n, and the answer is sqrt(i/n)*h.

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

      "if such a triangle has height h(i), that the base has length (h(i)/h)." - can you please explain me why the base has length (h(i)/h) ?

      Thanks in advance.

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

        You can use Thales theorem to prove this, since cuts are parallel to the base.

        Let b the length of the base you want to compute. Then h(i)/h = b/1.

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

Anyone please help me to solve B?

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

Quite fast system test today..

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

Fastest system testing I have ever seen :O

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

Ultrafast speed of systest <3

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

Amazingly fast system testing

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

Fastest System Testing ever !!!

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

what's the answer of s = "ddd", t = "aaa" for problem C ?

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

Why did my code got TLE? Complexity looks fine to me — CODE

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

How to hack B?

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

Could someone please explain to me why in Test Case 4 (abc aaa), the answer is aab?

I feel the answer should be aba, because Oleg will place 'a' at Position 1, then Igor would place 'a' at Position 3 because he wants the string to be lexicographically large, so Oleg will be left with Position 2 and he'll place b at Position 2.

Thanks in advance!

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

27081526 In this submit time equal 405ms, but it got verdict TL. How it could possible?

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

pls anyone could explain me why the answer of the test Oleg's reddit and Igor's abcdef is dfdeed but not dfdede ? (test 5)

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

Can anyone please explain the output of this test case in problem C.

reddit

abcdef

Expected answer is this --> dfdeed

My answer --> dfdede

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

    So, the answer will be of 6 letters. letters for optimal answer- {d,d,e} and {f,e,d} Steps are :- 1)d????? 2)df???? 3)dfd??? 4)dfd??d 5)dfd?ed / dfde?d 6)dfdeed

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

Fastest system test, and fastest rating update ever, nice round :D

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

How to make a segment sum tree with range updates and range queries? I'm asking for problem F, to maintain a segment tree for every digit that have sums like that digit was 1. :)

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

Can problem F be solved with DSU on Segment tree? I tried really hard but still in vain with TLEs. It seems like it can pass in time if I change long long to int, but of course with WA.

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

I submitted two codes one with long double (code) and one with double code.

double got AC and long double got WA on test 1(though it works perfectly on my machine). I always have a rough time with doubles. Am I missing something? some compiler issues?

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

Why ratings are updated without removing cheaters?

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

In problem C can someone explain test case:

reddit
abcdef

The answer is:

dfdeed
  • Oleg plays with letters dde
  • Igor plays with letters fed
  1. Oleg plays: d?????
  2. Igor plays: df????
  3. Oleg plays: dfd???
  4. Igor plays: dfde??

So why would Oleg now play dfdee? — it is not optimal for him?

He should play dfde?e.

So Igor must play: dfdede

For Oleg dfdede is better than dfdeed?

UPDate: got it

Step 4. Igor plays: dfd??d forceing e on the 4th spot.

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

Now that this round is finished, when will you announce the random playrix t-shirt winners ? KAN

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

In D tests does not check for overflow in clique check.

This AC submission http://mirror.codeforces.com/contest/794/submission/27090233 would fail for almost every graph with n = 65538, m = 98305

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

Hello guys ! Can someone please help me in problem C. A test case : abc aaa . In the first turn the first player will put 'a' in the first place,then in the second chance the second player can put 'a' either in the second place or in the third place. According to the solutions which have passed they put it in the second place. But i think it will be more optimal to put it in the third place. this way it would be lexicographically bigger from the second player's point of view. Can somebody please explain this to me ?

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

    No. The optimal strategy for the first player is to place his letter 'b' to the last position on the first turn.

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

    As it was written player can place their letter anywhere instead of question marks. So the first turn of Oleg is to place the 'b' at the end. Then, as the biggest letter in Igor's set is 'a' he will place it also at the end. Then, the Oleg's turn is to put 'a' to the first letter. Consequently, the answer is 'aab'.

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

Could anyone explain me the last input-output example of problem D? Although there is note under the example, I can't catch its point.

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

I am getting TLE for 11 test case for problem C in nlogn. Still it gives TLE. My Submission : http://mirror.codeforces.com/contest/794/submission/27085787 Can anybody please tell me reason for that. Thanks

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

    27115362 Here you go.

    Basically you TLE because of these lines.

        for( i=0;i<n/2;i++){
        sm=sm+a[i];
        lr=lr+b[i];
    }

    these operation are n^2 instead of n as you recopy the whole string each time. you need to write it as

        for( i=0;i<n/2;i++){
        sm+=a[i];
        lr+=b[i];
    }

    instead.

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

Everybody's rating was back to that before the contest for a moment to ban sepanta.

Anyway, justice was done. Well done, Codeforces!

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

I tried to solve the problem E.**Leha and security system** https://pastebin.com/haK2wtvr upon submission I am getting run time exception with Exit code is 1

Can anybody help me to figure out what went wrong. Thanks in advance.

→ Reply