Vladik's blog

Codeforces Round #321 (Div. 2)
By Vladik, 11 years ago, translation, In English

Good day to everybody!

The next round for the participants of the second division will be held at September 22, 2015 at 19:30 MSK. Traditionally, the members of the first division may take part in the contest out of competition.

I (Vladislav Vishnevski) and igdor99(Igor Doroshev) are the authors of the round. We would like to please Zlobober (Maxim Akhmedov) for the assistance in the preparation of tasks, Delinur(Maria Belova) for translating statements into English, MikeMirzayanov(Mike Mirzayanov) for remarkable systems Codeforces and Polygon, as well as our friends daksenik(Dmitry Aksenik) and irevt(Ivan Revt) for their assistance in the round preparation. This is our first round, and, we hope, it won't be the last one!

You will be proposed 5 tasks and 2 hours for their solution.

The protagonist of the round is the parrot Kefa, who likes money and restaurants.

Good luck and high rating!

UPD: The scores — 750-1250-1500-2000-2500.

UPD: Editorial!

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

Comments Comments (158)
| Write comment?
»
11 years ago, hide # |
 
Vote: I like it +20 Vote: I do not like it

3..2..1..Go!

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

Summary: Vladik and igdor99 would like to please Zlobober, Delinur, Mike and RevtIvan. It looks like they will have their hands full for a while.

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

    I'm sure they will all be pleased if the round goes well :)

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

      I assume Jefe tried to go for an obvious innuendo. I learn more about CF community every day.

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

        In part I wanted to point out they made an English mistake, swapping "Thank" for "Please".

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

Why no div1 :/

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

And in the hope ... that i shall get some hacks :D GL & HF :)

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

Oh it will be a magical round.

P.S : Please see the tags.

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

thanks for magical contest about parrot KEFA)

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

Do you mean Kefa ?

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

i just want raising rating .......

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

hope to see hard math problems :)

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

Div. 1 guys do not make new accounts please. :)

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

    Toooo_Simple

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

    Why did you make a new account then ?
    You're unrated and you know that some of div1 contestants make new accounts and you know the whole story, Then definitely you're not new to Codeforces and I can say that you already have another account!

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

    Why did you?

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

I hope that it does't be dynamic. How about you? Do you agree with me?

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

we want div.1 contests .

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

My last contest in summer! I'm going to school on Wednesday! Hope a good contest! Good Luck!

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

I am no longer scared of fake contestants. If my rating goes down, its because I suck, and not because of anyone else.

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

Hello my friends ;)

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

Scoring will be 500-1000-1500-2000-2500?

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

In my whole country adsl is down. I'll be solving this contest on mobile net :)

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

750 points for div2 A :| from where that it cant be very nice i think it will be a long boring brute force :(

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

Why doesn't codeforces allow a little bigger hack files? There are solutions that will get time limit exceeded when the constraints are used but the files are bigger than 256 KB.

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

MLE on pretest 1 in D :(

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

What for the sake of God is wrong with pretest 9 Div 2 C?

Isn't it finding the longest non zero subsequence from an arbitrary vertex I with no childs?

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

A lot of pretests, yet smooth system testing and no issues. Really nice contest.

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

How to solve E problem?

It was so interesting.

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

how to solve E ?

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

Pretest 9th for C ?

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

I was unable to submit in the last 60 seconds because codeforces was too busy. I hate it when that happens.

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

    And I was unable to hack in the last 60 seconds.

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

    Same here :/ I tried to hack in the last 20 seconds, but the challenge wasn't submitted.

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

    same as your problem :|

    solved D but It didn't submited, also in previous contests I have this problem too!!!

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

    Блин решил последние две задачи а кодфорцез затупил и я не сумел послать(((((((((( уверен, это дело рук красных они бояться конкурентов и поэтому зажимают F5 на последних минутах и кодфорса ломаеца. предлагаю ограничивать красным доступ на сайт на время контестов.

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

I don't like problem scores!!! u think difference between problem C (or B) and D should be ONLY 500 (or 750).than it's same to solve A+B instead of D. May be my fault coz I solved only A,C,D(coz of not enough time),but anyway I don't think that this correct: man who solved first 3 problem is in front of me in list... D is much harder than A+B+C -_- sorry for my open mind

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

What's the problem with code generated tests ? I've got this one:

Validator 'valid.exe' returns exit code 3 [FAIL Expected EOLN (stdin)]

Thanks in advance.

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

Is there anything need to pay attention to in the C problem? I failed to pass the 8th test and i can't find any mistakes.

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

Can someone suggest an approach for 2nd? I basically sorted the friends based on their money, and I was then going to group friends based on the condition and sum their friendship factor, and check which group has the most. Is there a better way to do it? or any flaw in my solution.

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

    you can read about the two pointer technique , and try solving the problem.

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

    Firstly,sort the friends based on their money.Then,enumerate every element in array and use the function "lower_bound" to find the first element which is bigger than the it.And use the sum of factor between the two element to update your answer

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

    1) sort based on money

    2) find prefix sums for friendship factors

    3) for i=1 to n
    a) use any O(log n) mechanism to find index j such that money[j]>=money[i]+d ... I used c++ map for this.
    b) ans = max (ans,prefix_sum[j-1]-prefix_sum[i-1])

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

      I had the same solution. Used std::lower_bound(a + i, a + n, a[i] + d) to find the least index ahead of i which I can not select, if I select i.

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

      Index j is also invalid so why are you doing prefix_sum[j-1] and not prefix_sum[j] ?

      Am assuming that i > j as we are considering the ith element and the old set if in [0..i-1]

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

        Assume your set starts from i. We have sorted in ascending order of money so j>i because j is the lowest index you need to exclude if the set starts from i such that money[j]>=money[i] + d ... you can set money [n+1] = INF ... Include all elements from i to j-1 in current set and to get the sum of friendship factors of such ranges/sets of in O(1), I pre-calculated prefix sums. To get sum of elements from i to j-1, you need to subtract prefix[i-1] from prefix[j-1].

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

    Sort + Two Pointers O(nlogn)

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

Can someone explain D soln ?

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

Went out and could not fully participate in contest. Too bad!!!.

My thinking of how to solve Div2 B.(not sure if its correct)

  1. Sort set S by amount.

Suppose we have <n=k people already to be a company. They are K-1 of them in number.

Consider the Kth person.

Case 1 : He should be in company. This is only possible if this amount is a < S[0].a That is it is smaller than the amount of the smallest person in the group.

Case 2: His amount is bigger.

In this case, we can use binary search to find a range of numbers that conflict with the Kth person, we sum the total factors of this said group.

We have to choose between the whole group and the Kth person. Which ever increases the overall amount.

Please would this have solved the problem???

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

Can't wait to see the rating change!!!

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

were the test case for 2nd question weak because i used upper_bound instead of lower_bound in hurry and i got AC? :P

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

I have this idea for D. Please tell me if you find something wrong in it.

  1. Use bitmask to find numbers with m set bits.
  2. From the k-rule directed tree, form a directed sub-tree which has only the vertices identified in step 1. Add their individual satisfaction values.
  3. Start from leaf nodes. Push them in a queue. Pop only if all children of the vertex have been popped. This way, do a Comparison for every non-leaf vertex to pick the child path that gives maximum satisfaction. So, along with all child-path satisfaction values, you add only 1 extra value for joining vertex v to its max satisfaction child.

Is it correct to start from leaf nodes?

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

Oh my god, i have disastrous bugs :'( i will cry in the bathroom.

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

I assumed that input was (parent, child) on C!!! ... silly mistake.

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

I agree with everything above and confirm that I will provide my own problems

Just a quote regarding D.

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

How can we solve problem B if every friend was associated with hia own value of 'd', the value that makes him feel poor.

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

Nice problem ( E — Kefa and Watch ). I found a solution using hashing + segment tree, but couldn't solve it in time. BTW is there any solution without using hashing?

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

kuldeepfouzdar nice trick for Unsuccessful hacking attempts on your solution, in the problem B:

#define int long long

http://mirror.codeforces.com/contest/580/submission/13163755

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

Hello all,

I have a question about an unsuccessful hack that I did during the contest. I hacked the following submission as I noticed that the numbers of the sequence are stored in indices of an array starting from 1 to n. The array is of size n and hence I expected that the hack will result in run time error due to the index overflow for a large input where the size of the sequence is 10^5.

Can anybody explain to me why did the hack fail? I expect it might have something to do with the unused array f but I am not sure about it.

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

    C++ doesn't have index overflow run time errors, all that happens is that it accesses memory outside the array and as long as said memory is not used for something else it will pass.

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

How come 300 div2 participants managed to solve D? In my opinion it was a pretty hard dynamic programming problem.

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

    Really ? I think that's the basic form of bitmask dynamic programming though

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

      Basic bitmask would not have arbitrary transition rules, most in div 2 fails at problems like this. I think its strange that it was solved by as many div 2 participants as this problem which is much easier:

      http://mirror.codeforces.com/contest/574/problem/D

      This problem is also easier and was solved by just 100 div 2 participants:

      http://mirror.codeforces.com/problemset/problem/540/D

      So I'm just wondering: what makes this problem easy?

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

        Rather than "easier", I would say it is more well known

        IMO, one of the most basic problem for bitmask DP is finding shortest path to travel through all vertices in the graph which is completely the same as 574D, except that the answer lie only in status 2^n - 1

        P/s : this is the first bitmask DP problem I learned so it can be just me

        UPD: I've seen some tutorials about bitmask DP (just google search, you'll find them) use above problem as sample to solve so it should be well known

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

          Ah, I see! Thanks! I had just seen it for things like edit distance and knapsack and those are way easier.

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

    Future div1 participiant ;)

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

Stand-up contest)

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

Really nice contest, can't wait for your next one.

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

When will the solutions be uploaded?

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

so many O(m(n+k)) solutions passed E 13198157

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

In Problem B, I think it should be "Print the maximum total friendship factor that can be reached." in the Output statement.

→ Reply