Nerevar's blog

Codeforces Round #274
By Nerevar, 11 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?
»
11 years ago, hide # |
 
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
»
11 years ago, hide # |
← 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
»
11 years ago, hide # |
← 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
»
11 years ago, hide # |
 
Vote: I like it -7 Vote: I do not like it

ICPC rules?

→ Reply
»
11 years ago, hide # |
 
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
»
11 years ago, hide # |
 
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
»
11 years ago, hide # |
 
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
»
11 years ago, hide # |
 
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
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

My first Div. 1 contest!! :)

→ Reply
»
11 years ago, hide # |
 
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
»
11 years ago, hide # |
 
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
»
11 years ago, hide # |
 
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
»
11 years ago, hide # |
 
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
»
11 years ago, hide # |
 
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
  • »
    »
    11 years ago, hide # ^ |
     
    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
»
11 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
11 years ago, hide # |
 
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
  • »
    »
    11 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, hide # ^ |
     
    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
»
11 years ago, hide # |
 
Vote: I like it -47 Vote: I do not like it
The comment removed because of Codeforces rules violation
→ Reply
»
11 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Good bye yellow color!

→ Reply
»
11 years ago, hide # |
 
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
  • »
    »
    11 years ago, hide # ^ |
     
    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
»
11 years ago, hide # |
 
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
»
11 years ago, hide # |
 
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
  • »
    »
    11 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

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

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

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

    → Reply
    • »
      »
      »
      11 years ago, hide # ^ |
      ← 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
    • »
      »
      »
      11 years ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        11 years ago, hide # ^ |
        ← 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
      • »
        »
        »
        »
        11 years ago, hide # ^ |
         
        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
  • »
    »
    11 years ago, hide # ^ |
     
    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
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

What is the solution for Div 1 A?

→ Reply
  • »
    »
    11 years ago, hide # ^ |
    ← 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
»
11 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

What is the Hacking testcase for C ?

→ Reply
  • »
    »
    11 years ago, hide # ^ |
     
    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
»
11 years ago, hide # |
 
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
»
11 years ago, hide # |
 
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
»
11 years ago, hide # |
 
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
  • »
    »
    11 years ago, hide # ^ |
     
    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
  • »
    »
    11 years ago, hide # ^ |
     
    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
    • »
      »
      »
      11 years ago, hide # ^ |
       
      Vote: I like it +4 Vote: I do not like it

      wow, that's unreal. This got me too

      → Reply
    • »
      »
      »
      11 years ago, hide # ^ |
       
      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
    • »
      »
      »
      11 years ago, hide # ^ |
       
      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
  • »
    »
    11 years ago, hide # ^ |
    ← 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
»
11 years ago, hide # |
 
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
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to solve Div 2 B?

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

How do we solve the problem D (div2)?

→ Reply
  • »
    »
    11 years ago, hide # ^ |
     
    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
»
11 years ago, hide # |
 
Vote: I like it +68 Vote: I do not like it

why haven't the system tests started?

→ Reply
»
11 years ago, hide # |
← 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
»
11 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

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

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

it's already 15:40 :(

→ Reply
»
11 years ago, hide # |
 
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
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Has the olympiad ended? Can you publish an editorial?

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

nice

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

finally system testing has started!

→ Reply
»
11 years ago, hide # |
← 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
  • »
    »
    11 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, hide # ^ |
     
    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
    • »
      »
      »
      11 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        11 years ago, hide # ^ |
         
        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
»
11 years ago, hide # |
 
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
»
11 years ago, hide # |
 
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
»
11 years ago, hide # |
← 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
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

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

Longest System test ever !!

→ Reply
»
11 years ago, hide # |
 
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
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, hide # |
 
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
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Any hint with DIV-2 E ?

Thanks in advance

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

    DP

    It was asked here before...

    → Reply
  • »
    »
    11 years ago, hide # ^ |
     
    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
  • »
    »
    11 years ago, hide # ^ |
    ← 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
»
11 years ago, hide # |
 
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
»
11 years ago, hide # |
 
Vote: I like it +29 Vote: I do not like it

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

→ Reply
»
11 years ago, hide # |
 
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
»
11 years ago, hide # |
 
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
»
11 years ago, hide # |
 
Vote: I like it +28 Vote: I do not like it

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

→ Reply
»
11 years ago, hide # |
 
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
  • »
    »
    11 years ago, hide # ^ |
    ← 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
»
11 years ago, hide # |
 
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
  • »
    »
    11 years ago, hide # ^ |
     
    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