fcspartakm's blog

By fcspartakm, history, 4 years ago, translation, In English,

670A - Holidays

There are many ways to solve this problem. Let's talk about one of them. At first we need to write a function, which takes the start day of the year and calculate the number of days off in such year. To make it let's iterate on the days of the year and will check every day — is it day off or no. It is easy to show that if the first day of the year equals to the first day of the week (i.e. this day is Monday) in this year will be minimum possible number of the days off. If the first day of the year equals to the first day off of the week (i.e. this day is Saturday) in this year will be maximum possible number of the days off.

670B - Game of Robots

To solve this problem we need to brute how many identifiers will called robots in the order from left to right. Let's solve this problem in one indexing. Let the current robot will call i identifiers. If k - i > 0 let's make k = k - i and go to the next robot. Else we need to print a[k], where a is the array with robots identifiers and end our algorithm.

670C - Cinema

We need to use map-ом (let's call it cnt) and calculate how many scientists knows every language (i. e. cnt[i] equals to the number of scientists who know the language number i). Let's use the pair res, where we will store the number of \textit{very pleased} scientists and the number of \textit{almost satisfied} scientists. At first let res = make_pair(0, 0). Now we need to iterate through all movies beginning from the first. Let the current movie has the number i. Then if res < make_pair(cnt[b[i]], cnt[a[i]]) let's make res = make_pair(cnt[b[i]], cnt[c[i]]) and update the answer with the number of current movie.

670D1 - Magic Powder - 1

This problem with small constraints can be solved in the following way. Let's bake cookies one by one until it is possible. For every new cookie let's calculate val — how many grams of the magic powder we need to bake it. For this let's brute all ingredients and for the ingredient number i if a[i] ≤ b[i] let's make b[i] = b[i] - a[i], else let's make b[i] = 0 and val = val + a[i] - b[i]. When we bruted all ingredients if val > k than we can't bake more cookies. Else let's make k = k - val and go to bake new cookie.

670D2 - Magic Powder - 2

Here we will use binary search on the answer. Let's we check the current answer equals to cur. Then the objective function must be realized in the following way. Let's store in the variable cnt how many grams of the magic powder we need to bake cur cookies. Let's iterate through the ingredients and the current ingredient has the number i. Then if a[icur > b[i] let's make cnt = cnt + a[icur - b[i]. If after looking on some ingredient cnt becomes more than k the objective function must return false. If there is no such an ingredient the objective function must return true.

If the objective function returned true we need to move the left end of the binary search to the cur, else we need to move the right end of the binary search to the cur.

670E - Correct Bracket Sequence Editor

Let's solve this problem in the following way. At first with help of stack let's calculate the array pos, where pos[i] equals to the position of the bracket which paired for the bracket in the position i. Then we need to use two arrays left and right. Then left[i] will equals to the position of the closest to the left bracket which did not delete and right[i] will equals to the position of the closest to the right bracket which did not delete. If there are no such brackets we will store -1 in the appropriate position of the array.

Let's the current position of the cursor equals to p. Then if the current operation equals to \texttt{L} let's make p = left[p] and if the current operation equals to \texttt{R} let's make p = right[p]. We need now only to think how process the operation \texttt{D}.

Let lf equals to p and rg equals to pos[p]. If lf > rg let's swap them. Now we know the ends of the substring which we need to delete now. If right[rg] =  =  - 1 we need to move p to the left (p = left[lf]), else we need to move p to the right (p = right[rg]). Now we need to recalculate the links for the ends of the deleted substring. Here we need to check is there any brackets which we did not deleted to the left and to the right from the ends of the deleted substring.

To print the answer we need to find the position of the first bracket which we did not delete and go through all brackets which we did not delete (with help of the array right) and print all such brackets. To find the position of the first bracket which we did not delete we can store in the array all pairs of the ends of substrings which we deleted, then sort this array and find the needed position. Bonus: how we can find this position in the linear time?

670F - Restore a Number

At first let's find the length of the Vasya's number. For make this let's brute it. Let the current length equals to len. Then if len equals to the difference between the length of the given string and the number of digits in len if means that len is a length of the Vasya's number.

Then we need to remove from the given string all digits which appeared in the number len, generate three strings from the remaining digits and choose smaller string from them — this string will be the answer. Let t is a substring which Vasya remembered. Which three strings do we need to generate?

  1. Let's write the string t and after that let's write all remaining digits from the given string in the ascending order. This string can be build only if the string t does not begin with the digit 0.

  2. Let's write at first the smallest digit from the remaining digits which does not equal to 0. If we have no such a digit we can't build such string. Else we need then to write all digits with smaller than the first digit in the t in the ascending order, then write the string t and then write all remaining digits in the ascending order.

  3. Let's write at first the smallest digit from the remaining digits which does not equal to 0. If we have no such a digit we can't build such string. Else we need then to write all digits with smaller than or equal to the first digit in the t in the ascending order, then write the string t and then write all remaining digits in the ascending order.

Also we need to separately consider the case when the Vasya's number equals to zero.

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

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

well, that was quick :v

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

(Sorry for my poor english...) This round was very interesting for me... Thanks a lot fcspartakm ...

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

In problem C

TLE when using an unorderd map :17741658

Accepted when using a map :17749162

why ?!

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

    In worst case, unordered map works in O(N) time, when ordered has O(logN).

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

      Java solutions work normally using HashMap. Tests should have been more strict to time out all solutions that use hashing, not just C++.

      Also unordered_map can pass if you set size to 10000000 / 3. I got this off stackoverflow, and it passed in 600ms which is faster than map.

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

        what do you mean by "set size to 10000000 / 3" ?

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

          When you initialise your map put that number between the brackets. I think it has something to do with load factor or size. I haven't had the time to google/search yet like the guy below me is saying,especially that C++ is not my main language. Have a look at my latest submission if you need an example, I'm on mobile and can't link.

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

          Hello,

          in C++ you can use for example "M.max_load_factor(.4)"

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

        You should try to understand how std::unordered_map is implemented rather than just "hack" around it.

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

    Same problem :( I won't use unordered containers in C++ anymore!

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

    i don't know how c++ implements the map . but in java Hash Map worst case is O(n) but it rarely happens .. the common is o(1) but if we assume that the probability of collision is big the worst case would be O(n/K) k is a constant number . but in Tree map or ordered map in c++ . it guarantees O(log n ) for basic operation .

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

Hi guys I used binary search to solve problem B. Simple and easy.

let f(x)=x(x+1)/2
first we will find the smallest x such that f(x)>k
to find the smallest x such that f(x)>k we will use binary search

then the answer is A[x-f(x)-k] assuming 0 based indexing


17739820

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



    Easy solved problem?

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

      by easy I mean easy concept. the WA's occured cause of using int when i changed that to ll it worked.

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

    You can just solve this quadratic equation to get the right x. I would say this is a lot easier then binary search.

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

      yes you could do that but for some reason my brain did not work in the contest.

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

Can anybody help me with my solution for problem E. Expected output and my output are same. But still, I am getting a wrong answer. 17746092

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

I'm Pretty Sure I've solved E correctly with a good complexity using linked list

However the system gives me TLE on pretest 1 even though it works on ideone.17748382

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

    could someone please help me out on this it's driving me crazy thx

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

      ah well :-(

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

        You could use custom invocation to test on codeforces.

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

          That's the problem. It gives me TLE even on custom invocation (which means it takes at least 10 seconds) even though it works perfectly on ideone: http://ideone.com/cIPfDR

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

            You should replace s.erase(it); by it=s.erase(it); otherwise it is not clear where "it" is pointing out once you remove the element from the list.

            This will let you pass the first pretests but then you will hit test 8. The problem there is different, you have trouble at the 4 instruction that corresponds to the second delete instrucition. When you remove a group of parenthesis at the end of the list, the new position should be the previous position not the next one.

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

              Thank you very much!!!!

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

could someone tell me why my code for E gets TLE on test case 77?

That's when the number of queries is very big. But doesn't my code spend per query? Is there some case that makes it O(n)?

The basic idea is to just build a segment tree on top of the input, where a node is either alive or dead and corresponds to a subset of parenthesis of size 2i. To remove all nodes between l and r all you need to do is kill the nodes that correspond to intervals [l', r'] that are contained within the interval [l, r]. Going right/left corresponds to finding the alive successor/predecessor leaf of the leaf that your cursor is currently positioned at. This should also be doable in time.

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

    There is simple O(n) solution. ST doesn't necessary. Keep it short and simple

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

      I am aware of the O(n) solution, I just need to understand why my solution with segment trees does not work.

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

    And use scanf / printf

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

problem D was awesome :D

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

**IN PROBLEM B **

There is a solution in O(1) http://codeforces.com/contest/670/submission/17761850

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it -6 Vote: I do not like it

    How can there be a O(1) solution,if you read the array in O(n)? Before posting something stupid,check your affirmation!!

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

      Chill out, his solution is still useful, and gives you new options to attack the problem.

      He probably meant O(1) without counting the reading part so just tell him nicely, we are a "community" after all...

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

      I mean O(1) except getting the elements of the array ! thank you

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

    Unfortunately, your solution has O(n) complexity because of reading n elements.

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

      I mean O(1) except getting the elements of the array ! thank you

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

why am getting Wa on problem F? is my solution is wrong? http://codeforces.com/contest/670/submission/17762248 if it does can you explain me why?

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

    Your solution fails on this:

    11034
    10
    

    The answer is 1013.

    Though, mine passes test 4 but fails on this test too, so I'm not sure if it's exactly what you're looking for.

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

      My code for problem F gives runtime error on test case 7.Code Does anyone know why?

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

I would highly appreciate if someone could explain the solution to problem B in more details.

Here is my solution which got TLE. I basically checked for all the ids called by a particular robot. I mentioned my naive solution so that a comparison with the expected solution can be drawn. Thanks in advance. :)

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

Problem D2. Not able to find any error in my solution. It fails in test case 128. Can someone please help in finding out the error. I uploaded the same code for D1 which got accepted. Here is my solution. Please help :p http://codeforces.com/contest/670/submission/17734861

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

Can someone tell me what is wrong with my approach 17778797 to solve E? It got Wrong Answer.

My approach:

  1. Find the positions of the matching brackets. pr[i]=j indicates i th bracket matches with j th bracket. I have used four stacks (left_part to store left part of the string, Left to store the positions of the brackets of left_part, similarly right_part and Right), though it can be done more effortlessly.

  2. Maintain two arrays next_right and next_left which respectively stores the position of the closest undeleted bracket at the right and the position of the closest undeleted bracket at the left.

  3. Use a variable border to mark the end of the valid string. It is equal to the position of the rightmost undeleted bracket plus 1.

  4. Now scan the operations.

    a. if the current operation is "R", p=next_right[p]

    b. else if the current operation is "L", p=next_left[p]

    c. else if the current operation is "D" :

    l=p, r=pr[p], if l>r : swap(l,r)

    if r+1==border : p=l-1, border=l

    else : p=r+1, next_right[l-1]=r+1, next_left[r+1]=l-1

    fill [l,r] of the string with '*', meaning these locations are deleted (I

    have done this to avoid re-calculation of pr)

5. Print the characters of the initial string of brackets if the character is not '*'.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    p=r+1;
    next_right[l-1]=r+1;
    next_left[r+1]=l-1;
    

    It should be next_right[l-1]=next[r] and next_left[r]=next_left[l]

    because in a certain moment r+1 doesn't represent the next position of r after some deletions.

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

      Thanks for your reply. Actually, your suggestion has some bugs, but the reason you have given is perfectly correct!


      I have found out what was wrong with the solution, thanks to you! Basically, inside the deletion

      operation, all r+1( except the border checking) should be replaced by next_right[r] and all

      l-1 should be replaced bynext_left[l] (I had considered this case only in 'L' and 'R'

      operations, my bad!). Though, it gives TLE on test 83 (17988636) after the corrections are made. I guess

      the proper way is to delete brackets in [l,r] and recalculate pr instead of filling [l,r] with

      '*'.

      On a side note, if I check for the border like this: r+1>=border, then it gets stuck at test 88 instead of test 83 (17989026)! I think that's just a coincidence and kind of effect of re-run. :)

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

Why is this solution of mine of Div2B giving a TLE? I am performing a maximum of 10^5 calculations. Someone please help!

Here is the link to my solution: TLE Solution

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

In problem 2 : Memory limit exceeded. I don't understand how to take care of it. My code is as follow :

include<stdio.h>

int main() { int i,l=1,j,h,c=0; long long int n,k; scanf("%lld",&n); h=n*(n+1)/2; long long int a[n],b[h]; scanf("%lld",&k); for(i=1;i<=n;i++) scanf("%lld",&a[i]); for(i=1;i<=n;i++) { for(j=1;j<=i;j++) { b[l]=a[j]; if(l==k) {printf("\n%lld",b[l]); c=1; break;} l++; } if(c==1) break; } return 0; }

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

IN PROBLEM D2 I THINK I HAVE A BETTER SOLUTION USING DP RATHER THAN DIVIDE AND CONQUER. MY ALGORITHM:- 1.CALCULATE INT[] DOING INTERGER DIVISION OF B[i] with A[i]. 2.sort this INT[]. 3.Now in a single scan of this array INT we can calculate the answer s.t. At each point we keep track of how many grams of magic powder can make one more cookie. 4.If INT[i+1]=INT[i] we just update this required number to build one new level 5.if INT[i+1]>INT[i] we try to increase INT[i].

Can anybody please tell me if my solution is better than the one given as I'm not sure.

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

Can anyone explain solution of B. I am not getting what is indexing?what does it mean?Thanks in advance

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

Check out my solution for Problem F. I wrote comments as I was writing the code to illustrate my thought process.

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

I don't know why my solution gets WA 18297102

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

There exists a simple greedy solution for problem D . Time complexity O(nlogn) for sorting. And O(n) processing.

19073660

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

I don't understand the solution of problem D, can anyone explain it elaborately, please?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How do I show this claim in the tutorial :

It is easy to show that if the first day of the year equals to the first day of the week (i.e. this day is Monday) in this year will be minimum possible number of the days off.