vepifanov's blog

By vepifanov, 14 months ago, translation, In English,

Intel Code Challenge Final Round will take place on Saturday, 8 October 15:05 MSK.

All users of the Codeforces can participate in it as in an usual round. The round will be rated and both divisions can participate. Pay attention to the time of the beginning of the round.

There will be 7 problems with statements in english and russian languages and 3 hours to solve them. Scoring distribution will be announced closer to the start of the round.

The problems were prepared by me — Vladislav Epifanov (vepifanov). I want to say thanks to Alexey Shmelev (ashmelev), Alexander Fetisov (alexfetisov) and Vladislav Isenbaev (winger) for testing the problems, coordinator of the Codeforces Gleb Evstropov (GlebsHP) for his help with the contest preparation, and Mike Mirzayanov (MikeMirzayanov) for the Codeforces and Polygon systems.

UPD. Scoring distribution: 500-1000-1500-1500-2500-2500-2500. Since the round will be 3 hours long, the number of points for each task will decrease slower than in usual round.

UPD. 2 Due to some issues on one of sites for official participation in Intel Code Challenge we shifted the beginning of the round for 10 minutes. Sorry for the inconvenience.

UPD. 3

Final rating changes will be available after removing unfair participants.

Editorial will be published on Sunday, 9 October.

Editorial

UPD. 6

Photos from the onsite event. ### Nizhny Novgorod

Arkhanglesk

Volgograd

Kazan

Moscow

Saint Petersburg

Winner of the Intel Code Challenge — Evgeny Kapun (eatmore)

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

»
14 months ago, # |
  Vote: I like it +98 Vote: I do not like it

Hope better English statements:D

»
14 months ago, # |
Rev. 6   Vote: I like it -45 Vote: I do not like it

how can (all users of the codeforces) participate in round (with div_1 and div_2 participants and 7 problems and unusual time of the beginning) as in an usual round?

»
14 months ago, # |
  Vote: I like it +35 Vote: I do not like it

please provide better problem statement in english.

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

Hope the scoring distribution can be announced a little earlier。:D

»
14 months ago, # |
  Vote: I like it +83 Vote: I do not like it

Will the problems be harder than the problems from the intel elimination round ?

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +157 Vote: I do not like it

    Problemset is designed to satisfy participants of all skill levels.

»
14 months ago, # |
  Vote: I like it -16 Vote: I do not like it

Hope I solved the problem better!

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

Hope it will be an awesome contest with some awesome problems.

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

i have a doubt ... As div1 contestants are participating along with div2 contestants...will this affect ratings for ppl in div2 differently as compared to when div1 ppl participate out of the competition ... Thanks in advance :) :) :)

  • »
    »
    14 months ago, # ^ |
    Rev. 6   Vote: I like it +8 Vote: I do not like it

    you can make virtual participation later. the problemset is good for all contestants so every one would compite in this kind of rounds , do not worry about rating just enjoy and Good luck for all .. sorry for bad english !

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I m participating but just wanted to know about rating system...

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

        Don't worry man Everybody will satisfied after the contest.. you will get what you deserve. I think it will be better of solving problem rather than thinking about rating changing process :)

»
14 months ago, # |
  Vote: I like it +47 Vote: I do not like it

Why does every comment in the form "Hope [noun/pronoun] verb ..." get downvoted? I don't understand...

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +57 Vote: I do not like it

    Does anyone ever understand the reason for downvotes on codeforces?

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +127 Vote: I do not like it

    Hope this comment won't get downvoted :)

    • »
      »
      »
      14 months ago, # ^ |
      Rev. 2   Vote: I like it +30 Vote: I do not like it

      Red Coder _ / \ _. Comment upvoted without even reading

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

      The "Red coders get Upvote" theory has been proven.

»
14 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Good luck for all (:

»
14 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Hope to become cyan finally, I need +22

good luck and have a good contest ...

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

    hoping same just need +31

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

      Advice from little bro- Try solving from reverse. like , if you solve a,b,c thn solve today c,b,a :D

»
14 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Timings are getting bad for me. Will we have a contest on usual time any day soon?

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

glad to know that all divisions coder will be participant. thanks a lot for the rated contest :)
hope so, it will be a great contest as elimination round :)
all the best to all :)

»
14 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Will the problems be significantly harder than the first round??

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

hope same kind of problem but of course with better statement. last round was awesome with the problem statement..... __

»
14 months ago, # |
  Vote: I like it -26 Vote: I do not like it

I hope to raise my rating

»
14 months ago, # |
  Vote: I like it -134 Vote: I do not like it

give me some downvotes

»
14 months ago, # |
Rev. 2   Vote: I like it -41 Vote: I do not like it

Good Opportunity to gain something new... :)

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

    why downvote his comment just because he is Asian.Or he is telling about a useful competition that dosent concern you.Or people just love to downvote if someone is not red. Now downvote me.

»
14 months ago, # |
  Vote: I like it +21 Vote: I do not like it

This is my last codeforces round before flying to Dalian,wish to learn new skills!Thank you,vepifanov!

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

    It is my last round before going to Hangzhou and Shenyang.

»
14 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Good luck to all and thanks vepifanov for this contest !!

»
14 months ago, # |
  Vote: I like it -13 Vote: I do not like it

In combine competition the div2 contestant participate a lower one. only div2 rated contest participate >=5000. But div1+div2<5000 and participate of div1 is high. so if distribution rating are seperate div1 and div2 contestant will be increase div2 but decrease div1.

»
14 months ago, # |
  Vote: I like it -8 Vote: I do not like it

unusual is the new usual

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

Hope, This round will be lot of excitement means hacking others code. :)

»
14 months ago, # |
  Vote: I like it +7 Vote: I do not like it

wish to see a programming contest not a hack contest and better English statements

GOOD LUCK FOR ALL :D

  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it +12 Vote: I do not like it

    dude you don't have to comment the same phrase each contest xD

»
14 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Contest start delayed?

»
14 months ago, # |
  Vote: I like it +36 Vote: I do not like it

(score[2] == score[3]) && (score[4] == score[5]) && (score[5] == score[6])? This is a strange distribution......

»
14 months ago, # |
  Vote: I like it +10 Vote: I do not like it

delay 10 minutes

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

Why Delayed -.-

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

First 3hr long rated round of my CF life. Wish a different result then usual :)

»
14 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Is the contest delayed because they want more participation ( 6k+ ) or because of some technical problem ?

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Neither I think.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think they want more people to participate

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +68 Vote: I do not like it

    We are waiting for the onsite participants to be ready to start.

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ohh.. cool. I didn't thought of that.

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

      May be, they are not free. Because it's unusual time

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    maybe they are giving a chance to those who missed to register in time :p

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't think 10 min would become a huge impact on participation...

»
14 months ago, # |
  Vote: I like it +25 Vote: I do not like it

This is my first contest. Feeling scared and excited at the same time !

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

    after a while it will be boring to wait until the contest starts! :/

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

Why I can't unregister? :/

»
14 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I hope I can Change to Blue

»
14 months ago, # |
  Vote: I like it -9 Vote: I do not like it

Strange Scoring distribution: 500-1000-**1500-1500**-_2500-2500_-2500.

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

Gl hf

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

My submission for D has been running pretest 10 for close to 10 minutes now with no final verdict. Can anyone help me out?

»
14 months ago, # |
  Vote: I like it +23 Vote: I do not like it

After a long time, I loved a contest on Codeforces. Nothing could have been better about the contest except my performance. Thanks a lot vepifanov.

»
14 months ago, # |
Rev. 7   Vote: I like it +5 Vote: I do not like it

How to solve 2A?

Edit: Nevermind, my solution passed.

»
14 months ago, # |
  Vote: I like it +2 Vote: I do not like it

This was a very difficult contest for us DIV-2'ers :|

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

how to solve C? I tried a approach like making a equation with 2 variables but didnt have enough to solve it

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

How to solve G? I thought of bicconected components with Gauss elimination but could not work out the whole solution.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Hint: If you can solve the problem on tree, edges that create a cycle with that tree can be processed separately (they affect every path the same way)

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

What are the hacks for A and B?

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

Div2C I forgot to use long long and spent 40min debugging...

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "long long case" was included in pretests for C?

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      I failed on case #10, and got AC after using long long

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

http://codeforces.com/contest/724/submission/21292757 Can anyone tell me what optimisation I could've done so I wouldn't get TLE for C?

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

    Not increment or decrement x and y by 1 or -1, but by more at once. For example, always increment it enough to make x == n || x == 0 || y == m || y == 0, which is not that hard to do.

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

      Then how do you increase count of all the sensors that come in the path on one increment?

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

        I stored a map from the endpoints of a diagonal to a vector of the sensors on it.

        • »
          »
          »
          »
          »
          14 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          could you please explain a bit more in detail i didn't get your idea.

          • »
            »
            »
            »
            »
            »
            14 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            It's not hard to calculate for any point in which primary and secondary diagonal it's located, and what the endpoints of those diagonals are. It's also simple to calculate the time needed to get from an endpoint to any point on the diagonal. You store the index of the sensor along with its distance in the map entry for that diagonal, in both directions since the distance is different. Then you track the movement of the laser from one edge to the other and each time process all the lasers in your path, clear the list of sensors and increase the time elapsed. If you don't understand, you can take a look at my code.

»
14 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Just realized that n and m in problem C is only upto 105

my overkill problem C solution using successive_substitution, theoritically (if free of bug) can solve for n and m upto 2×109.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution's complexity is O(k) and it's 25 lines long. Is there a shorter slower solution that works?

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Actually, O(k+h)

      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you give me some hint about your solution?I get tle.

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

          Instead having a room, I assumed the laser continues forever. Than, for each sensor there are positions that if the beam reached them it would have reached the sensor position if there were walls.

    • »
      »
      »
      14 months ago, # ^ |
      Rev. 3   Vote: I like it +1 Vote: I do not like it

      There is some solution with complexity O(k+n+m) and IMHO the code is a bit longer, but faster to code.

      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Tried this and got TLE (in python though). How do you check what the input when it's so long they put "..."?

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

          No, i can't. If the input is not too long but get trimmed "..." you can see it with simple program: print the input at position a to b, and b-a<512 bytes.

          btw, python is slow language, you might consider to move on to C/C++?

          • »
            »
            »
            »
            »
            »
            14 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I should move on, but I really thought python would be able to handle O(k+n+m). Tried what I thought was a similar input (also n,m,k = 100000,99999, 100000) before submitting and it was ~1 second which is why I am curious to try their exact case on my computer.

»
14 months ago, # |
  Vote: I like it -8 Vote: I do not like it

saturday

»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

can some one explain how to solve B . my approach was to count how many operation i can do in optimal way to get the 2D array sorted ..so i was thinking in that i tried a lot test cases and i couldn't figure how to determine the optimal number of operations and check if this number is <=n+1 ..my problem was how to use columns to make optimal number of swaps ? could somw one help ?

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

    I did it this way

    first see if the array can be sorted without changing in rows -> (change in each line==0||change in each line==2)

    then, change each rows with n^2 and check all the same way

    this way O(n^3) but n is only up to 20 xd

    #include <stdio.h>
    
    int n, m;
    int data[30][30];
    bool ans;
    
    void change(int a, int b)
    {
        int i;
        for(i=0; i<n; i++)
        {
            int tmp;
            tmp=data[i][a];
            data[i][a]=data[i][b];
            data[i][b]=tmp;
        }
    }
    
    bool check()
    {
        int i, j;
        for(i=0; i<n; i++)
        {
            int cnt=0;
            for(j=0; j<m; j++)
            {
                if(data[i][j]!=j+1) cnt++;
            }
            if(cnt!=0&&cnt!=2) return 0;
        }
        return 1;
    }
    
    int main()
    {
        //freopen("input.txt", "r", stdin);
        scanf("%d%d", &n, &m);
        int i, j, k;
        for(i=0; i<n; i++) for(j=0; j<m; j++) scanf("%d", &data[i][j]);
    
        if(check()) {printf("YES"); return 0;}
        for(i=0; i<m-1; i++) for(j=i+1; j<m; j++)
        {
            change(i, j);
            if(check())
            {
                printf("YES");
                return 0;
            }
            change(i, j);
        }
        printf("NO");
    }
    
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    OK , so we go.At first you must see that row may be already sorted , it needs one swap , two or more. 1)If some row needs more than two swap , answer is NO as with this operations we can get at max two swaps in one row . 2) if in none of these rows need more than one swap , answer is of course YES , because we don't need to use "column swap" at all .3) We have some rows than need two swap , so it have 3 numbers not in correct place , than we don't need to do about sorted rows , also we don't need to do anything about "one-swap" rows before "column swap" because. and so we have to consider only two-swap rows . It's not hard to see that all different positions for two-swap rows must be at max 4 . and it's the case , than we check all column swap , at most 6 =) hope it helps ! Feel free to ask.

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Bounds are small to try all O(M^2) possible column swaps. I think it's better than considering all these cases, the more complex your code is the higher the chance of making a bug.

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

Problem E. Goods transportation — Why is this O(n*n) approach incorrect?

0.1. i goes from n-1 to 0:

1.1. trans = min(prods[i], sells[i]); // Sell as much as possible at the current i-th city.

ans += trans; sells[i] -= trans;

1.2. j goes from i-1 down to 0:

trans = min(sells[i], c, prods[j]); // Transfer as much as possible from the j-th city.

ans += trans; prods[j] -= trans; sells[i] -= trans;

1.3. Output the ans.

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

    I think you need to transfer in such a way that the largest amount of excess goods is minimized. Consider the case where each town can sell 100 goods. Then for case: 150 150 0 with maximum transfer between any 2 towns=50

    You cannot transfer from town 0 to town 1 before transferring it to town 2.

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

      Dear meeeep,

      Edit: In your example, 50 goods are transferred from cities 0 and 1 to 2. Then there will be 100 goods in each city — my code covers this sample case.

      But I have made an example, which will break my code:

      3 2
      3 1 0
      0 0 4
      

      Here, 3 goods will be transferred to 2-nd city: 2 from 0-th, and 1 from 1-st.

      A better way is to move 1 unit of good from 0-th to 1-st city, and then move 2 goods from cities 0 and 1 to city 2, that is 4 goods in total.

      I supposed that there should be only direct transfers, that the same goods couldn't be transferred from city 1 to city 3 via city 2.

      Hope to read the description more thoroughly and do better next time.

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

Good thing that pretest were strong this time. Made me realize my mistake!

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

So fast system testing

»
14 months ago, # |
  Vote: I like it +9 Vote: I do not like it

At least I got the taste of being yellow (orange) for a while! :(

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

    wow!! master

    i cant get out of green island xd

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

      Candidate master now :D

      Don't worry, you will get through it if you keep practicing. At this time last year I was cyan for a while (but actually my level was around 1700-1800, I believe) so good luck! :)

»
14 months ago, # |
  Vote: I like it +8 Vote: I do not like it

AC D at 2:52,got 600 pts,:D FST B,lose 900 pts,:( gg my friend,return to div.2

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

Is the same seed random different number in different machine ? Because i used this code to generate hack case and it output differently in cf and local. I tried to run it in ideone and it gives the same as local and different in cf.

(http://codeforces.com/contest/724/hacks/261983/test)

(http://ideone.com/siTEFD)

»
14 months ago, # |
  Vote: I like it +35 Vote: I do not like it

 I check my program again and again,but I don't realize that I have edit my header code before somt time ago,when I write another problem...

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hmmm , I afraid of that and always I change name of define after changing it's definition. because it's the last thing that we notice it ...

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sry for necro-posting but how is this editor/IDE called. Ty in advance

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

For 2B why wouldn't switching a pair of columns in every possible way and then checking if for each way if it is possible to get a valid solution by making at most 1 swap for each row work?

http://codeforces.com/contest/724/submission/21298730

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

    The idea is correct, the implementation is wrong.

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you tell what is wrong?, I can't figure it out.

»
14 months ago, # |
  Vote: I like it +91 Vote: I do not like it

 .
lol

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

Questions were good...

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

Who can help me find why I got WrongAnswer with this code(http://codeforces.com/contest/724/submission/21298755)...

I got the correct answer on my computer but wrong answer on codeforces...

(Maybe I don't know something about codeforces? :D)

»
14 months ago, # |
Rev. 2   Vote: I like it +45 Vote: I do not like it

is there any place to make a bug report?

»
14 months ago, # |
Rev. 2   Vote: I like it -16 Vote: I do not like it

Deleted

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

How to solve D? and How to solve C using CRT ?

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, I don't know about CRT, but if you are looking for a solution based on Number Theory then you can check out mine 21299508

    The 4 linear diophantine equations represent the four types of points you get when you expand your rectangle to account for reflections (see this problem's discussion in the blog for further explanation 241C - Mirror Box, it redirects you to this: Codejam problem), and you need the minimum solutions with both x and y positive to find the closest of the points of that type having x == y.

    I failed during contest to solve those diophantine equations properly (a, b negative and getting the min x), do you know any other problem where I confirm if now I know how to manage such tricky requirements?? Notice I don't want to practice finding the equations, I just want to test my solver, although the problem being nice/hard is always a plus.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Reflect the box over the top and right sides, with the bottom left corner at (0, 0). So in the 3rd sample, all the boxes have left corners (7x, 4y). Note that the path of the ball is then equivalent to y = x. We can find the stopping point, which is the top right corner of some box, in the form (mk, nl) for some (k, l). It's also on the path, so mk = nl, and the first hit is at (lcm(m, n), lcm(m, n)).

    With some experimentation, you can see that for some point (x, y), it's also equal to all the points ( ± x + 2nk,  ± y + 2ml) for some (k, l). (In each box, there's 1 point). And because it's on x = y, we can use the 4 congruences

    We find the minimum such a, and check if it's  ≤ lcm(m, n).

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

Any ideas on how to solve D?

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

    Notice that if the greatest letter used is P, then all occurrences of letters 'a', 'b', ..., P-1 and some (possibly all) occurrences of P will be used in the answer. We can find P easily in O(N*ALPHABET_SIZE). Let's insert the positions of letters 'a', 'b', ..., P-1 into a set and then loop over all intervals ([1,M], [2,M+1], ..., [N-M+1,N]). If the current interval [L,R] has no 'a', 'b', ..., or P-1, then we should choose some of the occurrences of P in this interval [L,R] and insert it into the answer. It's easy to see and prove that it's always optimal to take the rightmost one. Everything I explained can be done with set linearly, don't look at my code, please! PLEASE!

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider the sorted version of the input string. The most crucial observation is that the best answer must be a prefix of this string.

    Let's binary search the length of the answer, the only problem is how to check it fast. An useful insight is that any prefix contains every positions of the same character, except one. So the problem reduce to this: Given the picked positions, select some more positions in order to fulfill the requirement, this can be done greedily in O(N).

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

    First notice that if you where to take only the smallest letter, then the solution is the least number of positions with that letter on the string fulfilling the "every m..." condition.

    To solve that problem a simple greedy works: go from left to right only taking a position if you passed over m positions without taking any, and take the last you have seen (remember this is only considering the smallest letter ie. 'a' if it existed), if there is no last seen position closer than m to current position then we can't solve it using the lowest letter only.

    Now back to the full problem is easy to prove that if we are using >= 2 types of letters is optimum to take all the positions of all but the greatest of the types of letters. Because inserting them before the greatest character makes the solution string smaller.

    Full solution is iterate over the greater character c to use and then perform the greedy described but taking all positions of the characters smaller than c.

    Link to my solution: 21281704

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

    I solve D with the 2- pointers technique. Fix the m first "window" ( interval from 0 to m-1). It must be covered by any of this characters. Then, we get the most right and most lexicographically smaller character (on position x). When we get this, we repeat the same problem in the (x+1,r+m-1) window. To do this we keep a structure pont[i] that keep the most right position of character i and update this with 2 pointers. After do that we have to add to the solution all character which is lexicographically smaller than your "bigger character". Sorry for my bad english ;/ My solution: 21297160

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

Unable to find the error. Please help. Got WA test 28.
Code is readable I think.
http://codeforces.com/contest/724/submission/21290857

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

    consider this test:

    2
    aba
    

    Answer : aa

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

    in line 65 you 'erase' too many positions, and besides you cannot guarantee last will become 0 neither (line 67).

    In the example huansuz1 provided you find a problem in position 1 (the one with the b) and it can be fixed, but last would become 1 not 0, and you cannot 'erase' the position 2.

    fixed solution: 21301915

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

Spent the whole time trying to figure out an efficient solution to problem B :/ Didn't see n, m, were only 20 and could be solved by brute-force. Read TooDifficult's solution and it is what O(nm^3)?!!

Anyways, any tips/hints for an optimal solution that can solve for large values of n. What I thought was to make a list of potential swap-able columns depending on number of unordered elements in rows (3, 4) and then eliminating them.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution is m*n Find all the possible pairs to swap Max 4 elements can be in wrong place For 4 elements in wrong place, there should be only 2 pairs For 3 elements in wrong place there will be 3 pairs For 2 elements in wrong place 1 pair I made all these possible pairs and at last checked if every row gas some common pair then ans is yes else no This solution is of course an overkill. I wrongly computed brute force so wrote this solution

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

Any ideas on how to solve E?

  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it +95 Vote: I do not like it

    We can model that problem as network flow as follows : create a source node (let's call it 0) and sink node (let's call it n + 1). Then we are asked to find maximum flow in network with edges 0 -> i, cap = p_i for 1 ≤ i ≤ n, i -> n + 1, cap = s_i for 1 ≤ i ≤ n and i -> j, cap = c for 1 ≤ i < j ≤ n (you can't get more than that because of the way network is constructed, you can get exactly this value, because this graph is DAG and you can always push flow in order of topological sorting). We could use any algorithm to find maximum flow, but this graph has O(n2) edges and they will all TLE probably.

    But maximum flow is equal by value to minimum cut, which we can actually find in O(n2) time and O(n) memory. Every cut in this network can be expressed as , . Now we can find value of dp[l][k] — minimum total sum of already cut edges if we have taken exactly k vertices into S from vertices 1, ..., l. Then it can be recalculated as follows: dp[0][0] = 0, dp[0][i] = inf if i > 0, dp[l][k + 1] = min(dp[l][k + 1], dp[l - 1][k] + s_l, dp[l][k] = min(dp[l][k], dp[l - 1][k] + p_l + ck (in first case only one edge is cut and this is edge from l to sink, in second case edge 0 -> l is cut and so are edges i -> l for . Of course, we need to keep only last two layers of this dp. Answer is min(dp[n][0], dp[n][1], ..., dp[n][n]).

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Good solution! I modeled the problem as maximum flow correctly in the contest, but I just forgot about the minimum cut. The problem is very nice!

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

The same code submitted from different c++ versions gives different verdict
http://codeforces.com/contest/724/submission/21301362
http://codeforces.com/contest/724/submission/21299482 . any guesses why?

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

    You have a bug in function next_point. y2 does not initialize. Likely you confused y1 to y2.

    ll x2, y2;
    if(dir == 1) {
    	if(n-x1 > m-y1) {
    		x2 = x1 + (m-y1);
    		y2 = m;
    		dir = 4;
    	}
    	else {
    		x2 = n;
    		y2 = y2 + (n-x1); //BUG
    		dir = 2;
    	}
    }
    

    P.S. Sorry for the bad English skills

»
14 months ago, # |
  Vote: I like it +28 Vote: I do not like it

why is a page like http://codeforces.com/ratings still blocked so long after the contest is over?

»
14 months ago, # |
  Vote: I like it -7 Vote: I do not like it

MY color changed

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

Ratings have been updated but the user rating graph is not updated.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And now the ratings have been reverted back too. Whats happening?

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Don't worry, I'm sure they'll update them back. They've probably finished with the cheating testing. The ladder changed a bit, so our ratings will too.

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes! I guess they are re-calculating the ratings after removal of unfair participants.

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

      Back to normal now. :)

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

After given rating why unrated me. http://codeforces.com/profile/Alhelal_WA Please check..............................

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

Editorial delay again

»
14 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Quite a long time for the next round :D

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

Any ideas on how to solve F and G? thx!

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

Can someone explain the logic behind problem C. What I could think of is mapping the room in both directions till it becomes a square of lcm(a,b)*lcm(a,b) and then map the corresponding points and check if it lies on the line y=x. Thanks in advance.

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

    consider bound as mirror

    then every action can be performed on another side.

    therefore, all points' coordinates are (x,x) (x )

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

      Thanks for the explanation. I had figured out this but couldn't find a method to solve for the time. Can you brief me on it.

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

        I can suggest you to draw an image and select one random point (sensor), which you will reflect after each passing through border. Then you will see that point with coordinates (x,y) reflects to (x, 2*m-y) or (2*n-x, y).

        After some experiments you can notice that going through sensor equals to going through any of points like

        (x, y)
        (x, 2*m-y)
        (2*n-x, y)
        (2*n-x, 2*m-y)
        

        AND points like mentioned above, but with +k*2*n to first coordinate, or +l*2*m to second coordinate.

        It looks like this:

        In other words, you should find a first point (x',y') such that

        (x' mod 2*n = x   OR   x' mod 2*n = 2*n-x)
        AND   (y' mod 2*m = y   OR   y' mod 2*m = 2*m-y)
        

        Consider all four combinations and solve an obtained system of equations. I can suggest my code for reference, but I think it's not clear and mostly devoted to solving of Diophant equation: http://codeforces.com/contest/724/submission/21292371 All I said you can see in these lines:

        val e1 = arrayOf((n*2 to x), (n*2 to (n*2 - x)))
        val e2 = arrayOf((m*2 to y), (m*2 to (m*2 - y)))
        for ((m1,v1) in e1) {
          for ((m2,v2) in e2) {
        
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody tell me the algorithm of problem b

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

editorial?

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

How to solve G ????

»
14 months ago, # |
  Vote: I like it +2 Vote: I do not like it

roses r red violets r blue codeforces is unusual just like u

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

Can problem D be done using this approach: starting from index 1, for each window of length 'm', we find the smallest character and add it to the answer. For checking the smallest character, set can be used with the element stored being (character,index). As we move the window, we remove the first element of the previous window and insert the new element of current window, then check if the new smallest character is the same as previous. If it is not, we can add it to our answer. Let the answer be 'ANS'.

At the end, we can iterate through the string and for each character that is not added in the answer, check whether it is less than the largest character that exists in 'ANS'. If yes, we can add it to answer and continue.

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

Hi, Can anyone explain why test case 49 for Div2. Batch Sort Problem is "YES". 3 3 1 2 3 3 1 2 1 3 2

According to my code, I'm getting it as "NO". Is there a way we can get the required 1 2 3 permutation in every row.

Please help...

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Make 1 3 2 in every row and swap columns.

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ohh. .Thank You. I was only checking the columns first and then rows.

»
14 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Hope better English statements,I also hope that my Rating can rise as well.

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

BTW, there was very similar to 724F - Uniformly Branched Trees problem in Gym: 100125C - Chemistry. Solutions for both problems differ in one small if-clause (ignoring modular arithmetic functions). See difference: 21344515 and http://pastebin.com/Gp0RKzmG

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

Could anyone tell me the reason that greedy is wrong in problem E ? Thanks ~:)

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

Nice photos and Nice contest.