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

Hello Codeforces!

On Dec/15/2018 17:35 (Moscow time) Educational Codeforces Round 56 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extented ACM ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

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

The problems were invented and prepared by Roman Ajosteen Glazov, Adilbek adedalic Dalabaev, Vladimir Vovuh Petrov, Ivan BledDest Androsov and me.

Good luck to all participants!

Our friends at Harbour.Space also have a message for you:

Hello Codeforces!

We are excited to announce that the Hello Muscat Programming Bootcamp registration is open! The camp will take place from March 9th to March 15th, 2019, and our early bird discount of 15% is going until December 15th!

This next edition in our Hello Programming Bootcamp will run in parallel with the traditional Moscow ICPC Workshop — both Bootcamps’ contests will be identical, and contestants will be able to see their position in the General Leaderboard. Every day, both camps will be competing simultaneously, 4,000 kilometers from each other!

REGISTER FOR THE BOOTCAMP

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 waynetuinfor 7 190
2 nuip 7 226
3 Ali.Sh 7 246
4 danya.smelskiy 7 252
5 Batrr 7 272

Congratulations to the best hackers:

Rank Competitor Hack Count
1 9646516 75:-20
2 interestingLSY 49:-24
3 NIKITA_BY 12:-1
4 katana_handler 11
5 marismmm 8
298 successful hacks and 565 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A sorry_stefdasca_snsdsux 0:01
B anti_my_abis 0:02
C Golovanov399 0:05
D Golovanov399 0:09
E ko_osaga 0:25
F gritukan 0:28
G tfg 0:09

UPD: Editorial is out

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

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

Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).

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

Clashes with COCI #3

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

    Best plan is participate in AGC29 and after 15 min participate in this round.

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

Yes, it is rated for Div. 2

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

gritukan is back

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

Is D bipartite checking?

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

    yes

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

      Pls explain in detail.

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

        check if each connected part graph is biparite, for each part color verticles with i.e. red and black and calculate number of red verticles. Then the result for each part is 2**red + 2**(part.size() — red) [you can put two's either in red verticles or black ones]. Multiply all numbers for final result, put modulo If m =0 , put 3**n % modulo. See my submission

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

      For a long time I thought graph was connected. After knowing that in hurry I used addition principle instead of multiplication :(.

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

how to solve D ?

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

    If graph contain odd cycle, answer is zero as no valid assignment can exist.

    Otherwise, let us find 2-coloring of each connected component in graph. Say, x nodes are colored red while y nodes are colored black. There are exactly pow(2,x)+pow(2,y) ways to color this component. Take product of this for all components.

    Reason of pow(2,x)+pow(2,y). You need sum of edges to be odd. So, one of the value on edge is 2 and other value is either 1 or 3. pow(2,x) assume we assign all red colored nodes with either 1 or 3, giving pow(2,x) choices. Same for y.

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

    It can be easily solved with BFS. And I came up with it a long time later, but I couldn't solve it because of Memory Limit Exceed.

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

It took me 4 wrong tries to actually realize that author has not mentioned that Graph will be connected in Problem D :'(

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

    i asked him . he said no !

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

    Graph doesn't have to be connected.

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

      Yes, I know. I actually assumed from the beginning that it will be that was the problem.

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

For those wondering about high submissions for G, You might find this problem interesting :)
MDIST

Can anyone share their idea for E and F?

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

    let's say p2[x] is position of x in second permutation, then you need to find number of l2 <= p2[i] <= r2 and l <= i <= r. It's easy to solve it with bit and sqrt decomposition.

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

      Wouldn't the complexity be n*root(n)*log(n) as for each block we need to find out how many values are there lying between l1 and r1, Also, if we use merge sort tree, we can reduce the complexity to n*log^2(n) as the problem is effectively calculating the no. of numbers that are between l and r in a particular range.

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

    In problem E you have to divide both permutations to blocks of length sqrt(n) and than make some calculations.

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

    My idea in E was creating sqrt(n) segment trees, so each of them contains a number of elements in the segment in the array b, that exist in according sqrt-bucket of the array a (t[s][l..r] — number of elements that exist both in in segment a[s*sqrt(n)...(s+1)*sqrt(n)] and b[l...r]). So it should have been some sort of sqrt-decomposition on segment trees.

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

    In the problem MDIST for 2-dim , we have to use 4 segment trees. But since in G there are more than 2 dimensions we have to use 2^k segment trees where k is dimension of the point. Is there any other way to do this problem?

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

I got a couple of wrong answers on D because I had mod = 1e9+7 saved in my template and forgot to change it to 998244353, and when I finally realized the mistake I corrected it in the last 10 mins. For those who say what's the use of setting mod to such a weird value its for people like me :-p

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

How to solve C? I made a great effort to solve it by using greedy algorithm only to get a wrong answer on #9.

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

    Yours approach looks correct.

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

      Yes,you are right. Thank you! Maybe last night I was too tired to stay calm. As a result, I dropped to green :(

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

    It's how you approached it.

    I did like this: split array a into halves, start filling from the middle of a (i.e. from right to left of array b).
    Denote the element

    Unable to parse markup [type=CF_TEX]

    as x, the two middle elements of a will be x

    Unable to parse markup [type=CF_TEX]

    2 and x - x div 2 respectively.
    For the next elements, let's denote the ones we need to fill in the left half and the right half as L and R respectively. Also, we have MinL as the minimum of filled numbers in the left half, MaxR as the maximum of filled numbers in the right.
    Obviously L ≤ MinL and MaxR ≤ R. From there, you can easily split the element from b into two most optimal halves that satisfies both inequalities above.
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did the same mistake :( So, now I have made a macro with int as long long.

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

I liked D. So, for any edge (u, v) exactly one of the nodes will have value 2.

If the graph has odd length cycle, then its impossible. Otherwise, simply do a black-white coloring of the graph. Now let # of black nodes be B.

Then in one case you can write 2 in B nodes, and the rest N-B nodes will have 2 options (1,3). In second case you can write 2 in N-B nodes, and the rest B nodes will have 2 options (1,3).

Ans = 2^B + 2^(N-B)

Code: https://ideone.com/2YmsN5

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

    Damn it!! I know understood how people solved this question in around 5 minutes. Nice one!

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

    Technically i think this is incomplete, it never says that the graph is connected. So use this solution for every connected component, and then multiply the solution of each one.

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

      Correct. I added that in the comments in my code. I was just highlighting the idea behind problem.

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

    Why this is giving TLE for a trivial case although I've implemented exactly this approach. code
    UPD: removedmemset() and it ACed :)

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

Are there faster solutions than Nlog^2N in E and Q*(2^K)*logN in G? Got TLE on both.

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

Problem D is pretty good ^^

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

For E, I couldn't pass a segtree of ordered_set in 6s. Is there any other better solution? Or it was just intended that we use BIT instead of segtree.

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

    Same here. After writing all that and getting TLE:

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

      I was doing with the same approach but could not complete coding. I think i would also have got the same verdict. :-p

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

    solve problem in offline: ordered_set -> BIT

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

    You can pass all tests with naive solution if you want in 5 seconds

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

      Why do you use alignas in your code? This is the first time that I'm seeing this.

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

        With alignas(32) pointer to array beginning will by dividing by 32-byte, or 256-bits. It allows GCC to use assembler command vpmaskmovd with AVX2 extension. You can read about vpmaskmovd (_mm256_maskload_epi32) this. So it needed only for fast loading to 256-bit cpu registers from memory.

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

          This is super interesting (and impressive). I have some followups:

          1. So I assume that it always makes sense to use alignas(32) before every array declaration? (One side question, it doesn't help to add that before a vector<int> declaration does it?)

          2. Do you know any other (hardware) tricks like this?

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it +5 Vote: I do not like it
            1. In case with vector you need to write own class aligned allocator and put it in vector template parameter.

            2. No, I know only about alignment. C++ has operator alignof(type) like sizeof(type).

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

    It's kind of unfair that the problem setters kept TL so tight that this is happening.

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

    Do you mean a merge sort tree?

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

Am i wrong or O(m * log^2) solution should get TL.

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

has anyone done E with Bitset ? I got TLE at testcase 13

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

What will be the Rating of problem D?

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

Why did this get TLE?

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

    Never mind, just got accepted. Never thought memset would pose a problem though.

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

      Same problem tle due to memset. Would never use it again ;)

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

        I think memset is still quite important sometimes. Just need to evaluate better next time!

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

          memset() time complexity in your code is O(MAXN) and you do it every test cases giving total time complexity O(T * MAXN) with T = 3*10^5 and N = 1 for every cases, the code will definitely TLE.

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

            Thanks but I already figured it out before getting accepted lol

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

Check my submissions if you are looking for challenging hacks. You have to complete 4 funny tasks. Good luck :)

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

    Actually your C is not hackable since the corresponding rand() sequence does not correspond to a valid input sequence (since you should be able to form some sequence a1, ..., an out of it per the problem statement).

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

      The random sequence b is increasing therefore it is possible to make sequence a.

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

        That is not a sufficient condition. What is a sequence corresponding to n=4, b = [2, 100]?

        Here is the random sequence for your code. Validator doesn't accept it.

        40
        42 18468 26335 36501 49170 55725 61479 79359 86963 94465 105706 118146 123282 136828 149962 150492 162996 171943 184828 195437
        
        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          You are right. I should have made decreasing array. Sorry for it. I uploaded the correct code. 47077025 Thanks for noticing and congratulation for the hack. If anyone else wants to hack: 47077601

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

    I'm quite confident your C is impossible to hack because it must be possible to recover the array from the input, but having your array as input doesn't correspond to any array from the task.

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

I had the same sqrt(N) blocks idea for E but ended up with memory limit exceeded. Did I derp too hard or was there something I'm missing? I had a 450 x 200005 int matrix at most

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

What's the hack for problem D?

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

    If someone is clearing the whole array of size 300000 for every test, then it'll TLE out.

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

      No that's not a hack test, as it appears in the pretests (Test: #21)

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

        My bad, I missed a '0' for t. It should be 300000. Test #21 is shy of one '0'.

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

My accepted solution for problem E in O(n * m) time works 5225 ms.

Can anybody hack it? Maybe halyavin?

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

Can anyone tell me, why i am getting compilation timeout???submission

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

Solution for F?

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

halyavin is coming!!!

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

I've just started using CodeForces and this was my first contest (and I got 2 accepted solutions). Can someone tell me:

why I still dont have a rating ? Will my profile be updated later (after few hours) ?

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

    There is hacking phase after Educational rounds which lasts for 12 hours then the system testing will begin, it takes around an hour. after all of this your rating will be changed.

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

      Wasn't System Testing done before the Hacking Phase? If System Testing has not started, the competition status will be displayed as 'Pending System Testing'. However, the current state of the competition is marked 'Finished'.

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

        No, it was the judging of the late solutions that were submitted on the last seconds.

        after the hacking phase, all of the solutions will be rejudged with the complete testset not only the pretests (this is the system testing).

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

      Thanks @Khaled_Mohamed !

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

47050528 hey, this is the fisrt time i am competing. Can anyone explain me whats wrong with this code for first problem.

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

    You were doing a wrong greedy.

    Since the constraints are pretty small, you can just brute force the answer: an answer i will be considered correct if 2i ≤ x ≤ 7i.

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

    When input is n = 29, your code doesn't give any output!

    After this step:

    std::cin>>x;
    rolls=x/7;
    x=x%7;
    

    'x' becomes equal to '1' and it can never become '0' in below mentioned conditions from your code:

    rolls=rolls+ x/6;
    x=x%6;
    rolls=rolls+ x/5;
    x=x%5;
    rolls=rolls+ x/4;
    x=x%4;
    rolls=rolls+ x/3;
    x=x%3;
    rolls=rolls+ x/2;
    x=x%2;
    

    So it doesn't print the output at this step:

    if(x==0){
         printf("%d\n",rolls);
    }
    

    PS: Think easy :)

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

      I've seen this code from other users, but I haven't thought of hacking. :(

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

      47059050 Can you please check this submission also. Thanks for explaining!

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

        'rolls' is uninitialised! Change it to rolls = 0;

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

          thanks man. It got accepted.

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

Can anyone please tell what is wrong in this solution for the problem D code

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

Can anyone explain the solution for problem C? I can't understand why we r taking a max of b[i] and b-a[n-i].

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

    a[i]=max(a[i-1],b[i]-a[n-i]) would ensure that a[i]>=a[i-1] which means that sequence is increasing and also a[i]>=b[i]-a[n-i] which means a[n-i]>=a[n-i-1].

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

Can someone please point out why do I hit a time-limit-exceeded on test 2 with this submission?

https://codeforces.com/contest/1093/submission/47082541

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

    Graph doesn't have to be connected. Here is example: n = 3 * 10^5, m = 0 Then this part:

    Spoiler

    will take n^2 time. Another bug in your code is in this line:

    ans += (1 << red) % MOD + (1 << black) % MOD;
    

    black and red can be bigger than 64. Better option is to just count every 2^k % MOD at the start of your program:

    POT[0] = 1;
    for (int i = 1; i < N; i++)
        POT[i] = (POT[i - 1] * 2) % mod;
    
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

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

    My way to solve this problem (not very efficient, but it passed):

    Represent each number as a point , then the problem will become count the number of points in the rectangle with two opposite vertices (la, lb) and (ra, rb). You can easily solve this problem with compressed 2D BIT.

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

Hi! I did really enjoy solving these problems, thank you to all the authors! Can please someone explain, what does C# dislike in test 10 of D so much, that it gives memory access error? 47082830 I understand, that the best solution is to never use C# for contests, but anyway

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

Can anyone explain solution to E with ordered statistics set? I saw few codes that get AC but I don't understand them all. And what does this magic loop:

for(int i = x; i <= n; i += i & -i)
»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone figure out why my program will get many negative outputs in problem D? 47086094

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

    a *= a % c means a = a * (a%c), which is not a = (a*a)%c, so it will overflow.

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

    I spent ages debugging this issue. From now on I have decided not to use shorthand [+-*/]= operator in C++ in such cases ....

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

i missed this -_________-

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

anyone solved D with DP ??

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

    But why?

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

      because i doesn't know the coloring in graphs

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

        It's pretty straightforward. You can use graph traversing algorithms of your preference (BFS or DFS) and just change used[] array to color[] array. You only need two colors for this problem. Then assign all children with a different color of its parent. Also, check that no neighbours have the same color (it is only possible if you have a cycle of an odd length).

        As for DP, I have no idea how such a solution would look like, but it probably would be an overhead.

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

          okay this may be straight-forward but what if i take a look as every edge has two vertices and if they are not colored yet i will color each of them with diff colors and my state will be the edge and the color of the 2 vertices so 3D array 0 if not colored 1 if odd ,2 if even but to consideration that you can color 2 times the odd vertices. I know it is much harder this way but i like the way to transform graph to dp. here is my solution http://codeforces.com/contest/1093/submission/47076428

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

Will there be an editorial?

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

How would we do problem E? I am getting TLE with my approach in test case 10

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

Can anyone help me with my code for D. I'm getting TLE for test13 My Submission

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

please release the editorial of this contest??

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

The idea behind E's solution is good. You have to choose such a block size such that n*(block_size+log(n)*n/block_size) is minimised. It is not necessary that optimal block_size is root(n),

PS: E passes with block_size = 3000.

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

I am pretty sure that problem F is the exact same problem as 204D - Little Elephant and Retro Strings. but instead of using only 2 values he uses k.

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

Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).

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

Does anyone know when the editorial will be released ?

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

Can anyone tell me what am I doing wrong in part D.

link : https://codeforces.com/contest/1093/submission/47249694