NelsonMondialu's blog

By NelsonMondialu, 10 years ago, In English

Hello everyone,

I'd like to invite you to participate in a 2-hours Div2 round which will be held this Saturday, August 30th at 11:30 AM MSK. Div1 coders can take part out of competition, as usual. The problems were prepared by me and Archazey (B and C). I'd like to thank Gerald for helping preparation, Archazey for english translation and MikeMirzayanov for the Codeforces system.

The main characters of this round will be Caisa and Gargari,which have some interesting tasks for you. I hope you will enjoy the round. Good luck and have fun!

UPD: It will be used a standard scoring.

Here are the winners:

1.lymmd

2.for_the_pride

3.danilka.pro

4.zld3794954

5.nxihkke

Stats about hacks can be found here.

Editorial is here.

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

| Write comment?
»
10 years ago, # |
  Vote: I like it +96 Vote: I do not like it

First time to take part out of competition :)

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

I think this is the first round made by someone from Vaslui (my hometown, too) :D My round is coming soon :P

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

The day is just to sign up for a new term, and it's afternoon in China! we happen to have much time for it ^_^ !

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

Very unusual contest time! :D

I think there will be a high decrease of the number of registrants!

Good Luck.

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

    That is because in the same day there will be topcoder SRM + Hackerrank 101 hack august

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

    It will surely increase there are a great number of chinese coder will join:)

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

    4077 registrants... :)
    In round 263 there were 3988 registrants...

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

Please add time conversions :)

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

    You can check time conversion from contests -> current contest and click on the time given :).

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

    According to this comment, you are not a programming contest addict... :P

    You know you are a programming contest addict when : You have become the master of converting timezones to your country's standard time.

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

      Hahaha, I became used to clicking the links in announcement post to check.

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

      That is an implication. But is it an equivalence?

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

Very nice. I will do my best to do this round and get >1700 rating.

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

    Best of luck! I hope I take part in this contest(I don't like the time of this contest) . If I do, I wish I atleast become blue again.

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

    According to my own experience, I think that you will stay in expert for a few rounds before getting to div1

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

finally a chance to participate in a good time :D

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

    Not a good time for US though: 12:30 AM to 3:30 AM depending on the time zone...

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

Converted Time Washington DC, District of Columbia, U.S... 3:30 AM EDT http://fc02.deviantart.net/fs71/f/2013/281/0/0/sleep_is_overrated__by_austin_comix_inc-d6ps3kj.gif

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

There wasn't any hurry for posting the blog :D

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

alert("dsjgds");

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

Please link converted time

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

May be i will Miss this contest Due to My Exam

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

is there any contest for beginner problem solving to start practice with ?? HELP

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

    Take any previous contest in virtual mode, for beginners DIV 2 is the place. Why not try the last contest itself : Click here Simply register and familiarize yourself with how a codeforces round actually is.

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

very excited about contest. First time to unofficially participate!!! Hoping to solve ABCD for first time :)

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

    Since solving AB doesn't really give you anything and there's no rating to lose, you should start from D or E. These div2 contests are a true golden mine for trying out risky new approaches :D

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

      Good advice :). I'll probably start from C, try D+E, then go to AB

      Also, do you read all of the problem statements before starting to work on any problems?

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

I want have a good grades in this contest,bless all!

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

I hope the problems have something to do with elegant graphs/dp/trees/combinatorics problems and not some greedy approach with a lot of conditions and corner cases!

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

Hope the problems will be interesting. Let's enjoy it. :)

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

this is my first contest

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

Waiting for a nice problemset!!

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

good time for contest :) <3

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

What was the solution of problem D?

I starting taking the LCS of the first and seccond line. And then LCS the result with the third line and ... (LCS calculation was DP — But I called it recursively for the new check).

I got segmentation fault. Does anyone know the reason? Is my algorithm correct?

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

    My idea was same too, but this technique wouldn't pass the sample I/O. I mean if there is several subsequence with same length , which one would you consider ? For example

    between

    1 4 2 3
    4 1 2 3
    

    you have 1 2 3 and 4 2 3 , which one would you choose for 1 4 2 3 , here it is obviously 1 2 3 eventually you have to try all the sequences. I think there are some other technique.

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

      I think they should have accepted all of the possible answers.

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

    You must use suffix automat.(Sorry for mistakes ) :D

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

    This problem is as like as SPOJ: X-MEN
    Difference is in the problem of spoj, we have to find out LCS between only one pair. But In D of this round, we have to find out LCS between each pair. And it is possible, as maximum value of k can be 5.

    *** The problem of SPOJ(given above) can be converted into LIS... Then I solved it in nlog(n).

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

    Your algorithm is not correct, because there could be more than one LCS.

    The solution is quite simple — for every you make a vector Vx = {a1, ... ak}, where ai means position of x in i-th permutation. Now you create a directed graph — iff . Now an observation — if u1, u2, ..., um is a common subsequence, then u1, ... , um is a path in our graph. So now your problem is to find the longest path in a graph. But this is a DAG, so it is easy — you can either make a topological sort, or just brute it in O(n2).

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

      Can you explain the graph creating part a bit please , I mean this part   .

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

        Sure. Let's look at positions of numbers 1 and 2 in our permutations. {x1, ..., xk} are positions of 1 (i.e. in i-th permuation number 1 is on xi -th position) and {y1, ... , yk} are positions of 2.

        Now we create a graph with vertices labeled with 1,2,...,n.

        When x1 < y1, x2 < y2, ... xk < yk, then we create a directed edge from vertex 2 to vertex 1. In other words, we create such an edge when in each permutation 2 comes after 1.

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

          it seems we can't do bitmask DP over k. At least my code failed. Could you give me a hint why? I do not get why it fails. :(

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

          Thank you , a little question though , if the array was not a permutation , i.e there was repeated numbers , could we have solved the problem using similar approach ? I mean can the normal lcs problem be solved like this?

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

          Thanks for nice explanation :)

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

      it seems we can't do bitmask DP over k. At least my code failed. Could you give me a hint why? I do not get why it fails. :(

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

    That will have problems in case of multiple LCSs. Eg, consider (1,2,3,4,5), (1,2,3,5,4) and (4,1,2,3,5). First two have two LCS : (1,2,3,4) and (1,2,3,5). If you took only one, and that was (1,2,3,4), then you will get final answer 3, whereas the final answer is 4.

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

    The trick here is that input is a permutation (no repeats). Hope this gives a hint to those who still want to think about D.

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

    i donot think u need all of that there is a very important observation which is for every sequence the numbers are found only once so u can save the index of every digit for every sequence and try to start with any of them but u will need to know the last digit taken so that the sequence in valid then u check if all the numbers are in valid position (after the last number) u add this digit in all the sequences to the solution so the state will be (last digit taken) and u will have a loop on the all the digits except the last one trying to choose any valid digit sorry if it seems a little bit messy or alot

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

Pretest 2 for problem E seems so strange...... So many people get WA or RE on this......

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

Div.2 B — find max?

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

What is the explanation of B seriously -_- . I first thought that it may be the maximum number . But I couldn't prove it. But at the last of the just before 3 min contest I see B was solved more than A , So , I just submitted by calculating the maximum number. I don't know if it is true though.

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

    It seems to be obvious that in each step the current energy is equal to h[0] — h[current_step], so you just need to increase h[0] (from 0 to max(h[]))

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

    Instead of increasing height of some pylons you can just increase on all your money height of the first pylon, answer would be the same because increasing height of the first pylon just increases your starting energy. So you calculate minimum energy on the way and then add this energy (or 0) as a height to the first pylon.

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

Problem C?

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

    make dp matrix for 4 diagonal you will need 4 dp arrays for that one to add dollars from up-left and from bottom-left , up-right , bottom-right.
    then make another dp matrix to collect all of them dp[i][j]=dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]-3*mat[i][j] --> mat[i][j] is original value we subtract 3 of them because we add the same cell 4 times and we need just once.
    one observation is that the one bishop will be on white cell and another will be on black one (like a chess board) because problem statement says that "there is no cell that is attacked by both of them" if you tried to put both on white cells you will see there is a cell attacked by two , try it
    so just loop on all i,j in dp and take maximum in black cells and maximum in white one and result is the sum.
    feel free to ask

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

When 1 hours remaining, then my father call me and come to eat pizza..:<

I solved A and B (for pretests) and I try to solve C, but I failed... and time was too short for me(I can use 1 hour..)

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

Nice contest Narcis and Mircea! I'm a little bit surprised that there are more pretest passed submissions on B than on A (because B was trickier in my opinion). A was very good for Div2. About C I would like to say that it's nice. I liked D the most, because it's really beautiful despite its very simple input. Initially I thought that E is some kind of HLD with segment tree, so didn't try it for long. Got the right idea in the last 20 minutes (some kind of sorting + DFS). Not the most prolific round for hacking though. Anyway, keep up the good work.

P.S.: Caisa is a really nice name for a task hero. Don't you think? (image) I'm curios what does Gargari comes from.

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

I missed a hack attempt in problem C. At 01:56 (4 minutes remaining), I saw a solution with overflow problem. I then wrote a code to generate worst case of 2000x2000 with all entries 10^9. Submitted at 01:59:57 ... It itself TLEd!... Then it striked that a 2x2 matrix would have been sufficient. LOL !! =(

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

What a contest! I hacked for the first time!

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

    What a contest! I was hacked for the first time! :/

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

Does anyone know how to solve C?

I precomputed the sums for each position where a bishop could be placed in O(n^2), but I don't know how to find the pair of bishops without checking each possible pair.

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

    Find the best bishop for (i+j)%2=0 and the best bishop for (i+j)%2=1, then add them. Like the board for chess.

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

      Why is this necessary? What if two bishops are placed in squares who are equivalent modulo 2 and they don't attack each other ?

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

        Give me example, please) (When two bishops are placed in squares who are equivalent modulo 2 and they don't attack each other)

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

          Oh sorry, Just realized that is not possible as as soon as you select a bishop , if you draw a line on the board along the square's diagonals , you have divided the board into two halves. Now if you place a bishop in another equivalent square (modulo 2) you have to cross this line which will have an intersection and that square will be attacked by both the bishops.

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

          I have to disagree with you here. Two Bishops attacking each other will have to be in the same diagonal. There is a difference between "two bishops attacking each other" and "two bishops attacking the same cell". The problem statement failed to differentiate between these two. Read this wolfram article. Cell (2,2) and (0,2) will both attack cell (1,3) but they are not directly attacking each other.

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

    colors of bishops should be different

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

    You don't need to check each and every combination of pairs. It is stated in the problem statement that "No position should be attacked by both the bishops", this made the problem simpler.

    Now you need to check the max for bishop on black positions and max for bishop on white position and add those. Thats it :)

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

    If you look carefully then you will see the board is bipartite.A white bishop cannot attack a black one. So find the max black diagonal and max white diagonal. answer is the summation.

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

    Oh, I missed that part. Thanks!

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

    Well , I think you know what a white cell and black cell in chess is. Now see , if you place a bishop in a black cell than you can't put the other in black too. because then they would attack atleast one common cell . try drawing it in paper. So , the problem is no bishop lines intersect each other. so you calculate for each one seperately like this

    //first bishop
    for(int i=1;i<=n;++i)
      int j;
      if(i%1)
         j=1 // for second bishop , j=2
      else
         j=2 // for second bishop, j=1
      for(;j<=n;j+=2)
        // calculate sum from fourcorners
      if(sum>bishop1Max)
         //change max value and position
    
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why so many people get wrong answer on pretest 5 in DIV 2 A problem ?

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

    I didn't)

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

    they thought they can buy more than one pocket with sugar

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

    This is tricky test case. 1 9 9 0 Output:0 not -1

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

    i got wrong answer because i do not see anywhere written that you cannot buy more that one unit of same sugar. I still do not see that, can someone please point out where it is mentioned in the problem A Div 2.

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

Hi, I am a newbie for Codeforces. I found that I was unable to view the results of pretest of my submissions. Everytime I clicked the number linking to the submissions which failed on pretest, the popup was just displaying my source code but no pretest results. And in the direct link of the submission was also just displaying the source. Any can help? Thanks in advance.

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

    this is only possible during practice. In contest You have to figure out by yourself :)

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

    You can't see your output.. You have to figure it out yourself

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

    That is the intended behavior during a codeforces round. You do not get to see the pretest that caused your program to fail.

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

    You can not see pretests during the round. You must find a wrong test and mistake in your solution yourself.

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

    You cannot see pretests during the contest ;)

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

Does anyone know the second test case of C?

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

This is very good contest that I participate first time but I could not solve any problems :D

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

in problem C
change
ll mx1=0,mx2=0;
to
ll mx1=-1,mx2=-1;

Accepted :( :(

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

Too fast systest!!

When I saw my ranking it was at 30% testing. In a few (~30) seconds, after I again checked the dashboard, it was 100%. I was expecting it to be around 40 — 60 at that time.

this is unbelievably fast!

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

Please, could you tell how to count the sum that gives the black bishop using dynamic programming

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

    The better solution is to use array sum[2][N*2]. sum[0] — sums of LT-RB diagonals, sum[1] — sum of LB-RT diagonals. To calculate such array you need only two formulas:

    sum[0][i+n-j-1] += a[i][j]
    sum[1][i+j] += a[i][j]
    

    Then the answer for (i,j) is sum[0][i+n-j-1] + sum[1][i+j] - a[i][j]. That's all.

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

    Just like Prefix sum

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

cin/cout gets TLE for problem C and scanf/printf AC ? Seriously ? Nice...

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

    Me too!I want explanation!

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

      cin is like a turtle. Very slow turtle.

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

      I agree !! I knew this happens on some OJs, but it never happened to me on CodeForces. Maybe the authors are inexperienced and missed that, maybe they should reeval.

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

    Use

    ios::sync_with_stdio(0);
    

    In case cin/cout is too slow, this line speeds them up

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

Did anyone else too misread problem C as placing bishops such that they do not attack each other, rather than placing bishops such that they do not attack any common cell. I wasted an hour on this before realizing I had misread the problem.

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

    I wasted half an hour because i thought that they were rocks and i don't know how :D then i wasted another half thinking that they mustn't attack each other :D

    strange contest time leads to weird results :D

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

    Exactly I even coded that to realise at 1:42 the insane thing i did.

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

    I calculated that max cost is 4n-4, only to realize that weights of the cells were input based. (i assumed 1!)

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

    Same here. The problem becomes much harder with this "new" statement.

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

Please publish a complete editorial and update ratings fast :)

Thanks

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

in problem B wouldn't it be sufficient to find the maximum pylon and print it out ?

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

    Yes it would be. Printing the maximum of the numbers would do.

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

For Prob A, if the input is

1 6
2 80

then, he can either buy just one for 2$ 80cents, and get 20 candies in return or, he can buy 2 worth 5$ 60cents, and get 40 candies in return. So, the answer should be 40 candies, and not 20.

I interpreted the problem in the above mentioned way. It was mentioned that he can purchase only one type of sugar, but it was not mentioned that he can purchase only one quantity of that type. I ended up wasting over an hour over this ambiguity.

Am I correct?

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

    Same with me,

    I think for 1 10 0 70, answer should be 90 (because 3 times of same type can be taken) but for all the AC solutions, the answer gives 30...

    WTH?!?!?

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

    I made the same mistake and cost me 2 WAs. however, maybe the problem setter wrote this line there are n types of sugar in the supermarket, maybe he able to buy one. to inform us that he can buy only one pocket of sugar.

    I think the problem statement should've been clearer .

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

Weak test cases for problem E. Even brutes are accepted.

TLE by cin and AC using scanf.

very upset by the contest.

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

    Maybe test cases for problem E were generated randomly.

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

:( Just changed cin to scanf on problem C an got AC, it's ok to get TLE because of reading method or the most important part is the algorithm and it complexity ??

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

As a Chinese I do not think there's no difference between "type" and "number".

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

Problem C got TLE just because of cin\cout.Without it I can become candidate master.Such a bad contest

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

Why this solution is wrong? I used DP over bitmaks of set of sequences and looked for the longest common subsequence.

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

can anyone tell me why i am getting TLE in problem C my complexity is O(n*n) solution code LINK.

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

    Maybe because cin is very slow

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

    You use cin. It's too slow. I made the same mistake

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

Nice Round!

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

Stop ZLD! Why you create so many accounts for div.2!

ZLD_submit_for_practice1 OrzSKYDEC hzwerOrz hellp zld3794954

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

TLE code ::: http://codeforces.net/contest/463/submission/7635306

AC code ::: http://codeforces.net/contest/463/submission/7642386

Difference is only a cin function :( too much pathetic :'(

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

nice round! +169 expert again! hoho!

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

Where is tutorial?!!

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

    you can play clash of clans . IT's best.

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

Country Wise Standings has been updated.

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

The E's system test may be too weak.

If the tree is a long link with all nodes is 2 with the deepest node is 3. And I query the last node every time. There seems many AC solutions cannot pass this case.

The data maker by python:

n = 100000
print n, n

for i in range(n - 1):
    print 2,
print 3

for i in range(n - 1):
    print i + 1, i + 2

for i in range(n):
    print 1, n

Maybe I am wrong. Please reply to point it out.

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

Stats about hacks can be found here.

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

how can i solve C in O(n^2)? the number of black and white cells can be up to (n^2)/2

so.. for white_x for white_y for black_x for black_y

i thought O(n^4) but it seems wrong.. sorry for dumb question and bad english

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

    Compute the value for each rightwards diagonal and leftwards diagonal . Now iterate through the whole 2D array , Find the value for that particular cell as (leftDiagVal(cell) + rightDiagVal(cell) — X[cell] ) and greedily update the answer for Odd(i+j) and Even(i+j) . //X[cell] is the value input in that cell Answer = Answer_Odd + Answer_Even

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

The data of Problem E is too weak 7644499 The time complexity of his algorithm is O(q*height) Why can he accept?

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

    I found it so... Test is too weak.

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

In problem A Div 2, i got wrong answer because i do not see anywhere written that you cannot buy more that one unit of same sugar. I still do not see that, can someone please point out where it is mentioned in the problem A Div 2.

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

    "maybe he able to buy one" in the second paragraph?

    I am not really sure either.

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

I really appreciated with fast turtorial bcz some problem seems hard for me to understand. After understanding the div2(ABCD) problems, I wrote the why and how here.

wrote in chinese. Hope useful for the guys like me^_^

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

In the Div2. C question, I get a TLE when I use cin to scan numbers which is understandable. But when I use fast io for cin, cout; precisely this :ios_base::sync_with_stdio(false);cin.tie(NULL); I get a WA on test1, which runs correctly on my shell though. However, using scanf my answer gets accepted. I have always ignored such fumble. Can anybody please explain me how I can use cin, cout in this case and still not get a tle?

TIA.

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

    Here you can find information about sync_with_stdio function. The reason, why you are getting WA is you unsync your streams, so if you are using scanf and cin in one program (as you're using in yours), then you will get undefined result.

    To use cin/cout with sync_with_stdio, you should not use scanf/printf. In this case it will work properly.