Vovuh's blog

By Vovuh, history, 5 weeks ago, translation, In English,

Hello!

Finally I am freed from the big part of summer cares and I can continue the preparation of Div. 3 rounds! I decided to add something written by me to this blog because TryToKnowMe (and many others, i think) noticed that i am really copy and paste this text from one announcement to another changing only contest name and start time. But... Who knows, may be this time which is saved by copy-pasting the announcement allows me to prepare the problems better?... Let it stay a mystery. So, let's go.

Codeforces Round #498 (Div. 3) will start at Jul/16/2018 17:35 (Moscow time). You will be offered 6 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail PikMike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

UPD: Also great thanks to the testers uwi, mareksom and ivan100sic for their invaluable help with the round preparation!

UPD2: Results table!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 HighPressure 6 236
2 LividFox 6 237
3 Rzuji 6 265
4 Syvail 6 273
5 khadgar1998 6 279

Congratulations to the best hackers:

Rank Competitor Hack Count
1 jhonber 131:-7
2 antguz 9
3 ducdien2267 9:-3
4 djm03178 6:-1
5 imlk 4

199 successful hacks and 232 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A eggmath 0:01
B eggmath 0:06
C thidailoc 0:07
D MoreThanANoob 0:23
E Student_of_Husayn 0:07
F NoTrolleNoLife 0:18

UPD3: Editorial is published.

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

»
5 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

hope halyavin the system tester also provides his service this time!!!

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I really want to know how does he do that so FAST!

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

      He uses some script.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      He should really do a screencast when he is hacking. I mean I don't get a test case for hacking until I have already given a solution which is accepted for the pretests and I have found a test case which is already in the problem statement and not matching my code

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

        The script is used only for testing the test case he feeds into the script on different submissions. The test cases are not generated by the script. He himself thinks of the test cases and then feeds into the script.

»
5 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

minimize hacking phase to 6 hours at least try it once if everyone agrees implement it permanently.

»
5 weeks ago, # |
  Vote: I like it -38 Vote: I do not like it

So it is unrated for 1600-1899?

»
5 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

let's hope strong pretests and fast responding server side...

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

Next contest starts after 10 days. MikeMirzayanov are you going somewhere?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone <3

»
5 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

Expecting more and more mathematical problems.

»
5 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

first contest after world cup ..

»
5 weeks ago, # |
Rev. 3   Vote: I like it +22 Vote: I do not like it

Vovuh i think you have to add this

penalte is 10 minutes so people who ask for it get downVote haha

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

    Big thanks to you! Added to the announcement.

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

    until now i have the most rated (upvoted) comment hahah ...

    and the most (downVoted ) will become true .. here ?!

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

      This comment really ruined your contribution :)

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

        you do not know me hahaha

        i make balanced comments +-

        contribution does not matter -101 is so good

»
5 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

I always feel comfortable with div 3 problems. So I love it very much.

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Sad that I may have to miss the round for my final year project work :(

»
4 weeks ago, # |
  Vote: I like it +42 Vote: I do not like it

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

Just mark the changes

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

For a long time, I am still in Cyan. :) Div 3, the road to changing color.

Many thanks about Div 3 idea.

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Don't worry buddy, we know you didn't copy pasted. Who need that when you have scripts lol

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

Why topcoders hide their faces behind anime profile pics?

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

i prefare regular div2 contest style not the ACM-style and hacking in contest time gives points ..

»
4 weeks ago, # |
  Vote: I like it -33 Vote: I do not like it

self-bombing

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

Hope that this will be my last div3 contest from next time I can participate out of contest.

»
4 weeks ago, # |
Rev. 2   Vote: I like it -12 Vote: I do not like it

Strong pretest :)

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

    Have you read this?

    You may edit your comment only for fixing grammar mistakes or small changes. Do not change the main idea of your comment. All previous revisions are available for others. Are you sure you want to edit comment?

    Main idea of Hope that this will be my last div3 contest from next time I can participate out of competition in div3. Never had that feeling :( and Strong pretest :) is not the same.

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Upvote for ivan100sic and good luck!

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

problem setters are ultimate!! hats off to them

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Probably, participants from the first division will not be at all interested by this problems.

I am always interested in Div.3 problem sets. :D

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

Easy offline solution for E using cartesian tree (treap). 40444978

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

    Easy solution for E using simple DFS/ 40428850

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

    Easy? The easy way is a preorder traversal

    (just realized it is probably sarcasm OOPS)

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

      Easy, because you don't need to think about it, just implement it.

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

      Yep, preorder traversal to save new array O(N), each query we can answer O(1)

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

      (just realized it is probably sarcasm OOPS)

      Oww, then I just realized my solution is so hard.

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

How to go faster than O(n2 * k) in B?

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

    Use k largest values for maximums of these segments, and then extend them.

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

    sort the values in reverse and find the index of top k values. then one loop would give you the size of each segment

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

      Can you explain more on how to get size of each segment?

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

        suppose I have [101,3,5,6,10,100]. So, I take a temp array and sort this in desc order. The temp[] = [101,100,10,6,5,3]. Now suppose we want to get the top 3, get the index of 101, 100 and 10 from original array and save it somewhere. idx[] = [0,4,5] (0 based indexing) . The size is 1, 4 and 1. You need to take care of duplicates. For that once you visit save the index and remove the element from original. I am very bad in explaining stuff. Submission: 40426181 .Please let me know if something is not clear. will try to explain more clearly.

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

    answer would be sum of k- maximum elements in array and keep these k maximum elements in a multiset then just traverse form 1 to n and if a[i] is element in multiset remove it and print number of elements from previous partition.

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

Can anybody explain problems D and F please?

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

    For D you just can see that changes makes cycles i -> n — i + 1. For every cycle find min changes.

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

    The key observation to solve problem D is that each letter in string A has 3 counterparts (except when n is odd and you consider the middle letter). These counterparts are the letter at the opposite position in string A, the same position in string B, and the opposite position in string B. You can think of these 4 letters as a group. Each group, after preprocessing modifications, must contain two pairs of letters. Once this observation is made, a bit of case-bashing can determine the number of modifications necessary.

    My solution for problem F was meet-in-the-middle. If you start from the bottom right corner, you can determine the possible values for any grid square which can result in a final XOR-value of k. I calculated these values along with the number of paths which resulted in these values up to the 'middle' of the grid (where Manhattan distance to either corner was equal to (n+m)/2-1). Then, the process was repeated starting from the upper left of the grid.

»
4 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

how to solve F?

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

    meet in the middle

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

    Notice that 20C10 is only < 200k, so we can use meet in the middle to get the answer -> DFS all possible routes from (1,1) until middle of grid and insert it into map, then DFS from (n,m) until middle of grid

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

      What about paths that don't go through the middle of the grid? I assume that middle is point (n/2, m/2).

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

        Middle of the grid can simply mean a certain Manhattan distance from the upper left of the grid (i.e. y+x==(N+M-2)/2), indexing at 0).

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

          Great solution! What will be the time complexity in this case? Thanks in advance!

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

            should be 2^20 * 20, i believe

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

              Since we are traversing just half the graph, once from (1,1) and once from (n,m), cant we just say it will be 2*(2^10)*(2^10) = 2^21?

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

                no, you don't multiply both halves when you traverse the graph. But each half individually is 2^20 ways, because 20 is only the halfway distance, and you have to choose either to go right or down. Last 20 is for the log factor in the maps.

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

                  Oh ok. Might sound noob but since one half takes 2^20 moves, and we traverse half the graph twice, shouldn't the complexity then become 2*2^20 = 2^21? And if we use unordered map which is essentially a hash table,can't we ignore the log factor coz of the maps?

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

                  unordered_map has test cases to counter against its usage, so I never use it anymore.

                  Yes, it will take 2^21, but the point is the complexity is n * 2^n still

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

                  Nice solution but how do we combine two half subproblems.Do we combine ans use binary search or something like that..

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

                  Can you explain any case for breaking unordered map I couldn't find any for that.

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

                  Couldn't find the original. This is pretty solid proof though:

                  https://codeforces.com/blog/entry/21853?#comment-322392

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

      Can you please suggest any good resources/problems with editorials for bidirectional DFS/ meet in the middle? It is a new topic for me. Thanks!

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

    Bidirectional bfs

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

there is no hacking in Div3?

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

Great contest, Problem set was so balanced and covered all topics perfectly. Ideal contest for div 3 participants. Dude make one div 2 as well, I would really like to attempt it officially :P

»
4 weeks ago, # |
Rev. 3   Vote: I like it +27 Vote: I do not like it

inYourDreaM hacked all his solutions!!

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

Realized the importance of time today !! :( But it was a great round.

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

why in Problem D my code get WA on test 3 -_-

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

    https://ideone.com/egWiTd here is my code -_-

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

      Your second condition in temp(=3) (i.e. b[i]==b[n-i+1]) is wrong. When a is "xy" and b is "uu", a can be preprocess to "ux" and then it can be changed into b using given steps.

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

    Check this test 2 aa bb Answer is 0

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

      yes, my answer is 0 swap(a1,b1),(a1,a2) so we can get ab==ab -_-, why it WA

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

        This one 2 cb aa Answer is 1 but yours is 2. Sorry i forgot that "note that you cannot apply preprocess moves to the string b b or make any preprocess moves after the first change is made"

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

      My code also got failed, could you please share some more complex test cases.

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

    Check 2 ab cc Answer is 1

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

    if(b[i]==b[n-i+1]) res+=2;

    In this case, you only need to do 1 preprocess step only. Your aim is to have two pairs of identical characters, so just change a character in string a to the other one.

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

    I think you are rejecting the case when all are four characters(a[i],b[i],a[n-i+1] and b[n-i+1]) are equal OR the case when N is odd and middle element a[i]==b[i].Solution 40472491

»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

my code is giving correct output for problem E in Sublime editor but wrong answer on the codeforces editor.How it is?

include<bits/stdc++.h>

using namespace std;
#define ll long long
vector<ll>v[200010];
vector<ll>vis(200010,0);
map<ll,ll>mp,mm;
vector<ll>gr;

ll dfs(ll s)
{
    mp[s]=gr.size();
    gr.push_back(s);

    vis[s]=1;
    ll a=0;
    for(auto aa:v[s])
    {
       if(!vis[aa])
       {   
         a+=dfs(aa);
       }
    }
    mm[s]=a+1;

}

int main()
{
    ll i=0,j=0,k=0,l=0,m,n,s=0,x=0,y=0,d;
    cin>>n>>m;

    for(i=2;i<=n;i++)
    {
       cin>>x;
       v[x].push_back(i);

    }
   dfs(1);

   // for(auto aa:gr)
   //   cout<<aa<<" ";

   for(i=0;i<m;i++)
   {
      cin>>x>>y;
      j=mp[x];

      if(j+y-1<=mm[x])
        cout<<gr[j+y-1]<<"\n";
      else
        cout<<"-1\n";
   }





}
»
4 weeks ago, # |
Rev. 2   Vote: I like it +38 Vote: I do not like it

Found some serious cheating going on here-

f20170604 Copied F from Roundgod --

40438080 Copied from — 40428801

Sad thing is that in order to hide it, five minutes later, this guy submits another code, with all the headers removed thinking he will not get caught.

Here is the second submission — 40438951

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

    What?How?I'm pretty sure that I didn't give my code to anybody...

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

      I hope you did not even mistakenly use an online compiler on a public mode. Highly unlikely but still.

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

        Pretty sure that didn't happen ,either. Have just changed my password. Thanks anyway.

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

      Did you try running that code on ideone.com or some other similar website?

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

        Nope. I used vim on my laptop, with gcc as the compiler.

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

    Finally found out what happened here... It turned out that I uploaded my code to my github after solving F... Have just made the repository private. My apologies.

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

      XD The guy wa 31 use the same idea and change your code a little bit But he got a wa So he submit your code directly to make sure that your code is right

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

      a master mistake costs 1000x times newbie mistake ..

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

      So he basically had your github repo open on one tab.google doesn't index so fast.

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

      Lol this has happened to me too.

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

    This can done easily with the help of Second id first he solves a problem and then he lock its problem and then see the code of any other guy and then he submits it with a different id.

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

      In div 3, he can't do that because it doesn't have "hack" and "lock", everyone can't see other's code until the contest ends.

»
4 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

" halve the grid diagonally not vertically nor horizontally you idiot! "

thats what test 22 on problem F would have said to me if it could speak.

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

    I went DP but full brute on bitmasks and got MLE at test 47. Hmm how come I passed that?

    My failed submission.

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

      the memory is 20*20*AllPossible xors

      All possible different numbers from taking the xor is a big number, thats why you Got memory limit exceeded

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

        Yeah, I meant, even bruting like that, how would I passed test 22 and dozens of tests following until that, while yours stucked at it? Just curious.

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

          Check the first tests they are meant for TLE detection.

          numbers are small thus their xor is also small and dp on these constrains work but when numbers are big dp will get you TLE or MLE whatever comes first.

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

            Alright, now I understand — difference in approach :D

            Thanks!

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

    How is diagonal better than vertical/horizontal ?

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

      If you go full brute, the maximum amount of bitmasks you have to handle is nCr(38, 19).

      Cutting vertical/horizontal decreases half the steps for one dimension, therefore the maximum bitmasks count lowers to about nCr(28, 9) or something similar — still insanely high and might not fit in TL/ML.

      Cutting diagonal decreases steps in both dimensions, therefore further lowering the bitmasks count, to about nCr(18, 9).

      (I'm not actually that certain in those combinatorics — those are estimated. Still you might get my points ;) ).

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

Hmm... is this normal??

image

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it -20 Vote: I do not like it

    it seems you do not know halyavin

    upd ..sorry wronge answer ..

    maybe arrays limits .. if conditions !?

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

    Check his solutions, he is using an if condition to hack it. for eg. In problem A, he used if(x==210400)return 0;

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

      Oops, that's bad, I see cheaters coming in waves :S

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

      How he knew that there was no value of (x==210400) ????

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

        Well, you can choose any random number and you'll have a very low probability of coincidence against pretests.

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

          and he succeed for all his 6 problems.

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

            Yes, for the same reason above. It's very feasible. You can calculate the probability for that to happen ;)

»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

ayush347 tried?

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

can someone help me to find the logical error for Problem D 40443887

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

    Fixed it: http://codeforces.com/contest/1006/submission/40452847

    The only change was: "if(ans[3]!=ans[2]) {...}" should be "if(ans[1]!=ans[2]) continue". ans[1] != ans[2] iff we have letters of type 'a a b b' and we shouldn't make changes in that case.

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

      but, in case of 'a a b b' , (ans[3]==ans[2]) ,so it wont increment the sum to sum+1.. So ,why is it getting wrong ljupche98

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

        You shouldn't check ans[2] and and[3] because they can be equal for case 'a b b b' (where the answer is 1) and 'a a b b' (where the answer is 0). What you should do, is check whether the groups have equal number of elements and that is, by checking ans[1] and ans[2].

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

Can anybody tell , why this 40450609 gives a runtime error on test case 2; Whereas it runs fine on removing the for loop for calculating subordinates O(n)

for(ll i=n-1;i>0;i--)
    {
        child[i+1]+=(child[i+1]==0);
        child[i]+=child[i+1];
    }

and calculating it when using dfs 40450928.

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

    In Example 1, your code has child [2] = 6, but this is obviously a mistake. In general, the value of child [i] is not determined by the value of child [i + 1].

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

      Thanks, for the help, That was a very stupid conclusion i made :(

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

When will the ranting be updated?

»
4 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

I think the difficulty differences between problem C and problem D is so big. It make participants uncomfortable.

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

Problem D :

7 abacaba bacabaa

  1. Replace a1 with b
  2. Swap a5 and b5
  3. Swap b3 and b5
  4. Replace a4 with a
  5. Replace a5 with c

Answer should be 3. Please correct if I'm wrong

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

    First do pre process , then swap.

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

      Miss that part of question. Thank you

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

      I first swapped to check how many matching cases can be made with given type of swaps after that it was just count(a[i]!=b[i])

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

    Look at this

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

another contest saying an array can be a birthday present, how boring you guys are!

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

Where's editorial ?

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

    It will be soon, wait a bit please

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

why sysem testing didn't start

»
4 weeks ago, # |
  Vote: I like it -27 Vote: I do not like it

I seemed to have used the right logic for B but my solution got hacked. It seems I didn't factor in some edge cases. Can someone help out?. My solution is here. Thanks in advance :)

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

    You should tell your logic too instead of expecting someone to figure it out and tell you whats wrong with your code.

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

      I am sorry. Will take care from next time. My logic was to find the k maximum elements of the array and then find those k elements in the array and mark them as -1. And then print the sum of those maximum k elements to get the first line of output. To get the second line of output I would count the number of elements till I encounter -1 and set counter as 0 again whenever I encounter -1. Further to take care of the test case of the encountering the last -1, I will simply add the rest of the elements left in the array to the counter. Hope that explains my approach :).

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

    you always ask very dumb questions

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

      I appreciate your criticism. Just that codeforces community has been the only bunch of people who seem to cater my dumb doubts. :)

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

    Your in-mind logic was correct, but you made a mistake in your invector function: after finding the desired element, you must terminate the function immediately (otherwise it will keep marking other elements with the same value).

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

      Thanks, I got it now. For multiple occurrences my code was simply making them -1 in all of the positions. :)

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

when is the result expected to come?

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

where is the rating changes??

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

Vovuh it was a good round :)

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

what does the test 16 in my submission mean? where does 3917963 come from?Vovuh

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

Very late in rating update.

»
4 weeks ago, # |
  Vote: I like it +86 Vote: I do not like it

wow, You forget to make f20170604 unrated... 40438080 is a directly copy from 40428801. Why this guy still rated? Vovuh

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

    After searching through past blogs, it seems like cf admins don't care about cheating instances like these. http://codeforces.com/blog/entry/60377#comment-442301 and http://codeforces.com/blog/entry/60573 were pointed out but the cheaters have not been disqualified :(

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

      Cheating on your girlfriend is a far more egregious crime than cheating on Codeforces, because Codeforces will forgive you but your girlfriend will not.

      Therefore I propose that anyone who participates in Codeforces contests must have a girlfriend, so no cheating will occur. #ProblemSolved (This implies that eggmath will not be able to compete, SAD!)

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        eggmath is too busy traversing trees to deal with these trivial corporeal matters.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
          Rev. 2   Vote: I like it +6 Vote: I do not like it

          My theory is that eggmath is actually a monkey who works at Facebook; hear me out.

          First, we see that YouTube's error message mentions "a group of highly trained monkeys" who are working to fix the error. YouTube's HQ is located in San Bruno, which is in Northern California. Guess what? eggmath lives in Northern California. This is the first clue that we are given.

          The other two clues are given in Facebook Hacker Cup. In the qualification round, Ethan is searching for a string. Do any animals actively search for strings? Yes. Cats and monkeys. Based off this knowledge, eggmath can be either a cat or a monkey.

          However, the next clue is pretty damning evidence: Ethan traverses a tree. Hear me out, I know cats can traverse trees too, but which other mammal traverses a tree better than a cat? That's right, a monkey. There is no other animal in the jungle that has such an agile and nimble body to traverse trees. If this evidence isn't clear enough, I don't know what is.

          Therefore, I believe that eggmath is indeed a monkey.

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

    Sorry, we will fix it soon. Thanks for the notification!

»
4 weeks ago, # |
  Vote: I like it -35 Vote: I do not like it

Maybe I have misunderstood something but...

It is told only the trusted participants of the third division will be included in the official standings table, but in standings there are many untrusted participants. And trusted participants ratings are affected by them. For example I am on 169th place in COMMON STANDINGS, but in RATING CHANGES and MY RATING HISTORY I am on 220th place, so my rating has been changed as I am on 220th place, Vovuh, MikeMirzayanov.

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

    In COMMON STANDINGS untrusted participants show up and then again disappear all the time.

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

    Sorry, it was my bug in the standings parser, the winners table may be wrong also in the some previous Div. 3 rounds. Now it is fixed (i hope) because i extracted the results manually.

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

      I am not so good in English Ой, извините, только что вспомнил.

      Кажется ничего не изменилось :( Видно проблема более глубокая и время MikeMirzayanov? Да ладно, не проблема. Спасибо, мне(и думаю почти всем) очень понравился ваш contest, а эту проблему можно решить, да?

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

    Also Mike knows about the bug with the standings table and it will be fixed soon i hope (really hope).

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

How do you mathematically compute the number of possible paths for problem F? I see many different combinatoric formulae here, but none of them are explained.

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

    Misunderstood your question.

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

      The number of paths for corner to corner can be seen as a permutation with repetition with formula (m + n)!/(m!*n!).

      The number of paths from a corner to the diagonal is 2^20 at most. When n = m = 20 each path is 20 steps and each step either down or right.

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

When editorial will be posted?

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

can someone explain how to divide matrix in problem f clearly.. UPD:GOT IT..clear and short codes are sometimes helpful;