Ne0n25's blog

By Ne0n25, 5 years ago, translation, In English,

Hello, Codeforces!

I'd like to invite you to Codeforces Round #298 (Div. 2). It will be held on Sunday, April 12 at 19:00 MSK and Div. 1 participants are invited to join out of competition.

Problems have been prepared by Maxim Mescheryakov (Ne0n25) and Danil Sagunov (dans). We hope you'll find them interesting.

Great thanks to Maxim Akhmedov (Zlobober) for helping us preparing the contest, to Maria Belova (Delinur) for translating the statements into English, to Mike Mirzayanov (MikeMirzayanov) for the great Codeforces and Polygon systems and ideas of some problems. Also thanks Vitaliy Aksenov (Aksenov239) for writing solutions.

You will be given six problems and two and the half hours to solve them.

UPD: Scoring system 500-1000-1500-2000-2500-3000

UPD2: Competition completed! Thank you all!

UPD3: Congratulations to the winners!

  1. xuanhien070594

  2. misis

  3. Mikagura_Seisa

  4. plem

  5. 11111111

UPD4: Editorial here

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

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

Why minus ? When I wrote this comment, scoring system wasn't announced. Also there wasn't even a " scoring system will be announced later " message

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

    I'm not a racist, but just because of your color :D

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

Scoring system will be announced later :/

»
5 years ago, # |
  Vote: I like it -25 Vote: I do not like it

It should be Dynamic Scoring :)

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

    So , people don't like dynamic scoring??
    Every new thing is hated in the beginning :p

»
5 years ago, # |
Rev. 8   Vote: I like it -38 Vote: I do not like it

Ok,you are right

»
5 years ago, # |
Rev. 2   Vote: I like it -15 Vote: I do not like it

:) Good luck

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it
»
5 years ago, # |
  Vote: I like it -6 Vote: I do not like it

I think it will be a good contest wish succes for every EXPERT

»
5 years ago, # |
  Vote: I like it -21 Vote: I do not like it

i hope you all know who is going to win this round!

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

Specialist Let's Muster...

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

So is there a dynamic scoring system or not? Does this mean that if I submit a 2000 point system even almost at end of contest, I get 2000 points if its accepted?

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

I hope to participate in Round #299 with (div.1) :)

»
5 years ago, # |
  Vote: I like it -9 Vote: I do not like it

six problems.Time duration 2.5 hours.

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

Coding Time

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

GLHF guys :)

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

    Sadly Codeforces system seems not working properly as my submission gives wrong ans before starting evaluation :(

»
5 years ago, # |
  Vote: I like it -23 Vote: I do not like it

The statments was very dificult to understand. problems are good but it takes very large time to understand a problem. Agree : +1 Disagree : -1

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

    Disagree -1 XD
    It's so clear to me. But I can't solve problems. I'm a noob :(

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

      I will see you soon.......
      Every body, Ehsan.poursaeed wants that you give me -1 and give him +1. see his conspiracy. Don't give him +1. but if you like give me -1

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

The pretest #15 of problem E doesn't have the visited stop list sorted. This costs me 45 minutes :( Was any one affected by this?

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

I liked the problems :)

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

How to solve second problem?

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

    It's dynamic programming. DP[current second][last speed]. But I spent a lot of time on understanding the statement.

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

      You don't need the dynamic programming. You just need to run from zero to t and update the speed using greedy approach. Check out my solution.

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

        Exactly. You just need to always increase the speed until it's possible to get to the required final speed in the remaining time.

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

    V increasing while we can decrease V to Vlast

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

      I think this idea in contest,but can't implement.How to implement?

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

    print(sum(min(v1 + d * i, v2 + d * (t - i - 1)) for i in range(t)))
    increase our speed as fast as we can. Also with decreasing
    (can't code without brackets highlighting :( and forget we need sum it, not print :( )

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

    This problem can be solved without using dynammic programming .. just traverse first from left to right and then right to left maintain minimum of both side at each second . sum them up :)

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

    if v1 + (t-1)*d <= v2, we know the best way is to increase the velocity by d every second. Otherwise, the speed would first increase to a top speed, let's say Vmax, then decrease to v2. We can enumerate the top speed Vmax to find the answer.

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

    maintain 2 arrays of size t.

    first has first element as v1 and contain maximum speed that can be attained at any time by increasing previous element by d.

    second have last element as v2 and contain maximum speed that can is possible at any time by increasing later element by d.

    example- if v1=10 and v2=30, t=5 and d=4

    array1- 10 14 18 22 26 array2- 14 18 22 26 30

    add elements from array1 to answer untill array1[i]<=array2[i], then add elements from array2.

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

    int main(){ int v1,v2; cin >> v1 >> v2; int t,d; cin >> t; cin >> d; int ans=0;

    while(t--){
        ans+=v1;
        v1=min(v1+d,v2+((t-1)*d));
    }
    cout << ans << endl;
    return 0;
    

    }

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

    you only need know how far is your v2:

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int main()
    {
      int rem,v1,v2,t,d;ll ans;
      cin >> v1 >> v2 >> t >> d;
      rem = v1;
      for(int i = 0 ; i < t-2 ;++i)
        {
          int max = v2 + (t-2-i)*d;
          v1 = (max > v1+d ? (v1 + d) : max);
          // cout << v1<<endl;
          ans +=v1;
        }
      cout << ans+rem+v2 << endl;
      return 0;
    }
    
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i did it without dp.... simply take a array 'A' of size t; A[1]=v1; A[t]=v2;

    for<- 2 to t-1 A[i]+=d;

    and traverse from back and check if abs(A[i]-A[i+1]>d) make abs exactly d...by changing A[i];

    then add all A[i];

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

    You can solve it by 2 pointers..

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

      arr[0] = v1; arr[t — 1] = v2; int s = 0, e = t — 1; for (int i = 0; i < t-2; i++) { if (arr[s] <= arr[e]) { arr[s + 1] = arr[s] + d; s++; } else { arr[e — 1] = arr[e] + d; e--; } } ll ans = 0; for (int i = 0; i < t; i++) ans += arr[i];

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

How to solve D? I think that I got the idea but I had 4 unsuccessful attempts. I know that we have to change the remainders in order 0-1-2-0-1-2-0-1-2-... but maybe I implemented it wrong.

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

how to solve problem D handshakes ?

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

    Bipartite matching !!

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

      can you please explain the idea ?

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

        let's suppose the entering position are from 0 to n-1...

        since a team of 3 can be formed, so in general student with 'i' handshakes can go at positions i,i+3,i+6,i+9... (because additional 3's can form a team resulting in 'i' handshakes).. (make edges correspondingly to form bipartite) so Now the question reduces to bipartite maching of n students with n positions.. :)

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

    My kind of brute-force algorithm couldn't pass pretest 9 but I think the idea is correct.

    Store the people in an array of vector, where vector v[i] stores people shaking hands with i people, initialise current index of all vector to 0.

    Now start from 0, if current index of v[0] is less than v[0].size(), it means there is a person that can enter now.add this person to solution vector, increment 0 to 1 and repeat.

    If, current index becomes >= v[i].size(), then check for current index that are possible, eg. for i=7, other states possible are 7-3=4, 4-3=1 and so on.If you cant find any valid state that has current index < v[i].size(), break out of loop.

    Edit: The idea is correct.It passed the system test after removing a stupid bug.

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

      Umm i seem to getting a TLE on #72. Encountered such a problem? Have a look at my post

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

    We only need to simulate the whole thing. But, we postpone groupings as late as possible.

    Let's say there is X ungrouped people and next one comes. First check if there is exists (remain) a person who shake hands with X people. If yes, allow him to shake hands with X people and add 1 to current no of ungrouped people.

    If not, form a group and try again, no of hand shakes becomes X = X - 3. Repeat if necessary. If ultimately not possible because there is not enough people to form groups anymore, output Impossible.

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

      Ditto approach. I seem to be getting TLE on #72. Could you have a look at my post at the bottom?

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

    D solution:

    Simple greedy: take the largest numbers first, e.g. 0 1 2 3 4 5 6 7, 5 6, 2 3 4, 0 1 2.

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

      Ok, How is about 0 1 2 3, 0 1 2 ?

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

        Oh, I understand. You try to increase number of people at first.

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

    I solved with greedy :D

    200000 stack

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

If in Problem 'A' n=4 testcase was not included in pretests, no. of hacks could be more!!

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

I see several people, including me, failed on system test 50 for problem C. Any idea what it may have been?

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

    Your A must be define as a long long... I have hacked 9 people like you :)

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

      Ah, seriously. I changed it to int when I uploaded it, since I thought it wasn't necessary and might have slown down the solution.

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

      but there written n,A <= 2·10^5, in test 50 A is 99964566758, am I misunderstand something?

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

        n ≤ A ≤ s , not 2 × 105

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

          I have changed all variables to long long, except n, A((. thanks

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

      I think A is not necessary to take as long long, rather sum in his case. Thanks. :)

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

    You have declared sum as int, but if I give you 200000 times 1000000 as d? Then the power goes to 11. Thanks. :)

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

I have done 4 problems and in my view, the difficulty level was C,D,A,B. Problem B just ruined my contest. -_- However, I have enjoyed the problem D very much. Thanks to the Almighty, thanks to the problem setters, thanks to all. :)

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

Can somebody explain why http://codeforces.com/contest/534/submission/10677423 submission passed test case no 50. The coder in the above solution has used int type for all the values and is still successfully dealing with large inputs. HOW? Costed me a unsuccessful hacking attempt.

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

    X + Y — Y would always result in X even if overflow occurs.

    As you can see in case 50 the answers are equal to the input.

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

Nice problem set can't wait to see tutorial of D

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

Is something with std::set solution wrong or just mine is incorrect (why?)? I got TLE on test #46 ;-; http://codeforces.com/contest/534/submission/10685572

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

    you used std::lower_bound, which has linear complexity
    use set::lower_bound and you get AC: 10685831

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

    use s.lower_bound(x) instead of lower_bound(s.begin(), s.end(), x)

    This have been discussed many many many times in Codeforces

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

      Thank you so much :)

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

      Could you refer me a blog where this has been discussed?

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

        I've seen this discussion couple of times on similar situation: some guys ask why his solution fail, another reply that lower_bound(s.begin(), s.end(), x) has linear complexity. But it's hard to find comments, so I can't give you links.

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

          I couldn't find anything on google search as well.Maybe we can formalise it here. So what it means is that lower_bound(), upper_bound() have linear complexity(I highly doubt that) but s.lower_bound(x) has O(logn). But I have passed programs having O(n*logn) with n<=10^6 using lower_bound().If lower_bound() is linear then complexity would have been O(n^2) (impossible to pass).Is this valid for set only or is it true for vector, array also?Is its complexity based on array configuration or what?

          And one more thing, as far as I know c++ stl is highly optimised. So how come lower_bound() is linear, because I sure can implement this in O(logn)?

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

            I'm pretty sure lower_bound() is O(log) for vector and array (but of course it is assumed that the vector/array is sorted).

            The thing with lower_bound() on set is that, you do not have random access in O(1), so probably it was implemented in a way that makes it O(N). I think it is stupid design of this C++ STL that allows people to use the library wrongly like that.

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

    I have a TLE on system tests, but I used 3 smaller multimaps(each element only in one multimap, depending on shakes[i]%3 and I cycled between them) and used insert, lower_bound ( s.lower_bound) , erase, empty operations. What could go wrong? Isn`t is supposed to be N*log N solution? Or is it not good enough? http://codeforces.com/contest/534/submission/10675989

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

      You gave link to another solution.

      For your D, it looks like good, but it gets TL on N=113 which is weird. I ran your solution locally and it spits error in free(). I guess it's because you access myit while lower_bound can return a.end() (so myit does not point to an element) and then you erase myit -> undefined behaviour. Very strange it gets TL on CF...

      Add check myit != a.end() and I hope it will pass.

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

        Thank you. Changing one of "Impossible" conditions from (a.empty()) to (myit == a.end()) helped. It was my first time using map, I will watch out for it in future.

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

فارسی زبونا همیات کنین

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

Why this solution gives WA for problem-B? Plz, help me--> 10682655

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

    When calculating DP you are setting your initial ret value to be 0. However, your recursive call can return you negative infinity, because there is no solution. Since you update ret to be a max of a previous ret value i+get(...), you lose that information. So for a state that doesn't lead anywhere, you will return 0, which is wrong. As a result, when the correct solution is 1+2+3+4+5+6+5+3+2+1, your program can do 1+2+3+4+5+6+7+8+9+0 (10 can't reach 1, so we use 0).

    Change line 50 from ret=0LL; to ret=-inf; and you'll get an AC :)

    Good luck!

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

D:Different teams could start writing contest at different times. the number of student -3 or -3*t(t=1.2...) it take me long time to understand the problem

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

Where can I find the rules for the scoring? Thanks in advance.

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

Thanks for the problems. It was a great contest with very nice problems.

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

Can someone explain why my code for C TLEd? http://codeforces.com/contest/534/submission/10682828 Shouldn't it be O(n)? Or do you need to somehow print more efficiently?

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

    As far as I can tell you just need to switch to faster i/o methods.

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

    Scanner.nextInt and Scanner.nextLong() is REALLY slow. You should use Integer.parseInt(sc.next()) and Long.parseLong(sc.next()).
    If it is not sufficient, you must implement method to parse integer.

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

For problem A — Exam why is the following output wrong for input 6?

6 Output 5 2 4 1 3 6 Answer 6 5 3 1 6 4 2 Checker Log wrong answer Jury has better result: 6>5

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

When will the editorial be published?

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

Is there a problem with submitting? Why can't I submit now?

Edit: It is fix.

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

I seem to be getting TLE on case #72 of problem D: Handshakes. I am using a Hashmap<Integer, ArrayList> which stores the keys as hand shakes and indexes of people in the arraylist. Code runs perfectly. Its based on the same idea as @_spartan has written. Any optimizations?

Edit: As hellman1908 suggested, the complexity increases. So i changes the ArrayList to a Stack since the order does not matter and VOILA, AC :D

http://codeforces.com/contest/534/submission/10687311

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

Is there any editorial links for the contest? sorry if I missed one thanks :)

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

How to solve Problem 'A'?

What is Logic behind it?

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

    Adjacent elements should differ by at least two, so if you enumerate first the odd numbers and then the even numbers you have a correct solution. For example, n = 5: 1 3 5 2 4

    This algorithm doesn't work when n < 5. In these cases, solve it on paper and hardcode into your source.

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

      Thanks

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

      it is actually works n < 5 except the fourth :)

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

        n = 2 (1, 2), n = 3 (1, 3, 2) does not work also.

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

My accepted solution for Problem — 'C' used binary search: http://codeforces.com/contest/534/submission/10684361. As far as I can see, no one else had used binary search to solve this problem. I am not able to digest this. What obvious thing am I missing?

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

    Probably you would do better if you think the problem in two cases: + when all the other dices do their best + when all the other dices do their worst (summing 1 each)

    this give you a range of points you need on the a_i dice you are working on (once at a time), and of course tells you the amount of points (or faces on the dice) that you will never see to accomplish A points.

    Hope this helps http://codeforces.com/contest/534/submission/10679438

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

      I applied exactly the same concept as you are mentioning, if you look into my code, it's doing the same thing — finding minVals for all dices and then maxVals for all dices.

      To get those minVals (and maxVals), I have used binary search (and you are saying that the minVals would simply be 1 for each die). Can there not be a case when the minVal for a die be more than 1? (I could not come up with a proof that there cannot be such a case. If someone has any, then please let me know.) To be certain of the correct answer, I used binary search to get the minimum values for each die and then the maximum values..

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

        think about this example

        1 8 9

        I hope I am getting your point, but if you are asking for a counter example where the lower value a dice MUST have this is the easiest case, obviously your lower value is 8, so your upper value, giving you 8-8+1 possible valid dice' faces (thus 9-valid = 8 not used faces).

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

    you did the same job as others! but your time complexity is O(log(n)) and other's is O(1)

    :D

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

Great round, I like how many variants people wrote to solve problem D, really creative.

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

In case of Problem-B it is given "the absolute value of difference of speeds between any two adjacent seconds doesn't exceed d."

and this also " Assuming that at each of the seconds the speed is constant, and between seconds the speed can change at most by d meters per second in absolute value "

so for first case is it also possible that speed will be constant after 2 second I mean 5+6+6+6=23 2nd second value change by 1 and after that speed not change could be answar

Am I wrong?

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

    You are right, but the task wants you to output maximum possible value, and your 23 is certainly less than correct 26.

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

      Ok I got it "maximum possible value"

      I missed this phrase

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

How to solve the problem F? Who can help me ?

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

    Notice that in a given row there can be maximum of 10 blocks (because we have at most 20 columns, and each block must be separated from next and previous block by at least one free cell). Also notice that we can encode any tiling by m integers as bitmasks (so that 0-th bit of every integer gives us the first row, 1-st bit gives second row, and so on) up to 25.

    Given that, let's do dynamic programming: dp[num_placed][r1][r2][r3][r4][r5][last] = true or false. It means, that we've already filled num_placed leftmost columns, and we must build r1 more blocks in first row, r2 more blocks in second row, ..., r5 more blocks in the fifth row; and last is the bitmask of last placed column. Let's estimate number of states: 21 * 115 * 32 = 108. Not all possible states are reachable.

    Instead of doing dp, I've made a backtracking, because it effectively visits all reachable states, with memoization it is done only once, and with some heuristics (for example, if we must place 5 blocks in some row and there are only 3 columns left, we can say 'goodbye' to this state immediately) it works even faster.

    But if you prefer dp approach, the main observation here is to encode [r1][r2][r3][r4][r5] as a single integer in numeral system base 11 (because each ri have possible values from 0 to 10), that makes coding more convenient.

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

      oh!Thank you very much.Your analysis is so distinct.And the search with memoization is more convenient to write.

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

In case of Problem-C

for the case 2 3
2 3

will not answar be 1,1

instead of 0,1 If second dice could not show 3 then this condition also apply for 1st dice too can't show 3 also?

I think then s=d1+d2+d3...dn condition will not satisfy

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

    1st dice cannot show 3 by definition: d1 = 2, so it can only show 1 or 2 (but not 3, 4, 5 or any greater value).

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

      by mean defination you mean this line?

      "s = d1 + d2 + ... + dn."

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

        No, I mean second sentence from the problem: "The i-th dice shows numbers from 1 to di".

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

Tutorial ?!

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

    What was this word "Tutorial"?

    Let's hope that the author haven't posted it yet because he wants to make it more understandable and detailed :)

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

Please anyone tell me , why this solution for problem-D is WA on test-9 ? Isn't it a correct order ?.. Sol:-> 10692139

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

    No, it isn't a correct order because if 2 shakes hands with 0 guys, then 7 will shake hands with 1 guy instead of 4 guys :)

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

Think Problem A pretests without test 5 -> Hacksss :)))

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

My code in problem 534D - Handshakes got AC 10687529 but when I try the test case n=5 - [0 1 2 0 4] it's output is Impossible but it should be possible 1 2 3 4 5 How come?!!!!!!

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

    No, it is impossible. If 4 handshakes with nobody, then 5 could not handshakes with 4 people. "At any time any three students could join together and start participating in a team contest, which lasted until the end of the day. " "so when another student came in and greeted those who were present, he did not shake hands with the members of the contest writing team." You assume the 1 2 3 formed a team so 4 handshakes with nobody then 5 can only handshakes with 4. So it is impossible. Sorry for my bad English

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

      I was misunderstand this part of the problem.. thanks :)

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

    If the 4th person shook hands with 0 people, how could the 5th person shake hands with 4 people?

    The answer is indeed Impossible.

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

where are the editorials

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

Please publish the editorials for the round!!

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

How to solve Problem-D

I mean from where I should start?

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

    First,You should count a[i]. a[i] is the number of students who shook hands i times. We define cur .cur is the number of student who we can shake hands with now. In the beginning cur=0.

    1. if a[cur] > 0 , it tells us we can add a student who will shake hands cur times in the permutation.And than a[cur]--(because we use a person)

    2. else cur-=3 (3 student start writing a contest) until (cur<3 or a[cur]>0)..

       2.1 if (a[cur]>0) is same as 1.

       2.2 cur < 3 it means the sought order of students doesn't exist.

    My english is very poor. You can see my code 10681578..I hope you can deal with it!

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

Here is the editorial, but for some reason it is not attached to the contest

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

Sorry,wrong contest.

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

hello I am tired , trying D problem

someone can help me !!!!! why does it give me runtime error on case 46 ??? 10733747

that is my code

thanks for advance everyone