티스토리 뷰
반응형
http://codeforces.com/problemset/problem/888/E
Difficulty : 4/10
I couldn't solve this problem during the contest.
this problem is not very difficult. but need some technique.
making subset (dfs or bitmask) and find max value ( low bound search )
This problem needs meet in the middle algorithm. meet in the middle algorithm is similar to brute froce.
meet in the middle is for big size, so that brute force cant be used.
In this problem - if n=35, we can make all subset in 2^35 *O(1) time. but it is too big time complexity to solve in time.
so we first divide set into two subset, then we make all subset A and B. (need DFS or bitmask)
these subset are equivalent to all possible sum of subset.
and then we find max value.
now the time to use search algorithm that is called low bound.
It returns min index that greater or equal to argument.
I use nested for loop (bruteforce) to find maxvalue .
so it return time limit exceeded.....
eg) {a, b, c , d , e}
=> divide in to two subset, {a, b, c}, {d, e}
=> make all possible subset
+ {a, b, c, a+b, a+c, b+c, a+b+c}, {d, e, d+e}
=> plus empty set
+ { 0, a, b, c, a+b, a+c, b+c, a+b+c} , {0, d, e, d+e}
=> find max value.
Source Code:
반응형
'알고리즘 문제 > sort, search' 카테고리의 다른 글
Leetcode - 1. Two Sum (0) | 2022.07.21 |
---|---|
codeforces 283 div2 d tennis game (0) | 2019.11.02 |
CF 1041D Glider (0) | 2018.09.20 |
Codeforces : Ordering Pizza (0) | 2017.10.02 |
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- rosen
- 최단경로 알고리즘
- 이산수학
- Arena
- 조합 코딩
- arena simulation
- 시뮬레이션
- Simulation
- 아레나
- Discrete Mathematics
- 대규모 시스템 설계 기초
- 로젠
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
- 데이터 중심 애플리케이션 설계
- beginning javascript
- 아레나 시뮬레이션
- 백준
- 이산 수학
- paul wilton
- grafana cloud
- flutter
- 명제논리
- Propositional and Predicate Logic
- Trie
- 엄청난 인내심과 시뮬레이션을 위한 아레나 툴
- 그라파나
- 아레나시뮬레이션
- 자바스크립트 예제
- 자바스크립트
- javascript
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |
글 보관함