Nerevar's blog

Codeforces Round #274
By Nerevar, 10 years ago, translation, In English

Greetings to the Codeforces community!

Yet another Div1+Div2 round will take place this Sunday, 19th of October at 13:00 MSK.

The round is based on the problems of the regional stage of All-Russia team school competition, which will take place at the same time in Saratov. We are aware about the overlapping with Opencup, but we have no option to shift the round, because we are bounded to the local event.

The problems were prepared by HolkinPV, gridnevvvit, danilka.pro, Avalanche, IlyaLos, Fefer_Ivan and me.

Scoring: 500-1000-1500-2000-2500 (both divisions).

UPD: Editorial is published.

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

Comments Comments (162)
| Write comment?
»
10 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I feel and i am sure that this round will be great and interesting :D

However, Unfortunately I wouldn't be able to participate in it because of its timing :\

May be I will try it as a virtual contest later in the evening :D

This might be good for my rating, I have just been a candidate master with only 9 points ;) :D

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

I'm sure that this round will be interesting too. ^^;

good luck for everyone!!

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

I wouldn't be able to participate in it because of its timing too.

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

ICPC rules?

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

    codeforces rules.the contest's email mentions it.

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

      you're right, codeforces rules! :)

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

And I would like to thank MikeMirzayanov and Codeforces team for this fabulous platform. :)

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

Maybe a little off topic, but due to the timing I'm really hoping for a 3-0 SSW sweep at world finals.

Context

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

a Russia's contest again !!!
Nerevar,thank you !!! your last contest had good problem :)

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

OPPS! I have to miss this contest. Unfortunately it will be at my EXAM time.

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

    You can actually miss your exam for codeforces round because it is more important. sorry for my bad english.

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

    Exam on Sunday? Quite strange. Sunday is generally a holiday.

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

    You can virtual participate in this contest when you are free, though it is unrated for virtual participating.

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

My first Div. 1 contest!! :)

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

"To wake up at 5 am, or to stay up until 5 am, that is the question!" -Hamlet, adapted

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

    I think that second option is much less painful, though the first one will result in better performance.

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

    2b||!2b

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

    Well, I just woke up at 5 am. (You could never stay up until 5 am :D)

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

The comment is hidden because of too negative feedback, click here to view it

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

I have registered but how to watch the questions?I am unable to get it last time when I entered.Where should I check for the question at the contest time?Please help me.

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

    Now the contest is pending... So you can't watch the problem now. After about 3 hours the contest will start. You can participate it if you have register this contest.

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

    Just visit this when the contest starts Codeforces Round 274 (Div. 2)

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

Good luck to every one!!! Its time to coding! Just believe! You can increase your rating! All of we can be grandmaster just we must trust! We must practice! We must start to solve difficult question! If we try to solve more difficult question solving question A B C will be easy! Sorry for my pure English. I wont to give some motivation sentence. Indeed person is able to do every thing. Just we must believe us.

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

    Sorry for my pure English

    I forgive :D

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

    Pure means perfect. I think you misuse it. May be you wanted to say Sorry for my bad/poor English. BTW never mind :) We should learn from our mistakes :)

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

Thanks perfect time for me, hopefully for some others also. More contests at the same time please ;-)

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

    And I problems were also interesting, great contest today. I had a little problem to understand C today, but that's my problem only...

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

It's 5PM now in China, and I'm quite hungry now..

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

Wrong answer in B problem — Div 2. For the third example the answer should be 3 2, not 3 3: 8-3-2-6-3 1)7-3-3-6-3 2)6-4-3-6-3

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

    There's no requirement that the number of operations used is minimum.

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

      Oh, thanks! I'm sorry for the stupid question!

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

      but 3 2 must be right also as 3 3! is it really so in test system?

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

    This problem took me 20 minutes. I misunderstood it. I thought like you that the second number should be minimal. And then I saw this example... . It took me far more time to see that second number shouldn't be minimal.

    → Reply
»
10 years ago, # |
  Vote: I like it -47 Vote: I do not like it
The comment removed because of Codeforces rules violation
→ Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Good bye yellow color!

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

Can't understand how to crack another participant's submissions. no button, no link...

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

    You have to lock your problem first on the Dashboard page. Only then can you hack other solutions.

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

Why wasn't I able to copy-paste my hacking input(that I had generated seperately) to hack another solution ?

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

    You cannot do that if the input is so long, you have generate input when you try to hack.

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

    there is a file upload option also, you could use that.

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

So the intended solution of C Div1 was an O(n^2) DP?

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

    i think it is, cuz my solution with segment tree was hacked

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

    My solution is O(nk), but yes, it's DP.

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

      Sorry, I meant O(nk), anyway, k is O(n). Thank you for reply.

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

      can u tell how to do it ... my solution was n^3 dp .

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

        Just recalculate sequence of its partial sums sum[] on each iteration.

        a[i][l]+a[i][l+1]+...+a[i][r-1]+a[i][r] = sum[r]-sum[l-1]

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

        I'll see whether my solution passes or not, but basically I compute the number of ways to end up on floor i after j steps for all possible i, for j = 1, 2, ..., k. Or more precisely:

        • Convert the buildings stuff so that the secret lab is on floor  - 1. We start on floor a' - 1 and the maximum height is on floor n' - 1. (In my solution above, I used that the secret lab is on floor 0, we start on floor a', and maximum height is floor n'; this made the array 1-based which is hard, so you can see a couple of places mentioning a-1 and never only a.)
        • Create a DP array of n' elements, indicating the possible number of ways to go to i-th floor after k steps. (This is array last and next; I only use the last row to construct the next row, hence why only two arrays and not a two-dimensional array.) At first, last[a' - 1] = 1 and last[i] = 0 otherwise for step k = 0.
        • Each iteration, compute next[i]; this is the sum last[i / 2 + 1] + last[i / 2 + 2] + ... + last[n' - 1], since we can go to floor i from floors i / 2 + 1, i / 2 + 2, ..., n' - 1. Subtract this with last[i], since we may not stay in the same floor. After all n' elements, replace the elements of last with the corresponding elements of next. To do this efficiently (O(n) instead of O(n2) each iteration), begin by taking and let next[i] = sum - last[i]; also, every time i is odd, subtract last[i / 2] from sum. All divisions are taken to be integer divisions. Remember to use modulo.
        • Iterate k times. The answer is the sum of last[i] after k iterations, of course after modulo.
        → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Well I think so, pretty sure that there is no soln in less than O(nk) and O(nk) surely exists.

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

What is the solution for Div 1 A?

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

    I just sorted them in descending order by a[i]. Have a variable that keeps track of the current day, let's name it day. Starting case is day = b[0] (zero indexed, already sorted) Now for all elements (starting from the second):

    if b[i]>day, day=b[i]

    else if b[i]<day, day=a[i]

    Just print day at the end. It's a simple O(NlogN) solution that I believe works (hasn't been hacked, can't know for sure before grading).

    EDIT: Forgot about the sorting when mentioning complexity.

    Here's my solution

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

What is the Hacking testcase for C ?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it 
    3
3 2
4 1
6 5

    Many people assumed that when the pairs are sorted by a, the resulting permutation of b must also be sorted in order for the answer to be bn (otherwise an). This is not the case, as shown by the test case above. (The answer is 5; many people give 6.)

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

      Also, another good hack is:

      4
5 4
5 3
5 2
5 1

      I managed to hack 2 solutions with this test (probably the ones which worked on your test above). Solutions which only sorted by a will fail on this test.

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

        Damn it, why did I write sorted(a, key = lambda e: e[0]) instead of sorted(a) >.<

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

        What answer should be 4 or 5, mine is giving 4??

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

A guy in this room reaaallly wanted to hack the room leader's solution...

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

    it's like gambling, you play, you lose but play again hoping to win what you have lost, until you end up being completely homeless.

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

    At least, Rostislav_the_great can now be sure his D submission is correct.

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

As always, unrated coders take over: 3 out of top 5 in Div2 are unrated

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

What were the hacking test cases for B div. 1? I found only one more or less common mistake — not checking whether the additional labels belong to [0 , L] interval.

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

    Well, my solution didn't pass pretests when I wasn't checking if new added dot < L, so maybe it's only the left if it's positive

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

    I found this (which also failed my locked submission):

    6 20 14 15
0 9 10 16 17 20

    Some people that made searching whether a distance exists in the array made it a function and thus only returned the first occurrence. In this case, the first occurrence of y - x is (9, 10), and with bounds they go over the ruler. However, there is another occurrence (16, 17), which fits; a new mark can go to 2, so the answer is 1 new mark. Those unlucky people (read: me and a couple I hacked) answered 2.

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

      wow, that's unreal. This got me too

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

      can u tell why my solution was hacked.... on your test case as well i am getting 1 2 as the ans . http://mirror.codeforces.com/contest/480/submission/8311510

      i will try to explain my approach . first find if any of x or y exists or not . if they both exist than output 0 if only one exist than output the other one if none exist than starting from every point find arr[i]-x,arr[i]+x,arr[i]-y,arr[i]+y keeping in mind about the overflow. if any of them occurs twice than output that coordinate else output given x and y. did i miss any case ??

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

        try this 4 33 5 7 0 6 16 33 ans should be 2.

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

          thnx got it .. did mistake in checking ... so stupid of me..

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

      well ..., next time will be because my D solution is broken with this case.

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

    My solution had the problem that I was introducing only the new values of arr[i]+x or arr[i]+y. A case like

    3 9 1 4
0 6 9

    would fail.

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

The Constraints of div1A were misleading :\ Made it look like an O(n^2) solution was the best when O(nlogn) is the most common solution.

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

    Well, maybe the setters wanted that even a O(N^2) sort can do.

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

How to solve Div 2 B?

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

    You can just take k times,in each time you work for the maxium-1 and the minium+1,notes the ans. And then it'll be solved:)

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

How do we solve the problem D (div2)?

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

    Solution can be 0,1 or 2(its obvious). Now, you can check if answer is 0(There exists both x and y). After, you can check if you can add a dot somewhere and make both x and y. If you cannot, just print 2 x y. Time Complexity: O(NlogN) logN is for using map/set/binarysearch. Space Complexity: O(N)

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

      I did the same thing by using a hash table, but it didn't pass the 4th test. Do you know the reason?

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

        You missed the possibility that the distance x + y or y - x might already exist.

        3 10 3 4
0 1 10

        Correct answer is 1: 4 (you use the pairs of marks (1, 4) and (0, 4)); some people give 2: 3 4.

        Meanwhile, that's not all of it...

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

      Time Complexity should be O(N)

      You are need to check 4 cases once by shifting check bounds http://mirror.codeforces.com/contest/479/submission/8327088

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

why haven't the system tests started?

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

    From the post at the very top: UPD: System testing will start at 15:30, because local school competition is not finished yet.

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

TESTINGTASK asked me during the contest for soln of Div2 C,stating " I'm new to codeforces and im struggling a lot. Can you tell me your solution to task C? ". Please "BAN" this guy!

Edit : Image Attached [Image Link]

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

It's already 15:30,but why didn't the testing happen?:)

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

it's already 15:40 :(

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

    We are working adding hacks into tests. It seems it will be a looooooong judging.

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

      I thought you want to hack the task C(DIV1) using bit?

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

On problem D on Div.1, I think O(Sn^2) solution is easy but doesn't pass, but someone said it will pass.

If it will pass, what a sad...

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

Has the olympiad ended? Can you publish an editorial?

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

    Editorial usually takes a couple of days

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

      I saw Nerevar writing a editorial.

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

      It depends on the author of the round. Some prepare an editorial before the round and publish it right after it's finished.

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

nice

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

finally system testing has started!

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

Why is gcd(185,230) not a valid answer for pretest 1? please help in Problem-D Long Jumps Div2!!! We can measure in multiples of 5. What's the problem with that?

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

    answer can be 0, 1 or 2. Re-read the statement.

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

    It's not a valid answer because it doesn't use the minimum number of marks.

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

      The number of marks is 1 only but the value is 5.

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

        Oh, I misread; I thought you meant there are marks.

        Reread the problem statement; you may not move the ruler while measuring the distance. In other words, the distance must be exactly the distance between some two marks, not the sum of several such distances. If you measure with the GCD, you need to move the ruler to construct the distance 185 and 230, which is not permitted.

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

What about problem E of div. 2? I thought of a O(n^2) solution, though sadly after the contest.

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

    Just doing DP with using consecutive sums.

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

Excuse me, I open CF website very slow on chrome, even can't see other people's codes after locking my problem B (I double click on other's scores of problem B in my room, but nothing happened). But it works well and very fast on IE. Can anyone tell me what will be the reason?

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

Can someone help me to understand this?

scoeretable

I solved C at 0:47, so I should have less points than wzyjerry. I missed somthing?

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

    Might be he had wrong attempts.

    EDIT : Indeed. He made a re-submission to the problem. Check his submissions.

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

      Ok, but I cannot see those in history for C (not sure if it should be there or not), he had both hack attempts for C.

      EDIT: you were correct, I didn't know what state "skipped" is

      detail

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

    -50 for failed attempt.

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

    the person mentioned might have had a WA/TLE on a previous solution, thus reducing 50 points from what they should have got.

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

This test #11 for DIV2, problem D is a killer :-D

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

Longest System test ever !!

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

Anybody can explain me why Bailando's 8304577 Div2 B problem works in 61 ms with this code:

rep(i,1,k) {
		sort(a+1,a+n+1,cmp);
		a[1].x++;a[n].x--;q[i].y=a[1].id;q[i].x=a[n].id;
		sort(a+1,a+n+1,cmp);
		ans[i]=a[n].x-a[1].x;
	}

2*k times sort n elements!

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

    N is up to 100 only, you can sort them 10-100 more times and that will still pass the TL.

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

why is the system tes taking too much time ???n thats weird !! :/

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

    It seems there is 111 tests for problem DIV2 D...

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

    There were a lot of successful hacking attempts today. So number of final tests is also very large.

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

    More than half of our judging machines were switched off from Codeforces because we need them on High-School Contest and Saratov ACM-ICPC Subregionals Contest.

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

I thought this contest was going to clash with codechef's. I missed it. :(

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

Any hint with DIV-2 E ?

Thanks in advance

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

    DP

    It was asked here before...

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

    Make DP in O(n3) and add presum for make it O(n2).

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

    A simple DP solution in O(n2k):
    Let dp[i][j] — number of sequences of length j which end with number i.
    Then it's easy to make forward DP propagation:
    dp[t][j + 1] += dp[i][j] for all t reachable from i.
    We can also notice that all ts for some i form a subsegment (or two), so we can use something similar to partial (cumulative) sums in order to achieve O(nk) time.

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

      Thanks so much, very well explained

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

(time zones in EST) Contest duration: 5:00 — 7:00 Addition of Hacks to System tests: 7:00 — 7:45 System Tests: 7:45 — past 10:15 Rating Addition: past 10:15 — ???

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

Russia School Competition pwned Codeforces Testing System's head for 254 gold !

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

    wrong answer ,753 gold since the testing systems had a streak!

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

Div2 Rating Changes posted but Div1 has not been updated yet.

Back to purple again! :)

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

These are two of my submissions, 8318803 and 8319108, the only difference between them is that in the first one I have used a macro at one place and in the second submission I havent used a macro at that single place. The observation is that when I didnt use a macro, the solution got faster by 31ms, so does a macro slow down a solution to that extent?

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

    A macro is only processed by the compiler's preprocessor, so it won't affect your runtime. This is just a result of inconsistent judging.

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

Looks like my prayers for red were answered. 2201!!

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

Very weak tests for Div 1. A!

The solution before I submitted, which is wrong:

http://mirror.codeforces.com/contest/480/submission/8322271

gets AC.

My correct solution (http://mirror.codeforces.com/contest/480/submission/8307803) also gets AC... but it seems I shouldn't have resubmitted D:.

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

    That else block will never occur. Read the problem statement again; the first element will always be greater than the second element, so dead[g].first >= last will always be true.

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

Need some help in Div 2 C or Div 1 A 479C - Exams. This submission 8310177 got WA for test 18 while this submission 8322341 got AC. Both codes are similar- the first one uses an array and the second one uses STL pair. Can someone please explain what went wrong in the first one. Thanks in advance.

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

    Sort stinks. Try sorting with cmp1 first, then with cmp. But I'd rather write all this into one comparator.

    if(x.a<y.a) return 1; else if(x.a==y.a) return x.b<y.b; return 0;

    Try.

    → Reply