MateoCV's blog

By MateoCV, history, 6 months ago, In English

Hola Codeforces!

I am happy to invite you to Codeforces Round #774 (Div. 2), which will take place on Mar/04/2022 18:35 (Moscow time). Notice the unusual time! The round will be rated for participants with rating lower than 2100. You will have 2 hours to solve 6 problems. The problems were authored and prepared by me.

I would like to thank the following people who made the round possible:

See you in the standings!

UPD:

Scoring distribution: $$$750$$$ — $$$1000$$$ — $$$1250$$$ — $$$2000$$$ — $$$2500$$$ — $$$3000$$$

Thanks to ak2006, video editorials for some of the problems will be available on his channel after the round.

UPD: Editorial

UPD: Congratulations to the winners!

Official winners:

  1. lydia1
  2. mjhmjh1104
  3. sbzhangjianjun
  4. Vsinger_MoQingxian
  5. WAduck
  6. woolim
  7. Iam1789
  8. yagoo
  9. Koba.rde
  10. dtc03012

Unofficial winners:

  1. Vercingetorix
  2. Um_nik
  3. hank55663
  4. Yuu
  5. dlalswp25
  6. MeliodasIRA
  7. rainboy
 
 
 
 
  • Vote: I like it
  • +643
  • Vote: I do not like it

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

Good luck and high rating.

»
5 months ago, # |
  Vote: I like it -48 Vote: I do not like it

Good luck to all Ukrainian contestants

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

Note The Unusual Timings (1 Hour Late)

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

gl ^ hf

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

best of luck for all♥️

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

Good luck and positive rating!!!

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

This will probably be my first contest in over a month...I'm awaiting -100 delta :P

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

    same... I'm awaiting losing my green after my first contest :P gl

    that wasn't true gonna get +20 :yayy:

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

      let's go! i'm having my series of defeat too

      i overslept so i didn't participate

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

      Losing Vir-greenity... Btw I am also hoping for the same :)

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

Good luck everyone. Maybe this round will help improve people's mood at codeforces.

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

    hello gagan plz guide me as i am stuck in newbie-pupil phase from a long long time and i don't see improvement also provide tips for dp if any. thnx in advance.

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

      The key to improvement is indeed just good-old practice. Now, everyone should choose a practice regime which suits them well. I just like you were shuffling pupil and newbie for 1 year. This year I started practicing more with a focus on solving questions rather than learning new algorithms. You only need a handful of algorithms like dfs-bfs, Dijkstra, dsu, segment tree to reach the expert but dp practice is very important. I practiced dp from problemset with filter-tag and started solving from 1000 rated questions and gradually increased rated questions. When I felt like I can do 1600 rated dp questions pretty confidently then I started randomly doing questions with gradually increasing difficulty from 1000 to 1600.
      Make sure you actually solve the questions and don't see the editorial until you solve it. If it seems impossible then try to read other people's code before checking out editorials. Do cp with your friends, discuss approaches and try to outrank your peers :p. This is what has worked for me till now, hope this helps you. Good luck!

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

        I think DP is the most important thing. segment tree is not too important at pupil stage.

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

          I was talking about the concepts which can land you to expert level.

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

            expert level doesn't need segment tree to be fair, binary search, greedy, simple DP, DFS/BFS and a little knowledge of graph.

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

      Hello

      Same for me i am stuck at newbie stage for last 2-3 months i have been doing it consistency with avg daily 4-5 of 1300 rated questions but still sometimes i am unable to solve or come up with an approach even for B of div 2 or with C

      Help appreciated

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

Maybe we have the opportunity to just focus on this round itself!

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

Look at the quality of the questions. My hands are too slow.Orz

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

Before the usual time was 16:35, then 15:35, then 11:35 ... What is the actual usual time ?

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

ooo thanks

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

Are we going to fight against "Robot" in this round?

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

I hope I am able to do the third question at least in this round :)

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

May C problem be solved by less than 2000 people. I want it to be an interesting one.

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

    Bruh This is every Cyan dream . That it has less than 2000 solves and we are among them . But sadly cheaters will never make it happen ;_;

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

      I would say and pupil too — last 3 contests happens to me top 1000 after A,B (top 100 last round), and then somehow stuck on C, and -∆, -∆, -∆

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

score distribution plz :)

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

First argentinian contest! Congratulations MateoCV

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

Contest after long time.Eager to participate

»
5 months ago, # |
  Vote: I like it -63 Vote: I do not like it

Let's Pray for Ukrain and hope good for the world

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

Good luck everyone! Have a good contest!

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

Argentinian round? Aguante el Diego, Talleres y FaMaF!

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

Good job guys, good luck.

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

Good luck!

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

good luck :)

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

Unfriendly time for Chinese contestants.

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

Finally a CF round after long time. All the best everyone.

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

This contest will be harder than previous contest!!!

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

Dear contest, How do you feel today? Yet another person commented on your announcement page rn (me). Since I said hi to you, please give +ve this time to me. yk the usual. thanks in adv

Regards, that random user asking for +ve in rating

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

Very cool scoring distribution 1000 — 750 = 1250 — 1000 , 3000 — 2500 = 2500 — 2000

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

there is no as a tester comment.

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

How many of you logged in at the usual time?

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

SpeeeeedForcesssss

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

    why? the number of people who solved C isn't high or too low

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

antonforces

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

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

I haven't coded recursive code in 2 years lol good to remember it with problem C

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

    I did it without recursion

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

      How?Plz share your approach..

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

        Store the factorials numbers <=1e12 in an array (I think the count of them is 13 or 14)

        Just iterate on all subsets of them (by iterating from 0 to 214) and then subtract the factorials number from n (let's call the resulting number as temp). After each subset, count the number of set bits in temp. This will be the number of powers of 2 required. Do this for all and keep track of min so far. Submission https://codeforces.com/contest/1646/submission/148374185

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

          you mean factorials?

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

            My bad, dk why I typed fibonacci. Corrected it.

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

        Solved it using bitmask dp on factorials <= 1e12 and pop count

        Submission: https://codeforces.com/contest/1646/submission/148339954

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

          I don't think there is any DP in your solution :p.

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

            sorry used bitmasks to generate all possible subsets of size 15 :)

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

            Why did the setters confuse with -1 where ans is always possible?

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

              Just to check that we are smart enough to think that . As its quite obvious that every no can be represented in binary form. So there no chance for answer to be -1.. But some ppl i saw do handle that case ;_;

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

      I think it's still the same complexity recursion can be done in a different approach of course

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

    I did with a mask-compressed DP...

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

It took me 2WA's and 50 minutes to figure out that for long long integers __builtin_popcount doesn't work and we need to use __builtin_popcountll ... :-/

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

    I realized it just before click submit button...

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

      I am just happy that at least I figured it out before the contest ended :)

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

    You should keep such things as #define (macro), easier to remember

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

    I suggest using std::popcount(). The only issue with this function in terms of competitive programming is that it requires x to be of unsigned type, so we have to cast explicitly if x is long long.

    int popcnt = popcount(uintmax_t(x));
    

    Of course, the simple macro solves this problem: #define popcnt(x) popcount(uintmax_t(x)).

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

5th test case of problem D...

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

it was so fun to write 15 nested for loop in problem C(p.s. I know recursive solution would also work)

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

    that means you don't know this

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

      I mentioned fun, actually you don't know what I know so please read comments carefully next time

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

Imagine wasting 20 mins debugging E because you "simplified" $$$\frac{lcm(x_1, x_2, \ldots, x_k)}{x_1}$$$ to $$$lcm(x_2, \ldots, x_k)$$$ without thinking properly T_T.

Also I can't exactly describe it, but CDE feel like they are somehow standard yet fairly interesting at the same time. Maybe its because they have extremely simple and natural formulations which don't feel like they've been forced to match an idea?

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

A nice contest for me!! I loved the problem C. Would love to share my experience while solving problem C,

Initially after reading the problem , I immediately thought of solving it using subset generation through bitmasks , because i thought the size of factors + powers of 2 would be around 30 , but turned out it was ~52. So i drifted a bit & thought of solving it using DP(using coin change approach) but that is also not feasible.

Solution :

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

    you only need to bitmask factors, then greedy choose powers of 2 for the rest.

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

      Yup, thats what i did. I don't think you need to greedy choose powers of 2 for the rest , because the remaining number's binary representation containing the set bits already is the least number of powers of 2 required to represent it.

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

Logic for C?

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

    Note that n can allways be constructed with number of its bits, since these are powers of 2.

    So construct all possible sums of factorials (that are at most 2^14 since there are only 14 factorials in range), subtract each one from n and count the bits of the difference.

    Smallest number of set bits in difference plus bits in factorial sum is ans.

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

How to do F?

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

What d hell is test case 5 of D -_-

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

    Either a large graph or something that kills the incorrect bipartite idea I guess.

    Try the following graph if you don't get why bipartite is incorrect:

    Input Graph
    Answer
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There are cases where it is optimal to not take two neighboring nodes. Splitting the tree to a bipartite graph and then taking one of the two parts is not always optimal. The idea is similar to the well-known DP problem "Maximum sum over array such that no two elements are adjacent" but implemented on a tree.

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

    2,3-dimethylbutane

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

My Idea for D :

  • Take all leaves to be good vertices
  • Now all parents of the leaves (call it buds) are assigned with weight = 1
  • Now the graph is split into separated sections with "buds" as boundaries for each section
  • For each section, I solve them independently by coloring it "bipartitely". In each section, I find which gave me the best arrangement whether the color "black" / "white" on this section are good vertexes and bad vertices for its counter-color.

I got WA on pretest 6. Not sure if the idea is wrong or my implementation My submission : 148381092 Any thoughts?

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

    I tried the same thing (but failed pretest 5) :(

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

    it is true that a good vertex(blue) must be surrounded by bad vertices(black) but it is not necessary that bad vertices be adjacent to good vertices. so if u two color the tree, u wouldn't take into consideration cases where two adjacent nodes are bad

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

    Pretty sure it's finding the max independent set.

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

      I did it in sort of dp style. Rooted the tree at 1.

      dp[i][0] = <C,S> means ith node is not good and fill its children however you want such that max good vertices below my subtree is C with sum of edges as S.

      dp[i][1] = <C,S> means ith node is good and fill its children however you want such that max good vertices below my subtree is C with sum of edges as S.

      For transitions dp[i][1] depends on dp[c][0] where c is children of i since you are good, children can't be good.

      dp[i][0] picks dp[c][0] or dp[c][1] according to which is best.

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

        did it work ? i tried the same thing but kept getting WA in pretest 5 or 6

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

          You also need to keep track of the cost in case dp[i][0]==dp[i][1].

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

            Yeah the reason for storing S in the dp is to handle the case of dp[c][0] == dp[c][1]

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

    How does the problem change after removing all the leaves?

    If there exists some tree for which bipartite doesn't work, I can just create a new tree by attaching a single node to each leaf and your soln won't work for it.

    And try the following graph if you don't get why bipartite is incorrect:

    Input Graph
    Answer
    A Correct Solution
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i defined dp[i][0] = max good vertices if vertex i is good and dp[i][1] for bad. and dp[i][0] = 1 + all dp[ne][1] in neighbours and dp[i][1] = max(dp[ne][0] and dp[ne][1]) for all neighbours. Is is correct ? i kept getting WA in either pretest 5 or 6

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

        I guess in dp[i][1] case if dp[ne][0] and dp[ne][1] are equal then how are you ensuring which one to pick to get minimum sum.

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

          Yup, this is likely the issue.

          One way to solve this is to store the dp value as a pair $$$<\text{max number of nodes}, -(\text{min sum of degree})>$$$, then taking max works as expected.

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

          did this as well :( 148378253

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

      Oh I see. I get it. Thanks!

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

      Wait, in your explanation should it be $$$dp_{x, 0} = max(dp_{v,0} , dp_{v,1})$$$ ?

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

        no if a vertex is good, then its neighbour cannot be good. so for dp[x][0] we only see dp[v][1]

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

    Failing testcase : Ticket 724

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

Could someone share their approach for B ?

I tried solving it by sorting the array (minimize the Blue sum) and using prefix sum, but failed. I think this is because my approach colored all the numbers.

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

    Use sum of two smallest numbers as small sum, and biggest number as big sum.

    If both sums are ok ans=YES else add next smallest number to small sum, next biggest number to big sum. Repeat.

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

    Well, I also sorted it first, and then kept on calculating Blue Sum from the start and Red Sum from the end of the array. Also, to maintain the count(Blue) > count(Red), I initialised the starting index to be 1(0-based indexing) while initialising Blue Sum to be equal to the first array element.

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

submitted C in the last minute

took more than 1 hour to realize brute-forcing all subsets of factorial values is feasible

but brute-forcing all subsets of 2-power values is infeasible which gave me a wrong intuition that the factorial counterpart is also infeasible

I hope in the future I can be more familiar with the thresholds of feasibility.

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

    Why we Can't use one factorial two times?

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

      because we need distinct numbers

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

        Got it now. I Read the question again. Sucks when missed important point.

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

        Please explain and share your approach!

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

      That would make it way harder so be glad about it

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

      the problem description said distinct.

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

    Even if it was feasible to brute force all powers of 2, how would you find the needed amount of factorials?

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

      I don't know how to find the needed factorials except for brute-force, so I should have taken that approach initially. Unfortunately the infeasibility of brute-forcing 2-powers gave me the wrong intuition that brute-forcing factorials is also infeasible.

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

      No Idea. That is why I was not able to solve C. Was expecting there is some other trick to solve the problem which I was not able to think.

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

      There are not much factorials in range, it is only 14 numbers. So you can create only 2^14 sums from these numbers. Just try all of them.

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

    Went through the same trajectory, except I took even more time to realise this and couldn't submit my code in time :( It also somehow escaped by mind that combinations of powers of 2 literally define every single number in exactly one possible way.

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

Thanks for the contest, I don't know why I did so dumb on A and B, But after all I really liked the problems.

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

In c, finding all the numbers powerful in a set then take a number which are just less than n and subtracting them from n is not feasible why?

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

    For 184 the correct answer is 120 + 64 but your approach would yield 128 + 32 (edited from 56) + 24.

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

      How did you get 56 here....

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

        184 — 128 = 56. The point is that you can't pick the max number <= n.

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

          But 56 won't be in set, so it would look like 184 → 128 + 32 + 24 (wrong approach)

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

            Ah sorry, I meant 128 + 32. Thanks :)

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

what is pretest 6 of D? ಥ_ಥ

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

    If you were doing BFS solution from leaves, It would fail. Optimal solution will be reached by dynamic programming.

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

I think D is just Maximum Independent set with least total degree which can be solved by dp. I realised this, but could not reconstruct the solution from the dp before the contest ended.

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

How to solve E? I was looking for numbers with the same prime factors

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

    Take 2, 4, 8, ... as example. In the row starting with 2, you get 2^1, 2^2, ... In the row starting with 4, you get 2^2, 2^4, ..., so what in the cells are these powers of 2: 1 ~ M, 2 * 1 ~ 2 * M, 3 * 1 ~ 3 * M, ..., depending on how many powers of 2 are less than or equal to N. Then, what you need to do is calculate how many distinct number is in this list. Sum up all the length of lists of a number that is not power of another one. Don't forget 1.

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

Any counterexample on D solving with 2-coloring?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    6
    1 3
    2 3
    3 4
    4 5
    4 6
    
  • »
    »
    5 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    6

    1 2

    1 3

    1 4

    4 5

    4 6

    The output should be:

    4 6

    1 1 1 1 1 1

    The idea is that although there can be no 2 adjacent good nodes, this does not mean that there can be no 2 adjacent bad nodes. Unfortunately I realized that a short time just before the contest ended.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    Input Graph
    Answer
    Visualization
»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hey,
In the first problem, why this works cout << s/(n*n) << '\n';
but using cout << (int)(s/pow(n,2)) << '\n'; gives wrong answer in test 2?

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

    because pow() returns double which may cause precision issue.

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

    It turns out s/(n*n) is bounded within INT_MAX because bounds of s depend on n. Problem was caused due to precision issue of pow() as Aging1986 pointed out.

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

tried dp in D but it doesn't work... so retried bipartite and failed again.

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

Is it possible to output -1 in c ??

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

    no, any number can be represented as sums of powers of two (its binary representation).

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

Getting MLE on test 39 on problem D just because I used longs and a relatively high memory constant is the most unfair thing ever...

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

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

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

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

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

Nice contest!

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

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

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

Would this idea work for D?

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

    It won't work

    Edit:

    Actually I don't know.

    Edit2:

    I've coded it — it doesnt find the minimal value correctly.

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

Hi in problem C this solution i want to get minimum number of distinct integers their sum equal to n in vector (fact) how can i do that : code : https://ideone.com/sjl5Od

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

Finally, contest with a normal time :D

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

Finally got rated :)

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

can we solve problem c using dynamic programming